Strategy-proof and envy-free random assignment

• 成果类型: Article
• 署名作者: Basteck, Christian; Ehlers, Lars
• 署名单位: Universite de Montreal; Universite de Montreal
• 刊物名称: JOURNAL OF ECONOMIC THEORY
• ISSN/ISSBN: 0022-0531
• DOI: 10.1016/j.jet.2023.105618
• 发表日期: 2023
• 关键词: Random assignment; strategy-proofness; Envy-freeness; q-unanimity

摘要

We study the random assignment of indivisible objects among a set of agents with strict preferences. We show that there exists no mechanism which is unanimous, strategy-proof and envy-free. Weakening the first requirement to q-unanimity - i.e., when every agent ranks a different object at the top, then each agent shall receive his most-preferred object with probability of at least q - we show that a mechanism satisfying strategy-proofness, envy-freeness and ex-post weak non-wastefulness can be q-unanimous only for q <= n 2 (where n is the number of agents). To demonstrate that this bound is tight, we introduce a new mechanism, Random-Dictatorship-cum-Equal-Division (RDcED), and show that it achieves this maximal bound when all objects are acceptable. In addition, for three agents, RDcED is characterized by the first three properties and ex-post weak efficiency. If objects may be unacceptable, strategy-proofness and envy-freeness are jointly incompatible even with ex-post weak non-wastefulness.(c) 2023 Elsevier Inc. All rights reserved.