Research Repository

Envy-freeness in house allocation problems

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

1905.00468v2.pdf - Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (82kB) | Preview


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

Actions (login required)

View Item View Item