Metraipolis › archive › dc_76544ecaa2eb

Non-Existence of EFX Chore Allocations for Monotone Cost Functions with Binary Marginals — arXiv:2608.10572

Source: arXiv (en)
Original: https://arxiv.org/abs/2608.10572
License (as archived): CC0-1.0
Archived: 2026-10-19T06:15:06.611Z
SHA-256 of the archived text: 75ab65c03e324c51c8d40b8afb529509299f253ddd76d9922ac755145072c789
Stable URL of this page: https://metraipolis.com/documento/dc_76544ecaa2eb

How to cite

Non-Existence of EFX Chore Allocations for Monotone Cost Functions with Binary Marginals — arXiv:2608.10572 — arXiv (en), https://arxiv.org/abs/2608.10572 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_76544ecaa2eb (Metraipolis archive dc_76544ecaa2eb, sha256 75ab65c03e324c51c8d40b8afb529509299f253ddd76d9922ac755145072c789)

BibTeX

@misc{dc76544ecaa2eb,
  title = {Non-Existence of EFX Chore Allocations for Monotone Cost Functions with Binary Marginals — arXiv:2608.10572},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.10572},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_76544ecaa2eb; sha256 75ab65c03e324c51c8d40b8afb529509299f253ddd76d9922ac755145072c789},
  year = {2026}
}

Archived text

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

We study the existence of envy-free up to any item (EFX) allocations of indivisible chores when agents have monotone cost functions with binary marginals. For indivisible goods, the corresponding existence question is known to have an affirmative answer for general monotone functions with binary marginals. For chores, however, the existence of EFX allocation was previously known only for more restricted classes, while the general binary-marginal case remained unresolved. In this paper, we provide two counterexamples based on the same 18-agent, 53-chore word gadget, with one cost profile for binary XOS costs and another for binary supermodular costs. In both cases, a complete EFX allocation need not exist. Finally, we formalize and verify our main results in Lean 4.

Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-08-12 in cs.GT).
Categorie arXiv: Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2608.10572 — 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-19T06:10:07.747Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-08-12?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).