Weighted Envy-Freeness in House Allocation
<|reference_start|>Weighted Envy-Freeness in House Allocation: The classic house allocation problem involves assigning $m$ houses to $n$ agents based on their utility functions, ensuring each agent receives exactly one house. A key criterion in these problems is satisfying fairness constraints such as envy-freeness. We extend this problem by considering agents with arbitrary weights, focusing on the concept of weighted envy-freeness, which has been extensively studied in fair division. We present a polynomial-time algorithm to determine whether weighted envy-free allocations exist and, if so, to compute one. Since weighted envy-free allocations do not always exist, we also investigate the potential of achieving such allocations through the use of subsidies. We provide several characterizations for weighted envy-freeable allocations (allocations that can be turned weighted envy-free by introducing subsidies) and show that they do not always exist, which is different from the unweighted setting. Furthermore, we explore the existence of weighted envy-freeable allocations in specific scenarios and outline the conditions under which they exist.<|reference_end|>
@article{dai2024weighted,
    title={Weighted Envy-Freeness in House Allocation},
    author={Sijia Dai, Yankai Chen, Xiaowei Wu, Yicheng Xu, Yong Zhang},
    journal={arXiv preprint arXiv:2408.12523},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.12523},
    primaryClass={cs.GT}
}