Abstract:
This study investigates efficient and strategy-proof mechanisms for allocating indivisible goods under constraints. First, we examine a setting without endowments. In this setting, we introduce a class of constraints-ordered accessibility-for which the serial dictatorship (SD) mechanism is Pareto-efficient (PE), individually rational (IR), and group strategy-proof (GSP). Then we prove that accessibility is a necessary condition for the existence of PE, IR, and GSP mechanisms. Moreover, we show an example where the SD mechanism with a dynamically constructed order satisfies PE, IR, and GSP if one school has an arbitrary accessible constraint and each of the other schools has a capacity constraint. Second, we examine a setting 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 PE, IR, and strategy-proof. We also demonstrate that a top trading cycles mechanism satisfies PE, IR, and GSP under any generalized matroid constraint. Finally, we observe that any two out of the three properties-PE, IR, and GSP-can be achieved under general constraints.