# Envy-Freeness in House Allocation Problems

@article{Gan2019EnvyFreenessIH, title={Envy-Freeness in House Allocation Problems}, author={Jiarui Gan and Warut Suksompong and Alexandros A. Voudouris}, journal={Math. Soc. Sci.}, year={2019}, volume={101}, pages={104-106} }

We consider the house allocation problem, where $m$ houses are to be assigned to $n$ agents so that each agent gets exactly one house. We present a polynomial-time algorithm that determines whether an envy-free assignment exists, and if so, computes one such assignment. We also show that an envy-free assignment exists with high probability if the number of houses exceeds the number of agents by a logarithmic factor.

#### Topics from this paper

#### 10 Citations

On the Complexity of Fair House Allocation

- Computer Science
- Oper. Res. Lett.
- 2021

It is shown that maximizing the number of envy-free agents is hard to approximate to within a factor of n for any constant γ > 0, and that the exact version is NP-hard even for binary utilities. Expand

Fair Resource Sharing and Dorm Assignment

- Computer Science
- AAMAS
- 2020

It is shown that when the capacities of the dorms are 2, a Pareto envy-free assignment always exists and can be found in polynomial time; however, if the capacities increase to 3, Pare to envy-freeness cannot be guaranteed any more. Expand

Two-Sided Matching Meets Fair Division

- Computer Science
- IJCAI
- 2021

It is shown that (a slight strengthening of) DEF1 cannot always be achieved, but in the special case where both sides have identical preferences, the round-robin algorithm with a carefully designed agent ordering achieves it. Expand

Fair Resource Sharing with Externailities

- Computer Science
- ArXiv
- 2020

It is shown that when the capacity of the dorms is 2, a Pareto envy-free assignment always exists and a polynomial-time algorithm is presented to compute such an assignment; nevertheless, the result fails to hold immediately when the capacities increase to 3, in which case even Pare to envy-freeness cannot be guaranteed. Expand

Envy-Free Matchings with One-Sided Preferences and Matroid Constraints

- Computer Science
- 2021

A polynomial-time algorithm is proposed which is a generalization of the algorithm proposed by Gan, Suksompong, and Voudouris for the one-to-one setting and considers a stronger variant of envy-freeness. Expand

Combining Fairness and Optimality when Selecting and Allocating Projects

- Computer Science
- IJCAI
- 2021

Fairness and optimality issues are explored and the analysis of the rank-maximality and popularity optimality concepts show that they are compatible with reasonable fairness requirements related to rank-based envy-freeness and can be adapted to select globally good projects according to the preferences of the agents. Expand

Envy-free Matchings in Bipartite Graphs and their Applications to Fair Division

- Mathematics
- 2019

A matching in a bipartite graph $G:=(X + Y,E)$ is said to be envy-free if no unmatched vertex in $X$ is adjacent to a mathced vertex in $Y$. Every perfect matching is envy-free, but envy-free… Expand

Fair Division of Time: Multi-layered Cake Cutting

- Computer Science
- IJCAI
- 2020

This work shows that envy-free allocations that are both feasible and contiguous are guaranteed to exist for up to three agents with two types of preferences, when the number of layers is two, and devise an algorithm for computing proportional allocations for any number of agents and layers. Expand

Closing Gaps in Asymptotic Fair Division

- Computer Science, Mathematics
- SIAM J. Discret. Math.
- 2021

It is proved that the classical round-robin algorithm is likely to produce an envy-free allocation provided that $m=\Omega(n\log n/\log\ log n)$, matching the lower bound from prior work. Expand

Fair multi-cake cutting

- Mathematics, Computer Science
- Discret. Appl. Math.
- 2021

A polynomial-time algorithm that guarantees to each agent at least min ( 1 ∕ n , k ∕ ( m + n − 1 ) ) of the total value, and shows that this is the largest fraction that can be guaranteed. Expand

#### References

SHOWING 1-10 OF 16 REFERENCES

Local envy-freeness in house allocation problems

- Computer Science
- Autonomous Agents and Multi-Agent Systems
- 2019

We study the fair division problem consisting in allocating one item per agent so as to avoid (or minimize) envy, in a setting where only agents connected in a given network may experience envy. In a… Expand

Pareto Optimality in House Allocation Problems

- Computer Science, Mathematics
- ISAAC
- 2005

The concept of a signature is introduced, which allows us to give a characterization, checkable in linear time, of instances that admit a unique Pareto optimal matching. Expand

Pareto Optimality in House Allocation Problems

- Computer Science
- ISAAC
- 2004

The concept of a signature is introduced, which allows us to give a characterization, checkable in linear time, of instances that admit a unique Pareto optimal matching. Expand

The Efficient Allocation of Individuals to Positions

- Economics
- Journal of Political Economy
- 1979

In a variety of contexts, individuals must be allocated to positions with limited capacities. Legislators must be assigned to committees, college students to dormitories, and urban homesteaders to… Expand

On a conjecture by gale about one-sided matching problems

- Mathematics
- 1990

Abstract This paper proves the following result on one-sided matching problems: when there are n objects to be assigned to n agents, for n ⩾3, there exits no mechanism that satisfies symmetry, Pareto… Expand

Approximation Algorithms for Computing Maximin Share Allocations

- Computer Science, Mathematics
- ICALP
- 2015

It is proved that in randomly generated instances, with high probability there exists a maximin share allocation, which can be seen as a justification of the experimental evidence reported in [5, 14], that maximin sharing allocations exist almost always. Expand

Approximation Algorithms for Computing Maximin Share Allocations

- Computer Science, Mathematics
- ACM Trans. Algorithms
- 2017

It is proved that in randomly generated instances, maximin share allocations exist with high probability, and this improves upon the algorithm of Procaccia and Wang (2014), which is also a 2/3-approximation but runs in polynomial time only for a constant number of agents. Expand

RANDOM SERIAL DICTATORSHIP AND THE CORE FROM RANDOM ENDOWMENTS IN HOUSE ALLOCATION PROBLEMS

- Economics
- 1998

Random serial dictatorship and the core from random endowments in house allocation problems

Bipartite Envy-Free Matching

- Computer Science, Mathematics
- ArXiv
- 2019

This paper presents sufficient and necessary conditions for the existence of a non-empty bipartite Envy-Free Matching, based on cardinality of neighbor-sets, similarly to Hall's condition for theexistence of a perfect matching. Expand

Algorithmics of Matching Under Preferences

- Computer Science
- Bull. EATCS
- 2014

This book builds on the author’s prior research in this area, and also his practical experience of developing algorithms for matching kidney patients to donors in the UK, for assigning medical students to hospitals in Scotland, and for allocating students to elective courses and projects. Expand