Metraipolis › archive › dc_4dbd89dae6bf

Polynomial-Time Approximate EFX for Chores via Flow and Matching — arXiv:2611.07468

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.07468
License (as archived)
CC0-1.0
Archived
2026-11-06T14:43:40.614Z
SHA-256 of the archived text
c378245fbab1546956343fd866e0380c930386068dae5d9971be1a0bc9eef65a
Stable URL of this page
https://metraipolis.com/documento/dc_4dbd89dae6bf

How to cite

Polynomial-Time Approximate EFX for Chores via Flow and Matching — arXiv:2611.07468 — arXiv (en), https://arxiv.org/abs/2611.07468 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_4dbd89dae6bf (Metraipolis archive dc_4dbd89dae6bf, sha256 c378245fbab1546956343fd866e0380c930386068dae5d9971be1a0bc9eef65a)
BibTeX
@misc{dc4dbd89dae6bf,
  title = {Polynomial-Time Approximate EFX for Chores via Flow and Matching — arXiv:2611.07468},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.07468},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_4dbd89dae6bf; sha256 c378245fbab1546956343fd866e0380c930386068dae5d9971be1a0bc9eef65a},
  year = {2026}
}

Archived text

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

We study approximate EFX allocations of indivisible chores under nonnegative additive costs. Exact EFX allocations need not exist in general. We develop a polynomial-time algorithm that computes a complete $(3+\varepsilon)$-EFX allocation for any rational $0<\varepsilon\leq1$, improving the previous approximation guarantee from a factor depending on the number of agents to a constant. The algorithm extends to EF$k$X, achieving a $(2+1/k+\varepsilon)$-approximation for every integer $k\geq1$. For instances with relatively few chores, the polynomial-time BRBI algorithm gives stronger guarantees. It finds exact EF$k$X allocations when $m\leq2kn$ and achieves a factor of at most $2-1/k$ when $m\le(3k-1)n$. In particular, $k=1$ and $m\leq2n$ give exact EFX. We further show that the approximation factor \(2+1/k\) is asymptotically tight for our main algorithm. We also construct a four-agent, ten-chore instance in which every complete allocation has EFX approximation factor at least $11/10$, improving upon the $20/19$ lower bound for submodular costs even under additive costs.

Tema degli esploratori: economia dei servizi IA (elenco arXiv cs.GT, nuovi lavori del giorno).
Categorie arXiv: Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2611.07468 — 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-06T14:20:12.601Z dalla pagina https://arxiv.org/list/cs.GT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).