Efficient and strategy-proof mechanism under general constraints

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 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 that 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 \emph{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 (SP). 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.