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

Kenzo Imamura, Yasushi Kawase

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.