Best-of-Both-Worlds Fairness of the Envy-Cycle-Elimination Algorithm
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_ | 1866929538175336448 |
|---|---|
| author | Garg, Jugal Sharma, Eklavya |
| author_facet | Garg, Jugal Sharma, Eklavya |
| contents | We consider the problem of fairly dividing indivisible goods among agents with additive valuations. It is known that an Epistemic EFX and $2/3$-MMS allocation can be obtained using the Envy-Cycle-Elimination (ECE) algorithm. In this work, we explore whether this algorithm can be randomized to also ensure ex-ante proportionality. For two agents, we show that a randomized variant of ECE can compute an ex-post EFX and ex-ante envy-free allocation in near-linear time. However, for three agents, we show that several natural randomization methods for ECE fail to achieve ex-ante proportionality. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_08986 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Best-of-Both-Worlds Fairness of the Envy-Cycle-Elimination Algorithm Garg, Jugal Sharma, Eklavya Computer Science and Game Theory We consider the problem of fairly dividing indivisible goods among agents with additive valuations. It is known that an Epistemic EFX and $2/3$-MMS allocation can be obtained using the Envy-Cycle-Elimination (ECE) algorithm. In this work, we explore whether this algorithm can be randomized to also ensure ex-ante proportionality. For two agents, we show that a randomized variant of ECE can compute an ex-post EFX and ex-ante envy-free allocation in near-linear time. However, for three agents, we show that several natural randomization methods for ECE fail to achieve ex-ante proportionality. |
| title | Best-of-Both-Worlds Fairness of the Envy-Cycle-Elimination Algorithm |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2410.08986 |