Weighted Envy-Freeness in House Allocation
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910573773455360 |
|---|---|
| author | Dai, Sijia Chen, Yankai Wu, Xiaowei Xu, Yicheng Zhang, Yong |
| author_facet | Dai, Sijia Chen, Yankai Wu, Xiaowei Xu, Yicheng Zhang, Yong |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_12523 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Weighted Envy-Freeness in House Allocation Dai, Sijia Chen, Yankai Wu, Xiaowei Xu, Yicheng Zhang, Yong Computer Science and Game Theory 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. |
| title | Weighted Envy-Freeness in House Allocation |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2408.12523 |