Gan, Jiarui and Suksompong, Warut and Voudouris, Alexandros A (2019) 'Envy-freeness in house allocation problems.' Mathematical Social Sciences, 101. 104 - 106. ISSN 0165-4896
|
Text
1905.00468v2.pdf - Accepted Version Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (82kB) | Preview |
Official URL: 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 |
---|---|
Divisions: | Faculty of Science and Health > Computer Science and Electronic Engineering, School of |
Depositing User: | Elements |
Date Deposited: | 16 Apr 2020 13:30 |
Last Modified: | 30 Jul 2020 01:00 |
URI: | http://repository.essex.ac.uk/id/eprint/27268 |
Actions (login required)
![]() |
View Item |