Breaking Ties among Equals: Serial and Sequential Dictatorships in House Allocation

Abstract

We study the deterministic allocation of indivisible objects to agents under unit demand and strict preferences, without monetary transfers. When every agent must receive an object, two agents who report identical preferences cannot be treated equally, so every mechanism embodies a rule for breaking such ties. We introduce two invariance requirements on this rule. Fair treatment of equals requires the favored member of every preference-identical pair to be the same at all profiles; the weaker pairwise tie-breaking allows the favored member to depend on the reports of the other agents but not on the pair's common report. Combined with non-wastefulness and strategy-proofness, (i) fair treatment of equals characterizes the serial dictatorships, (ii) pairwise tie-breaking and non-bossiness characterize the sequential dictatorships, and (iii) pairwise tie-breaking and the identical-preference lower bound---which compares each agent's assignment with her outcome when everyone shares her ranking---characterize the serial dictatorships once again. When agents may remain unassigned, the first two characterizations extend upon adding individual rationality, but the identical-preference lower bound no longer forces a fixed order. Among sequential dictatorships, the identical-preference lower bound is equivalent to boundedness: there is a priority whose $k$th-ranked agent is called after at most $k-1$ real objects have been assigned.

arXiv comment52 pages