Metraipolis › archive › dc_dce2056ea83f
Revisiting EFX and fPO Allocations for Binary Chores — arXiv:2609.13970
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.13970
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-15T23:48:25.553Z
- SHA-256 of the archived text
806a379a06f1a2e6ad14edb3db798b9bbaf99217dee206e4a5222df70c776431- Stable URL of this page
https://metraipolis.com/documento/dc_dce2056ea83f
How to cite
Revisiting EFX and fPO Allocations for Binary Chores — arXiv:2609.13970 — arXiv (en), https://arxiv.org/abs/2609.13970 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_dce2056ea83f (Metraipolis archive dc_dce2056ea83f, sha256 806a379a06f1a2e6ad14edb3db798b9bbaf99217dee206e4a5222df70c776431)
BibTeX
@misc{dcdce2056ea83f,
title = {Revisiting EFX and fPO Allocations for Binary Chores — arXiv:2609.13970},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.13970},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_dce2056ea83f; sha256 806a379a06f1a2e6ad14edb3db798b9bbaf99217dee206e4a5222df70c776431},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.13970. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study fair and efficient allocations of indivisible chores under binary additive costs, with a focus on unequal entitlements and best-of-both-worlds guarantees. While binary valuations have been extensively studied for goods, their chore counterpart remains much less understood. A notable exception is due to Tao et al. (TCS 2025), who established that EFX and fPO are compatible for binary chores with equal entitlements. We revisit binary chores under unequal entitlements and establish the computation of allocations that satisfy WEFX and fPO. Our key technical contribution is a new lexicographic potential function tailored to chores: any allocation minimizing this potential ensures both WEFX and fPO. This potential further guides a polynomial-time local-search algorithm for computing allocations with such fairness and efficiency guarantees. For best-of-both-worlds guarantees, we show that unequal entitlements create a sharp obstruction: even with two agents and identical binary additive costs, no lottery can simultaneously satisfy ex-ante WEF and ex-post WEF1. In contrast, for equal entitlements, we construct in polynomial time a lottery that is ex-ante EF and fPO, while every realization is both EFX and fPO. Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-15 in cs.GT). Categorie arXiv: Computer Science and Game Theory (cs.GT). Pagina del lavoro: https://arxiv.org/abs/2609.13970 — 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-10-15T23:17:52.827Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-15?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).