Envy-Free House Allocation with Minimum Subsidy
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914704642801664 |
|---|---|
| author | Choo, Davin Ling, Yan Hao Suksompong, Warut Teh, Nicholas Zhang, Jian |
| author_facet | Choo, Davin Ling, Yan Hao Suksompong, Warut Teh, Nicholas Zhang, Jian |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_01162 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Envy-Free House Allocation with Minimum Subsidy Choo, Davin Ling, Yan Hao Suksompong, Warut Teh, Nicholas Zhang, Jian Computer Science and Game Theory Computational Complexity 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. |
| title | Envy-Free House Allocation with Minimum Subsidy |
| topic | Computer Science and Game Theory Computational Complexity |
| url | https://arxiv.org/abs/2403.01162 |