Reachability of Fair Allocations via Sequential Exchanges
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915023709798400 |
|---|---|
| author | Igarashi, Ayumi Kamiyama, Naoyuki Suksompong, Warut Yuen, Sheung Man |
| author_facet | Igarashi, Ayumi Kamiyama, Naoyuki Suksompong, Warut Yuen, Sheung Man |
| contents | In the allocation of indivisible goods, a prominent fairness notion is envy-freeness up to one good (EF1). We initiate the study of reachability problems in fair division by investigating the problem of whether one EF1 allocation can be reached from another EF1 allocation via a sequence of exchanges such that every intermediate allocation is also EF1. We show that two EF1 allocations may not be reachable from each other even in the case of two agents, and deciding their reachability is PSPACE-complete in general. On the other hand, we prove that reachability is guaranteed for two agents with identical or binary utilities as well as for any number of agents with identical binary utilities. We also examine the complexity of deciding whether there is an EF1 exchange sequence that is optimal in the number of exchanges required. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_07241 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Reachability of Fair Allocations via Sequential Exchanges Igarashi, Ayumi Kamiyama, Naoyuki Suksompong, Warut Yuen, Sheung Man Computer Science and Game Theory Computational Complexity In the allocation of indivisible goods, a prominent fairness notion is envy-freeness up to one good (EF1). We initiate the study of reachability problems in fair division by investigating the problem of whether one EF1 allocation can be reached from another EF1 allocation via a sequence of exchanges such that every intermediate allocation is also EF1. We show that two EF1 allocations may not be reachable from each other even in the case of two agents, and deciding their reachability is PSPACE-complete in general. On the other hand, we prove that reachability is guaranteed for two agents with identical or binary utilities as well as for any number of agents with identical binary utilities. We also examine the complexity of deciding whether there is an EF1 exchange sequence that is optimal in the number of exchanges required. |
| title | Reachability of Fair Allocations via Sequential Exchanges |
| topic | Computer Science and Game Theory Computational Complexity |
| url | https://arxiv.org/abs/2312.07241 |