Constant Weighted Maximin Share Approximations for Chores
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912634668843008 |
|---|---|
| author | Li, Bo Wang, Fangxiao Xing, Shiji |
| author_facet | Li, Bo Wang, Fangxiao Xing, Shiji |
| contents | We study the fair allocation of indivisible chores among agents with asymmetric weights. Among the various fairness notions, weighted maximin share (WMMS) stands out as particularly compelling. However, whether WMMS admits a constant-factor approximation has remained unknown and is one of the important open problems in weighted fair division [ALMW22, Suk25]. So far, the best known approximation ratio is O(log n), where n is the number of agents. In this paper, we advance the state of the art and present the first constant-factor approximate WMMS algorithm. To this end, we introduce canonical instance reductions and different bounds of agents' valuations. We also prove that guaranteeing better than 2-approximation is not possible, which improves the best-known lower bound of 1.366. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_06581 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Constant Weighted Maximin Share Approximations for Chores Li, Bo Wang, Fangxiao Xing, Shiji Computer Science and Game Theory We study the fair allocation of indivisible chores among agents with asymmetric weights. Among the various fairness notions, weighted maximin share (WMMS) stands out as particularly compelling. However, whether WMMS admits a constant-factor approximation has remained unknown and is one of the important open problems in weighted fair division [ALMW22, Suk25]. So far, the best known approximation ratio is O(log n), where n is the number of agents. In this paper, we advance the state of the art and present the first constant-factor approximate WMMS algorithm. To this end, we introduce canonical instance reductions and different bounds of agents' valuations. We also prove that guaranteeing better than 2-approximation is not possible, which improves the best-known lower bound of 1.366. |
| title | Constant Weighted Maximin Share Approximations for Chores |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2510.06581 |