Journal article

### Envy-freeness in house allocation problems

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
Publication status:
Published
Peer review status:
Peer reviewed

### Access Document

Files:
• (pdf)
Publisher copy:
10.1016/j.mathsocsci.2019.07.005

### Authors

More by this author
Institution:
University of Oxford
Department:
Computer Science
Role:
Author
More by this author
Institution:
University of Oxford
Department:
Computer Science
Department:
Unknown
Role:
Author
More by this author
Institution:
University of Oxford
Department:
Computer Science
Role:
Author
ORCID:
0000-0003-1105-3856
Publisher:
Elsevier Publisher's website
Journal:
Mathematical Social Sciences Journal website
Volume:
101
Pages:
104-106
Publication date:
2019-07-30
Acceptance date:
2019-07-22
DOI:
ISSN:
0165-4896
Pubs id:
pubs:1046097
UUID:
uuid:6de5c0c9-e387-4a32-bf11-301bbaf35d56
Source identifiers:
1046097
Local pid:
pubs:1046097
Language:
English