Fair Division of Graphs: Beyond Traceability
Abstract
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 EF1outer, 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 EF1outer 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 EF1outer spectrum of trees due to Chen and Zwicker. Finally, we complement our structural results with algorithmic insights, showing that deciding the existence of an EF1outer 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.
Related
- An improved upper bound for the fair domination number of maximal outerplanar graphs
- Corrigendum to "On the Maximum Symmetric Division Deg Index of k-Cyclic Graphs [J. Math. 2022, (2022) \#7783128]"
- Maximum degree for random geometric graphs in the connectivity regime and beyond
- Conditions for traceability under a bound on the size of even-distance sets
- Causal Discovery beyond Conditional Independence: Identifiability, Algorithms, and Statistical Inference for Directed Acyclic and Cyclic Graphs
BibTeX
@misc{bousquet2026fair,
title = {{Fair Division of Graphs: Beyond Traceability}},
author = {Nicolas Bousquet and Frank Connor and Agnès Totschnig and Sébastien Zeitoun},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.29902},
eprint = {2608.29902},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.29902},
}
RIS
TY - UNPB
TI - Fair Division of Graphs: Beyond Traceability
AU - Nicolas Bousquet
AU - Frank Connor
AU - Agnès Totschnig
AU - Sébastien Zeitoun
PY - 2026
DA - 2026/08/30
PB - arXiv
DO - 10.48550/arxiv.2608.29902
UR - https://arxiv.org/abs/2608.29902
AB - 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 EF1_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 EF1_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 EF1_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 EF1_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.
ER -