On Truthful Mechanisms without Pareto-efficiency: Characterizations and Fairness
For mechanism designers in fair allocation, this work provides a complete characterization of truthful mechanisms without efficiency, revealing fundamental limitations for fairness.
This paper characterizes all strategy-proof, non-bossy, and neutral mechanisms for allocating indivisible goods as serial-quota mechanisms, even without Pareto-efficiency, and extends the result to cardinal preferences including additive valuations. It then derives negative implications for truthful fair allocation mechanisms.
We consider the problem of allocating heterogeneous and indivisible goods among strategic agents, with preferences over subsets of goods, when there is no medium of exchange. This model captures the well studied problem of fair allocation of indivisible goods. Serial-quota mechanisms are allocation mechanisms where there is a predefined order over agents, and each agent in her turn picks a predefined number of goods from the remaining goods. These mechanisms are clearly strategy-proof, non-bossy, and neutral. Are there other mechanisms with these properties? We show that for important classes of strict ordinal preferences (as lexicographic preferences, and as the class of all strict preferences), these are the only mechanisms with these properties. Importantly, unlike previous work, we can prove the claim even for mechanisms that are not Pareto-efficient. Moreover, we generalize these results to preferences that are cardinal, including any valuation class that contains additive valuations. We then derive strong negative implications of this result on truthful mechanisms for fair allocation of indivisible goods to agents with additive valuations.