Strategy-Proofness Makes the Difference: Deferred-Acceptance with Responsive Priorities

• 成果类型: Article
• 署名作者: Ehlers, Lars; Klaus, Bettina
• 署名单位: Universite de Montreal; Universite de Montreal; University of Lausanne
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2014.0662
• 发表日期: 2014
• 页码: 949-966
• 关键词: House allocation; school choice; college admissions; boston mechanism; EFFICIENCY; STABILITY; algorithm; marriage; MARKETS

摘要

In college admissions and student placements at public schools, the admission decision can be thought of as assigning indivisible objects with capacity constraints to a set of students such that each student receives at most one object and monetary compensations are not allowed. In these important market design problems, the agent-proposing deferred-acceptance (DA) mechanism with responsive strict priorities performs well, and economists have successfully implemented DA-mechanisms or slight variants thereof. We show that almost all real-life mechanisms used in such environments-including the large classes of priority mechanisms and linear programming mechanisms-satisfy a set of simple and intuitive properties. Once we add strategy-proofness to these properties, DA-mechanisms are the only ones surviving. In market design problems that are based on weak priorities (like school choice), generally multiple tie-breaking (MTB) procedures are used and then a mechanism is implemented with the obtained strict priorities. By adding stability with respect to the weak priorities, we establish the first normative foundation for MTB-DA-mechanisms that are used in New York City.