Envy-Free House Allocation with Minimum Subsidy
<|reference_start|>Envy-Free House Allocation with Minimum Subsidy: House allocation refers to the problem where $m$ houses are to be allocated to $n$ agents so that each agent receives one house. Since an envy-free house allocation does not always exist, we consider finding such an allocation in the presence of subsidy. We show that computing an envy-free allocation with minimum subsidy is NP-hard in general, but can be done efficiently if $m$ differs from $n$ by an additive constant or if the agents have identical utilities.<|reference_end|>
@article{choo2024envy-free,
    title={Envy-Free House Allocation with Minimum Subsidy},
    author={Davin Choo, Yan Hao Ling, Warut Suksompong, Nicholas Teh, Jian Zhang},
    journal={Operations Research Letters, 54:107103 (2024)},
    year={2024},
    doi={10.1016/j.orl.2024.107103},
    archivePrefix={arXiv},
    eprint={2403.01162},
    primaryClass={cs.GT cs.CC}
}