On Truthful Mechanisms without Pareto-efficiency: Characterizations and Fairness

Moshe Babaioff and Noam Manaker Morag have published a paper on arXiv (2411.11131) characterizing truthful mechanisms for allocating heterogeneous, indivisible goods to strategic agents without money. They prove that for important classes of strict ordinal preferences (lexicographic and all strict preferences), serial-quota mechanisms—where agents pick goods in a predefined order—are the only mechanisms that are strategy-proof, non-bossy, and neutral. Crucially, this holds even when mechanisms are not Pareto-efficient, extending prior work that required efficiency.

The authors generalize these results to cardinal preferences, including any valuation class containing additive valuations. This leads to strong negative implications for designing truthful mechanisms for fair allocation of indivisible goods: the space of possible mechanisms is severely limited. The findings have direct relevance to algorithmic game theory and theoretical economics, particularly for problems like course allocation, housing assignment, and resource distribution where strategic agents must report preferences truthfully.