[UTMD-056] Strategyproof Allocation Mechanisms with Endowments and M-convex Distributional Constraints (published in Artificial Intelligence, 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 type of object has multiple copies (e.g., multiple seats in 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 two mechanisms that are strategyproof, feasible (they always satisfy distributional constraints), and individually rational, assuming the distributional constraints are represented by an M-convex set. One mechanism, based on Top Trading Cycles, is Pareto efficient; the other, which belongs to the mechanism class specified by Kojima et al. [1], satisfies a relaxed fairness requirement. 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. Finally, we experimentally evaluate the performance of these mechanisms by a computer simulation.

*Published in Artificial Intelligence

PDF