Reforming an Unfair Allocation by Exchanging Goods
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_ | 1866916543504318464 |
|---|---|
| author | Yuen, Sheung Man Igarashi, Ayumi Kamiyama, Naoyuki Suksompong, Warut |
| author_facet | Yuen, Sheung Man Igarashi, Ayumi Kamiyama, Naoyuki Suksompong, Warut |
| contents | Fairly allocating indivisible goods is a frequently occurring task in everyday life. Given an initial allocation of the goods, we consider the problem of reforming it via a sequence of exchanges to attain fairness in the form of envy-freeness up to one good (EF1). We present a vast array of results on the complexity of determining whether it is possible to reach an EF1 allocation from the initial allocation and, if so, the minimum number of exchanges required. In particular, we uncover several distinctions based on the number of agents involved and their utility functions. Furthermore, we derive essentially tight bounds on the worst-case number of exchanges needed to achieve EF1. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_19264 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Reforming an Unfair Allocation by Exchanging Goods Yuen, Sheung Man Igarashi, Ayumi Kamiyama, Naoyuki Suksompong, Warut Computer Science and Game Theory Computational Complexity Fairly allocating indivisible goods is a frequently occurring task in everyday life. Given an initial allocation of the goods, we consider the problem of reforming it via a sequence of exchanges to attain fairness in the form of envy-freeness up to one good (EF1). We present a vast array of results on the complexity of determining whether it is possible to reach an EF1 allocation from the initial allocation and, if so, the minimum number of exchanges required. In particular, we uncover several distinctions based on the number of agents involved and their utility functions. Furthermore, we derive essentially tight bounds on the worst-case number of exchanges needed to achieve EF1. |
| title | Reforming an Unfair Allocation by Exchanging Goods |
| topic | Computer Science and Game Theory Computational Complexity |
| url | https://arxiv.org/abs/2412.19264 |