[UTMD-056] Strategyproof Allocation Mechanisms with Endowments and M-convex Distributional Constraints (by Takamasa Suzuki, Akihisa Tamura, Kentaro Yahiro, Makoto Yokoo, Yuzhe Zhang)

Author

Takamasa Suzuki, Akihisa Tamura, Kentaro Yahiro, Makoto Yokoo, Yuzhe Zhang

Abstract

We consider an allocation problem of multiple types of objects to agents, where each typeof object has multiple copies (e.g., multiple seats in a school), each agent is endowedwith an object, and some distributional constraints are imposed on the allocation (e.g.,minimum/maximum quotas). We develop two mechanisms that are strategyproof, feasible(they always satisfy distributional constraints), and individually rational, assuming thedistributional constraints are represented by an M-convex set. One mechanism, basedon Top Trading Cycles, is Pareto efficient; the other, which belongs to the mechanismclass specified by Kojima etal.[1], satisfies a relaxed fairness requirement. The classof distributional constraints we consider contains many situations raised from realisticmatching problems, including individual minimum/maximum quotas, regional maximumquotas, type-specific quotas, and distance constraints. Finally, we experimentally evaluatethe performance of these mechanisms by a computer simulation.

PDF