On two competing mechanisms for priority-based allocation problems

• 成果类型: Article
• 署名作者: Kesten, O
• 署名单位: University of Rochester
• 刊物名称: JOURNAL OF ECONOMIC THEORY
• ISSN/ISSBN: 0022-0531
• DOI: 10.1016/j.jet.2004.11.001
• 发表日期: 2006
• 页码: 155-171
• 关键词: Indivisible goods; agent-optimal stable mechanism; top trading cycles mechanism; acyclicity

摘要

We consider the priority-based allocation problem: there is a set of indivisible objects with multiple supplies (e.g., schools with seats) and a set of agents (e.g., students) with priorities over objects (e.g., proximity of residence area). We study two well-known and competing mechanisms. The agent-optimal stable mechanism (AOSM) allots objects via the deferred acceptance algorithm. The top trading cycles mechanism (TTCM) allots objects via Gale's top trading cycles algorithm. We show that the two mechanisms are equivalent, or TTCM is fair (i.e., respects agents' priorities), or resource monotonic, or population monotonic, if and only if the priority structure is acyclic. Furthermore, if AOSM fails to be efficient (consistent) for a problem, TTCM also fails to be fair (consistent) for it. However, the converse is not necessarily true. (c) 2004 Elsevier Inc. All rights reserved.