Strategy-proof and Envy-free Mechanisms for House Allocation

Priyanka Shende and Manish Purohit

Papers from arXiv.org

Abstract: 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 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 efficiency and envy-freeness in the class of strategy-proof 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 Pairwise Exchange mechanisms and make the surprising observation that strategy-proofness is equivalent to envy-freeness within this class. We characterize the set of all neutral and strategy-proof (and hence, also envy-free) mechanisms in this family and show that they admit a very simple linear representation.

Date: 2020-10
New Economics Papers: this item is included in nep-des
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://arxiv.org/pdf/2010.16384 Latest version (application/pdf)

Related works:
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:arx:papers:2010.16384

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().