 Strategy-Proof Tie-BreakingLars Ehlers and Alexander Westkamp Cahiers de recherche from Universite de Montreal, Departement de sciences economiques Abstract: 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. Keywords: Weak priorities; stability; constrained efficiency; strategy-proofness. (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:mtl:montde:2011-07 Access Statistics for this paper More papers in Cahiers de recherche from Universite de Montreal, Departement de sciences economiques Contact information at EDIRC. |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.