Gan, Jiarui and Suksompong, Warut and Voudouris, Alexandros A (2019) Envy-freeness in house allocation problems. Mathematical Social Sciences, 101. pp. 104-106. DOI https://doi.org/10.1016/j.mathsocsci.2019.07.005
Gan, Jiarui and Suksompong, Warut and Voudouris, Alexandros A (2019) Envy-freeness in house allocation problems. Mathematical Social Sciences, 101. pp. 104-106. DOI https://doi.org/10.1016/j.mathsocsci.2019.07.005
Gan, Jiarui and Suksompong, Warut and Voudouris, Alexandros A (2019) Envy-freeness in house allocation problems. Mathematical Social Sciences, 101. pp. 104-106. DOI https://doi.org/10.1016/j.mathsocsci.2019.07.005
Abstract
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.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | cs.GT |
| Divisions: | Faculty of Science and Health Faculty of Science and Health > Computer Science and Electronic Engineering, School of |
| SWORD Depositor: | Unnamed user with email elements@essex.ac.uk |
| Depositing User: | Unnamed user with email elements@essex.ac.uk |
| Date Deposited: | 16 Apr 2020 13:30 |
| Last Modified: | 30 Oct 2024 16:17 |
| URI: | http://repository.essex.ac.uk/id/eprint/27268 |
Available files
Filename: 1905.00468v2.pdf
Licence: Creative Commons: Attribution-Noncommercial-No Derivative Works 3.0