TY - JOUR
T1 - On the complexity of fair house allocation
AU - Kamiyama, Naoyuki
AU - Manurangsi, Pasin
AU - Suksompong, Warut
N1 - Funding Information:
This work was partially supported by JSPS KAKENHI Grant Number JP20H05795 , Japan and by an NUS Start-up Grant. We thank the anonymous reviewer for valuable feedback.
Publisher Copyright:
© 2021 Elsevier B.V.
PY - 2021/7
Y1 - 2021/7
N2 - We study fairness in house allocation, where m houses are to be allocated among n agents so that every agent receives one house. We show that maximizing the number of envy-free agents is hard to approximate to within a factor of n1−γ for any constant γ>0, and that the exact version is NP-hard even for binary utilities. Moreover, we prove that deciding whether a proportional allocation exists is computationally hard, whereas the corresponding problem for equitability can be solved efficiently.
AB - We study fairness in house allocation, where m houses are to be allocated among n agents so that every agent receives one house. We show that maximizing the number of envy-free agents is hard to approximate to within a factor of n1−γ for any constant γ>0, and that the exact version is NP-hard even for binary utilities. Moreover, we prove that deciding whether a proportional allocation exists is computationally hard, whereas the corresponding problem for equitability can be solved efficiently.
UR - http://www.scopus.com/inward/record.url?scp=85108009343&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85108009343&partnerID=8YFLogxK
U2 - 10.1016/j.orl.2021.06.006
DO - 10.1016/j.orl.2021.06.006
M3 - Article
AN - SCOPUS:85108009343
SN - 0167-6377
VL - 49
SP - 572
EP - 577
JO - Operations Research Letters
JF - Operations Research Letters
IS - 4
ER -