Efficient Allocation Mechanism with Endowments and Distributional Constraints

We consider an allocation problem of multiple types objects to agents, where each type of an object has multiple copies (e.g., multiple seats of a school), each agent is endowed with an object, and some distributional constraints are imposed on the allocation (e.g., minimum/maximum quotas). We develop a mechanism that is based on the Top Trading Cycles mechanism, which is strategy-proof, feasible (always satisfies distributional constraints), Pareto efficient, and individually rational, assuming the distributional constraints are represented as an M-convex set. The class of distributional constraints we consider contains many situations raised from realistic matching problems, including individual minimum/maximum quotas, regional maximum quotas, type-specific quotas, and distance constraints. To the best of our knowledge, we are the first to develop a mechanism with these desirable properties.