Metraipolis › archive › dc_8de64f2d40cd
Fair Division of Graphs: Beyond Traceability — arXiv:2608.29902
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.29902
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-17T08:19:26.651Z
- SHA-256 of the archived text
99255c0ec46f554184ec99e5dc9d98d68e243c3f9d4daa1150dbeaf55d2af2a3- Stable URL of this page
https://metraipolis.com/documento/dc_8de64f2d40cd
How to cite
Fair Division of Graphs: Beyond Traceability — arXiv:2608.29902 — arXiv (en), https://arxiv.org/abs/2608.29902 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_8de64f2d40cd (Metraipolis archive dc_8de64f2d40cd, sha256 99255c0ec46f554184ec99e5dc9d98d68e243c3f9d4daa1150dbeaf55d2af2a3)
BibTeX
@misc{dc8de64f2d40cd,
title = {Fair Division of Graphs: Beyond Traceability — arXiv:2608.29902},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.29902},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_8de64f2d40cd; sha256 99255c0ec46f554184ec99e5dc9d98d68e243c3f9d4daa1150dbeaf55d2af2a3},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.29902. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In this paper, we study fair division problems in which resources are structured as graphs and agents must receive connected bundles. This connectivity requirement fundamentally alters the problem, making it significantly more challenging than its classical counterpart. We focus on the fairness notion of $\mathrm{EF1}_{\mathrm{outer}}$, where envy can be eliminated by removing at most one vertex whose deletion does not disconnect the bundle -- a critical constraint for applications such as land division and network allocation. Our first result extends prior work by establishing the existence of $\mathrm{EF1}_{\mathrm{outer}}$ allocations for an infinite family of non-traceable graphs (that is, graphs that do not admit a Hamiltonian path), answering a central open question and generalizing Bilò et al.'s result for traceable graphs. We then make progress on a conjecture concerning the $\mathrm{EF1}_{\mathrm{outer}}$ spectrum of trees due to Chen and Zwicker. Finally, we complement our structural results with algorithmic insights, showing that deciding the existence of an $\mathrm{EF1}_{\mathrm{outer}}$ allocation is NP-complete even for binary additive valuations, thereby resolving an open complexity question. Taken together, our results deepen the connection between graph theory and fair division, and offer new tools for studying fairness in structured resource environments.
Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-01 in cs.GT).
Categorie arXiv: Computer Science and Game Theory (cs.GT) ; Discrete Mathematics (cs.DM); Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2608.29902 — 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-17T08:08:10.908Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).