Strategy-Proof and Envy-Free Random Assignment

Christian Basteck and Lars Ehlers
Additional contact information
Christian Basteck: WZB Berlin

No 307, Rationality and Competition Discussion Paper Series from CRC TRR 190 Rationality and Competition

Abstract: 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 ≤ n2 (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.

Keywords: random assignment; strategy-proofness; envy-freeness; q-unanimity (search for similar items in EconPapers)
JEL-codes: D63 D70 (search for similar items in EconPapers)
Date: 2021-12-22
New Economics Papers: this item is included in nep-des and nep-mic
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://rationality-and-competition.de/wp-content/uploads/2021/12/307.pdf (application/pdf)

Related works:
Journal Article: Strategy-proof and envy-free random assignment (2023)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:rco:dpaper:307

Access Statistics for this paper

More papers in Rationality and Competition Discussion Paper Series from CRC TRR 190 Rationality and Competition
Bibliographic data for series maintained by Viviana Lalli ().