Metraipolis › archive › dc_43ee08d562a5

Online Fair Division of Chores with Upgrade Recourse — arXiv:2611.00432

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.00432
License (as archived)
CC0-1.0
Archived
2026-11-03T11:04:47.248Z
SHA-256 of the archived text
05dc063b0c69089dee167108728235e0f723091467ebcab25c40c8246edcb3dd
Stable URL of this page
https://metraipolis.com/documento/dc_43ee08d562a5

How to cite

Online Fair Division of Chores with Upgrade Recourse — arXiv:2611.00432 — arXiv (en), https://arxiv.org/abs/2611.00432 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_43ee08d562a5 (Metraipolis archive dc_43ee08d562a5, sha256 05dc063b0c69089dee167108728235e0f723091467ebcab25c40c8246edcb3dd)
BibTeX
@misc{dc43ee08d562a5,
  title = {Online Fair Division of Chores with Upgrade Recourse — arXiv:2611.00432},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.00432},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_43ee08d562a5; sha256 05dc063b0c69089dee167108728235e0f723091467ebcab25c40c8246edcb3dd},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.00432. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We study the online fair division of indivisible chores among $n$ agents under upgrade recourse, where earlier assignments may be revised but each chore previously assigned to an agent must be replaced by a distinct chore that she finds no more costly. We show that a simple adaptation of round robin maintains envy-freeness up to one chore (EF1) together with a $(2-1/n)$-approximation of the maximin share (MMS), and that no deterministic algorithm without predictions can do better, even when all agents rank the chores in the same order. This stands in contrast to the allocation of goods, where the optimal MMS factor vanishes as $n$ grows and cannot be achieved together with EF1. Moreover, knowing only the number of chores modulo a period of length $O(n)$ (and nothing about the costs) suffices to improve upon this factor at the final configuration, while the same algorithm retains a factor below $3$ even if this information is wrong. On the other hand, envy-freeness up to any chore (EFX) essentially requires the exact number of chores: uncertainty between two consecutive values already rules out every finite approximation, and even exact knowledge does not allow EFX to be combined with an MMS guarantee better than the trivial factor of $n$.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.AI, nuovi lavori del giorno).
Categorie arXiv: Computer Science and Game Theory (cs.GT) ; Artificial Intelligence (cs.AI).
Pagina del lavoro: https://arxiv.org/abs/2611.00432 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T10:59:45.944Z dalla pagina https://arxiv.org/list/cs.AI/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).