Metraipolis › archive › dc_7410f71203fb
Balanced Fair Division and Generalized Kneser Graphs — arXiv:2611.04486
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.04486
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-04T18:48:17.247Z
- SHA-256 of the archived text
f215394dcc358ab5f01c69421194261bfcf5f7376d7380f2c21982ffd7e02dd1- Stable URL of this page
https://metraipolis.com/documento/dc_7410f71203fb
How to cite
Balanced Fair Division and Generalized Kneser Graphs — arXiv:2611.04486 — arXiv (en), https://arxiv.org/abs/2611.04486 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7410f71203fb (Metraipolis archive dc_7410f71203fb, sha256 f215394dcc358ab5f01c69421194261bfcf5f7376d7380f2c21982ffd7e02dd1)
BibTeX
@misc{dc7410f71203fb,
title = {Balanced Fair Division and Generalized Kneser Graphs — arXiv:2611.04486},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.04486},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7410f71203fb; sha256 f215394dcc358ab5f01c69421194261bfcf5f7376d7380f2c21982ffd7e02dd1},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.04486. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study indivisible goods allocated to two prescribed nonempty groups whose members have arbitrary monotone valuations. We guarantee balanced envy-freeness up to one good (EF1) for at most five agents and up to two goods (EF2) for at most nine, for any number of goods. Bundle sizes differ by at most one. The EF1 threshold is sharp: every split of six agents can fail. EF2 improves the previous five-agent guarantee. Via the connection of Kyropoulou, Suksompong, and Voudouris, these guarantees follow from chromatic bounds for $\mathrm{KG}(2n,n,r)$, whose vertices are $n$-subsets of a $2n$-set, adjacent when their intersection has size less than $r$. We prove its chromatic number is six for $r=2$, $n\ge2$, resolving Jafari and Alipour's conjecture, and at least ten for $r=3$, $n\ge4$, improving the previous lower bound of six; the known upper bound is fourteen. We show that the standard box-complex $\mathbb{Z}_2$-index bound yields exactly five and nine for $n\ge3$ and $n\ge5$, respectively. To exceed these bounds, we exploit restrictions on maps induced by colorings: a proper five- or nine-coloring must induce a nonzero homology map, yet local constraints force all generators, supported on pentagon or rook configurations, to map to zero. The ten-color proof compares integral and fractional common centers using a sharp rounding theorem for five subset constraints. A linear-time retraction from the full allocation graph onto balanced layers adds cardinality balance to known nonlinear discrepancy guarantees. For each fixed removal allowance in the guaranteed-existence range, finding a balanced fair allocation or an explicit monotonicity violation from valuation circuits is polynomial-time equivalent to finding a monochromatic edge in a circuit-specified coloring of the corresponding graph. The reverse reduction produces normalized monotone binary valuations using ordinary circuits.
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.04486 — 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-04T18:34:07.149Z dalla pagina https://arxiv.org/list/cs.GT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).