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 $n^{1-\gamma}$ for any constant $\gamma>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.
翻译:我们研究住房分配的公平性,在住房分配中,美元住房将由一美元代理商分配,这样,每个代理商都能得到一栋房屋。 我们证明,对于任何恒定的$\gamma>0美元来说,最大限度地增加无嫉妒的代理商数量很难接近于1-\gamma}美元这一系数,而准确的版本甚至对于二元公用事业来说也是坚硬的NP。 此外,我们证明,确定比例分配是否在计算上是困难的,而相应的公平性问题是可以有效解决的。