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

Preview

Text 1905.00468v2.pdf - Accepted Version Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (82kB) | Preview

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