Fair Assignment of Indivisible Chores to Asymmetric Agents
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911206341607424 |
|---|---|
| author | Seddighin, Masoud Seddighin, Saeed |
| author_facet | Seddighin, Masoud Seddighin, Saeed |
| contents | We consider the problem of assigning indivisible chores to agents with different entitlements in the maximin share value (\MMS) context. While constant-\MMS\ allocations/assignments are guaranteed to exist for both goods and chores in the symmetric setting, the situation becomes much more complex when agents have different entitlements. For the allocation of indivisible goods, it has been proven that an $n$-\WMMS\ (weighted \MMS) guarantee is the best one can hope for. For indivisible chores, however, it was recently discovered that an $O(\log n)$-\WMMS\ assignment is guaranteed to exist. In this work, we improve this upper bound to a constant-\WMMS\ guarantee.\footnote{We prove the existence of a 20-\WMMS\ assignment, but we did not attempt to optimize the constant factor. We believe our methods already yield a slightly better bound with a tighter analysis.} |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_10698 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fair Assignment of Indivisible Chores to Asymmetric Agents Seddighin, Masoud Seddighin, Saeed Computer Science and Game Theory We consider the problem of assigning indivisible chores to agents with different entitlements in the maximin share value (\MMS) context. While constant-\MMS\ allocations/assignments are guaranteed to exist for both goods and chores in the symmetric setting, the situation becomes much more complex when agents have different entitlements. For the allocation of indivisible goods, it has been proven that an $n$-\WMMS\ (weighted \MMS) guarantee is the best one can hope for. For indivisible chores, however, it was recently discovered that an $O(\log n)$-\WMMS\ assignment is guaranteed to exist. In this work, we improve this upper bound to a constant-\WMMS\ guarantee.\footnote{We prove the existence of a 20-\WMMS\ assignment, but we did not attempt to optimize the constant factor. We believe our methods already yield a slightly better bound with a tighter analysis.} |
| title | Fair Assignment of Indivisible Chores to Asymmetric Agents |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2510.10698 |