Metraipolis › archive › dc_2ecff405e905

Comparison-Based Fair Division of Indivisible Chores — arXiv:2609.08687

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.08687
License (as archived): CC0-1.0
Archived: 2026-10-16T13:32:14.985Z
SHA-256 of the archived text: 3bdb7a5081e2cc0a290844d6372707f463c88ecd6d4caf546aaf2df4a4f1baff
Stable URL of this page: https://metraipolis.com/documento/dc_2ecff405e905

How to cite

Comparison-Based Fair Division of Indivisible Chores — arXiv:2609.08687 — arXiv (en), https://arxiv.org/abs/2609.08687 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2ecff405e905 (Metraipolis archive dc_2ecff405e905, sha256 3bdb7a5081e2cc0a290844d6372707f463c88ecd6d4caf546aaf2df4a4f1baff)

BibTeX

@misc{dc2ecff405e905,
  title = {Comparison-Based Fair Division of Indivisible Chores — arXiv:2609.08687},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.08687},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2ecff405e905; sha256 3bdb7a5081e2cc0a290844d6372707f463c88ecd6d4caf546aaf2df4a4f1baff},
  year = {2026}
}

Archived text

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

We investigate the query complexity of fairly allocating $m$ indivisible chores among $n$ agents with additive cost functions. We depart from the standard cardinal model and assume only comparison access: an algorithm may ask an agent which of two bundles is less costly, but never observes numerical costs. Our first results concern proportionality up to one item (PROP1). We design comparison-based algorithms that compute PROP1 allocations using $O(n^3\log m)$ comparison queries. When the chores are arranged in a fixed order and allocations are required to be contiguous, we compute a contiguous PROP1 allocation using $O(n^3 \log^2 m)$ comparison queries. Our main result concerns the maximin share (MMS) guarantee. We show that for any fixed number of agents $n$ and constant $\varepsilon>0$, a $\left(13/11 +\varepsilon\right)$-MMS allocation can be computed with a comparison complexity logarithmic in $m$. Remarkably, comparison access suffices to match the state-of-the-art $13/11$ cardinal-access guarantee of Huang and Segal-Halevi up to an arbitrarily small loss. Furthermore, our result implies that the MMS distortion of comparison access (i.e., the worst-case multiplicative loss in MMS fairness incurred by observing only comparisons rather than numerical costs) is at most $13/11$. Finally, we show that, for three agents, an allocation satisfying envy-freeness up to one item (EF1) can be computed using $O(\log m)$ comparison queries.

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