Strategy-proof and envy-free mechanisms for house allocation

• 成果类型: Article
• 署名作者: Shende, Priyanka; Purohit, Manish
• 署名单位: Amazon.com; Alphabet Inc.; Google Incorporated
• 刊物名称: JOURNAL OF ECONOMIC THEORY
• ISSN/ISSBN: 0022-0531
• DOI: 10.1016/j.jet.2023.105712
• 发表日期: 2023
• 关键词: Random assignment; Ordinal; strategy-proofness; Envy -freeness; Equal division

摘要

We consider the problem of allocating indivisible objects to agents when agents have strict preferences over objects. There are inherent trade-offs between competing notions of efficiency, fairness and incentives in such assignment mechanisms. It is, therefore, natural to consider mechanisms that satisfy two of these three properties in their strongest notions, while trying to improve on the third dimension. In this paper, we are motivated by the following question: Is there a strategy-proof and envy-free random assignment mechanism more efficient than equal division?Our contributions in this paper are twofold. First, we further explore the incompatibility between effi-ciency, fairness, and strategy-proofness within random assignment mechanisms. We define a new notion of efficiency that is weaker than ex-post efficiency and prove that any strategy-proof and envy-free mechanism must sacrifice efficiency even in this very weak sense. Next, we introduce a new family of mechanisms called Rank Exchange mechanisms that are strategy-proof and envy-free and stochastically dominate equal division. Further, we show that Rank Exchange mechanisms characterize the set of neutral, strategy-proof, and envy-free mechanisms that also satisfy a natural separability axiom that may be of independent interest.(c) 2023 Published by Elsevier Inc.