Envy-Free House Allocation with Minimum Subsidy
arXiv:2403.01162 · doi:10.1016/j.orl.2024.107103
Abstract
House allocation refers to the problem where houses are to be allocated to 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 differs from by an additive constant or if the agents have identical utilities.