RECORD
Strategy-proof and Envy-free Mechanisms for House Allocation
Theoretical Economics · Submitted 30 Oct 2020
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim 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.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | We consider the problem of allocating indivisible objects to agents when agents have strict preferences over objects. | background 1.00 | 0.09 | 0.02 | asserted 0.86 |
| s1 | There are inherent trade-offs between competing notions of efficiency, fairness and incentives in assignment mechanisms. | background 1.00 | 0.07 | 0.04 | asserted 1.00 |
| s2 | 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. | background 0.97 | 0.08 | 0.04 | asserted 0.50 |
| s3 | 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? | gap 0.76 | 0.09 | 0.06 | unclear 0.56 |
| s4 | Our contributions in this paper are twofold. | contribution 0.99 | 0.78 | 0.03 | asserted 0.86 |
| s5 | First, we further explore the incompatibility between efficiency and envy-freeness in the class of strategy-proof mechanisms. | contribution 1.00 | 0.86 | 0.10 | asserted 0.68 |
| s6 | 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. | result 0.68 | 0.95 | 0.38 | asserted 1.00 |
| s7 | 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. | contribution 0.87 | 0.96 | 0.22 | asserted 1.00 |
| s8 | 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. | result 0.55 | 0.96 | 0.20 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original 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.
Human review
How the literature uses it
What this paper does with the arXiv papers it cites
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.