[UTMD-051] Efficient and Strategy-proof Mechanism under General Constraints (by Kenzo Imamura, Yasushi Kawase)

Author

Kenzo Imamura, Yasushi Kawase

Abstract

This study investigates efficient and strategy-proof mechanisms for allocating indivisible goods under constraints. First, we examine a scenario with endowments. We find that the generalized matroid is a necessary and sufficient condition on the constraint structure for the existence of a mechanism that is Pareto-efficient (PE), individually rational (IR), and strategy-proof (SP). We also demonstrate that a top trading cycles mechanism satisfies PE, IR, and group strategy-proofness (GSP) under any generalized matroid constraint. Second, we examine a scenario without endowments. In this scenario, we demonstrate that the serial dictatorship mechanism satisfies PE, IR, and GSP if the constraint satisfies a condition of ordered accessibility. Furthermore, we prove that accessibility is a necessary condition for the existence of PE, IR, and GSP mechanisms. Finally, we observe that any two out of the three properties―PE, IR, and GSP―could be achieved under general constraints.

PDF