2013/06/11 by Daniela Sabán, Jay Sethuraman · 1 citation
Economics, Econometrics and Finance · Decision Sciences · #Game Theory and Voting Systems #Auction Theory and Applications #Economic theories and models
paper · doi:10.1145/2492002.2482574
openalex publication_date 2013/06/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
We consider the problem of reallocating indivisible objects amongst a set of agents when the preference ordering of each agent may contain indifferences. The same model, but with strict preferences, goes back to the seminal work of Shapley and Scarf in 1974. When preferences are strict, we now know that the Top-Trading Cycles (TTC) mechanism invented by Gale is Pareto efficient, strategy-proof, and finds a core allocation, and that it is the only mechanism satisfying these properties. In the extensive literature on this problem since then, the TTC mechanism has been characterized in multiple ways, establishing its central role within the class of all allocation mechanisms. The question motivating our work is the extent to which these results can be generalized to the setting with indifferences. Our main contribution is a general framework to design strategyproof mechanisms that find a Pareto optimal allocation in the weak-core. Along the way, we establish a sufficient condition for a mechanism (within a broad class of mechanisms) to be strategyproof and use this condition to design fast algorithms for finding a "good" reallocation. Our results generalize and unify two (different) mechanisms for the reallocation problem derived, independently of each other, by Manjunath and Jaramillo, and Alcalde-Unzu and Molis.