2024/08/22 by Sijia Dai, Yankai Chen, Dai, Sijia +7 · 1 citation
Business, Management and Accounting · #Computer Science and Game Theory (cs.GT) #Dispute Resolution and Class Actions #Diverse Legal and Medical Studies #FOS: Computer and information sciences #Sharing Economy and Platforms
paper · pdf · doi:10.48550/arxiv.2408.12523
openalex publication_date 2024/08/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.