Strategy-Proof Tie-Breaking

We study a general class of priority-based allocation problems with weak priority orders and identify conditions under which there exists a strategy-proof mechanism which always chooses an agent-optimal stable, or constrained efficient, matching. A priority structure for which these two requirements are compatible is called solvable. For the general class of priority-based allocation problems with weak priority orders, we introduce three simple necessary conditions on the priority structure. We show that these conditions completely characterize solvable environments within the class of indifferences at the bottom (IB) environments, where ties occur only at the bottom of the priority structure. This generalizes and unifies previously known results on solvable and unsolvable environments established in school choice, housing markets and house allocation with existing tenants. We show how the previously known solvable cases can be viewed as extreme cases of solvable environments. For sufficiency of our conditions we introduce a version of the agent-proposing deferred acceptance algorithm with exogenous and preference-based tie-breaking.