EF1 for Mixed Manna with Unequal Entitlements
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909352882864128 |
|---|---|
| author | Garg, Jugal Sharma, Eklavya |
| author_facet | Garg, Jugal Sharma, Eklavya |
| contents | We study fair division of indivisible mixed manna when agents have unequal entitlements, with weighted envy-freeness up to one item (WEF1) as our primary notion of fairness. We identify several shortcomings of existing techniques to achieve WEF1. Hence, we relax WEF1 to weighted envy-freeness up to 1 transfer (WEF1T), and give a polynomial-time algorithm for achieving it. We also generalize Fisher markets to the mixed manna setting, and use them to get a polynomial-time algorithm for two agents that outputs a WEF1 allocation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_12966 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | EF1 for Mixed Manna with Unequal Entitlements Garg, Jugal Sharma, Eklavya Computer Science and Game Theory We study fair division of indivisible mixed manna when agents have unequal entitlements, with weighted envy-freeness up to one item (WEF1) as our primary notion of fairness. We identify several shortcomings of existing techniques to achieve WEF1. Hence, we relax WEF1 to weighted envy-freeness up to 1 transfer (WEF1T), and give a polynomial-time algorithm for achieving it. We also generalize Fisher markets to the mixed manna setting, and use them to get a polynomial-time algorithm for two agents that outputs a WEF1 allocation. |
| title | EF1 for Mixed Manna with Unequal Entitlements |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2410.12966 |