Envy-Freeness in House Allocation Problems
About
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.
Jiarui Gan, Warut Suksompong, Alexandros A. Voudouris• 2019
Related benchmarks
| Task | Dataset | Result | Rank | |
|---|---|---|---|---|
| Envy-Free House Allocation | House Allocation 0/1 preferences | Sum Score20 | 1 | |
| Envy-Free House Allocation | House Allocation Identical preferences | Sum20 | 1 | |
| Envy-Free House Allocation | House Allocation Additive Monotonic preferences | Sum Utility20 | 1 |
Showing 3 of 3 rows