Fair Division with Two-Sided Preferences
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910575334785024 |
|---|---|
| author | Igarashi, Ayumi Kawase, Yasushi Suksompong, Warut Sumita, Hanna |
| author_facet | Igarashi, Ayumi Kawase, Yasushi Suksompong, Warut Sumita, Hanna |
| contents | We study a fair division setting in which participants are to be fairly distributed among teams, where not only do the teams have preferences over the participants as in the canonical fair division setting, but the participants also have preferences over the teams. We focus on guaranteeing envy-freeness up to one participant (EF1) for the teams together with a stability condition for both sides. We show that an allocation satisfying EF1, swap stability, and individual stability always exists and can be computed in polynomial time, even when teams may have positive or negative values for participants. When teams have nonnegative values for participants, we prove that an EF1 and Pareto optimal allocation exists and, if the valuations are binary, can be found in polynomial time. We also show that an EF1 and justified envy-free allocation does not necessarily exist, and deciding whether such an allocation exists is computationally difficult. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2206_05879 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Fair Division with Two-Sided Preferences Igarashi, Ayumi Kawase, Yasushi Suksompong, Warut Sumita, Hanna Computer Science and Game Theory Theoretical Economics We study a fair division setting in which participants are to be fairly distributed among teams, where not only do the teams have preferences over the participants as in the canonical fair division setting, but the participants also have preferences over the teams. We focus on guaranteeing envy-freeness up to one participant (EF1) for the teams together with a stability condition for both sides. We show that an allocation satisfying EF1, swap stability, and individual stability always exists and can be computed in polynomial time, even when teams may have positive or negative values for participants. When teams have nonnegative values for participants, we prove that an EF1 and Pareto optimal allocation exists and, if the valuations are binary, can be found in polynomial time. We also show that an EF1 and justified envy-free allocation does not necessarily exist, and deciding whether such an allocation exists is computationally difficult. |
| title | Fair Division with Two-Sided Preferences |
| topic | Computer Science and Game Theory Theoretical Economics |
| url | https://arxiv.org/abs/2206.05879 |