Source-linked AI summary
Fair Division of Graphs: Beyond Traceability
Nicolas Bousquet, Frank Connor, Agnès Totschnig, Sébastien Zeitoun
TL;DR
The paper studies connected fair division on graphs under EF1_outer, motivated by applications where allocated bundles must remain connected. It establishes guarantees beyond traceable graphs, characterizes the binary-valuation tree spectrum, and proves NP-completeness for deciding allocation existence.
Problem
Connected bundle requirements motivate fair division on graphs, where EF1_outer permits removing one item only if the envied bundle remains connected.
Method
The paper combines structural analysis using bad sets, bottom-up dynamic programming for trees, and complexity reductions for restricted graph classes.
Results
An EF1_outer allocation always exists for an infinite family of non-traceable graphs, tree thresholds are characterized for common binary additive valuations, and the decision problem is NP-complete on several structured graph classes.
Takeaways & Limitations
Traceability is not necessary for universal guarantees under common valuations, while extending the results to heterogeneous valuations and beyond trees remains open.
Takeaways & Limitations
Fully characterizing the EF1_outer threshold beyond trees remains an important open question.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper studies EF1_outer fair division on graphs with connected bundles, establishing guarantees beyond traceable graphs, characterizing tree spectra, and proving computational hardness. It also develops bad sets as a structural tool for negative instances and threshold analysis.
- Motivation: EF1_outer requires removing at most one vertex from an envied bundle while preserving that bundle’s connectivity.The graph setting models items as vertices and agents as receiving connected subgraphs.
- Non-traceable graphs: An infinite family of non-traceable graphs always admits EF1_outer allocations for common monotone valuation functions.The construction uses valuation-dependent vertex orderings in graphs that are almost traceable and yields a polynomial-time allocation method.
- Tree spectra: For common binary additive valuations on trees, the EF1_outer spectrum follows the conjectured pattern of an initial yes string, a no string, and a final infinite yes string.The result gives the first broad step toward Chen and Zwicker’s conjecture since Igarashi’s work.
- Tree spectra: Bad sets characterize negative instances for prescribed agent counts and support a polynomial-time dynamic program for computing the tree spectrum threshold.A bad set has at least two more incident components than border vertices.
- Tree spectra: For an n-vertex tree with ℓ leaves, the spectrum threshold is at least (1 − C · 1/ℓ)n for common binary additive valuations.This identifies the number of leaves, rather than branching nodes, as the relevant tree parameter.
- Algorithmic results: The Outer Connected Fair Division of Graphs problem is NP-complete for common additive valuations on variants of stars, bounded-bandwidth graphs, and planar graphs.This addresses an open complexity question for deciding whether an EF1_outer allocation exists.
2 Preliminaries
The preliminaries model items as graph vertices and feasible bundles as connected induced subgraphs. Agents have monotone or additive valuations, and allocations partition the vertices into connected bundles subject to EF1_outer.
- Graph and bundles: An instance consists of agents with valuation functions over connected subsets of graph vertices.For X ⊆ V, connectivity means the induced subgraph G[X] is connected.
- Valuations: Monotone valuations do not decrease when a connected bundle is enlarged, while additive valuations sum the values of its vertices.Every additive valuation is monotone.
- Allocations: A connected allocation partitions all vertices into bundles, assigning one connected bundle to each agent.Envy-freeness requires every agent to value their own bundle at least as highly as every other allocated bundle.
- Fairness: EF1_outer holds when each agent’s envy toward another bundle can be removed by deleting one vertex while leaving the other bundle connected.An empty envied bundle satisfies the condition automatically.
- Tree terminology: In a tree, a proper tree is not a path, and an external vertex of a set is a leaf of that set’s minimal containing subtree.Equivalently, at most one component after deleting the vertex contains vertices from the set.
3 Universal Guarantee for Double Suns
Double suns are an infinite family of non-traceable graphs that nevertheless admit EF1outer allocations for every number of agents under common monotone valuations. The construction adapts path-based allocations through a carefully chosen vertex order while preserving connectivity.
- Graph structure: A double sun consists of a clique of size n − 6 with three attached K2,2 structures, yielding six connectors, six tips, and n − 12 core vertices.The clique supplies the core, while each attached pair contributes connectors and neighboring tips.
- Graph structure: Every double sun of size n ≥ 12 lacks a Hamiltonian path.The proof derives three distinct endpoint requirements from the attached structures, contradicting the existence of only two path endpoints.
- Universal guarantee: For every n ≥ 12, every k ∈ {1, . . . , n}, and every common monotone valuation, a double sun admits an EF1outer allocation.This extends the universal guarantee known for graphs with Hamiltonian paths to a non-traceable family.
- Allocation construction: The proof uses a vertex order whose consecutive subsets are connected except for one explicitly handled exceptional set.Although the order is not a Hamiltonian path because of a missing edge, it supports transferring EF1outer allocations from an auxiliary path.
- Allocation construction: For k ≥ 6, the procedure maintains connectivity while assigning vertices according to set priority and cases involving tips, connectors, and core vertices.The proof also establishes that the connector required in Case 1 remains unassigned when selected.
4 Spectrum of Trees with Binary Valuations
For trees under common additive binary valuations, EF1_outer existence is characterized exactly by the maximum size of a graph-theoretic bad set. The proof constructs negative instances from bad sets, positive allocations when sufficiently many agents are present, and a polynomial-time threshold algorithm.
- Graph-theoretic framework: A good component admits an injective matching from every other component to a boundary vertex; a bad set has no such component.These definitions underpin the tree-spectrum characterization.
- Characterization: Theorem 7 gives an EF1_outer allocation for every common additive binary valuation exactly when k ≥ τ(T) + 2.Here τ(T) is the maximum size of a bad set; paths have τ(T) = 0.
- Negative instances: Every nonempty set of branching vertices is bad, with at least two more components than selected vertices, providing the cardinality basis for Lemma 8.The proof removes suitable vertices while preserving badness.
- Negative instances: If a tree contains a bad set of size k, Lemma 9 constructs a binary additive valuation with no EF1_outer allocation for k + 1 agents.Lemma 8 reduces bad-set size, allowing negative instances for every k from 2 through τ(T) + 1.
- Positive allocations: For k ≥ τ(T) + 2, the positive-direction proof partitions zero- and unit-valued vertices into valid subtrees and splits them to obtain exactly k bundles.Each valid subtree contains one unit-valued vertex, or two with at least one a leaf; the resulting allocation is EF1_outer.
- Algorithmic result: The maximum bad-set size, and therefore the binary-valuation threshold, can be computed in polynomial time on trees using bottom-up dynamic programming.The dynamic program computes the quantities needed to determine the largest bad set.
5 Spectrum Threshold on Trees with Many Leaves
The section bounds the tree spectrum threshold by constructing large bad sets from structural features such as terminal vertices and bad caterpillars. For trees with many leaves, disjoint bad 5-caterpillars yield a threshold close to n.
- Theorem 21 gives a lower bound of (1 − C · 1/ℓ)n for the spectrum threshold of every tree with ℓ leaves.
- The proof constructs at least k/30 pairwise vertex-disjoint bad 5-caterpillars, so one has weight at most 30n/k and τ(G) ≥ (1 − 15/k)n − 12.
- A 3-terminal vertex of weight t yields τ(G) ≥ n − t/2 − 3.
- A pair of 2-terminal vertices of weight t yields τ(G) ≥ n − t/2 − 4.
- A 5-bad caterpillar of weight t yields τ ≥ n − t/2 − 10.
6 Algorithmic Aspects
The algorithmic section proves NP-completeness of deciding whether an EF1outer allocation exists, including restricted graph and valuation classes. The reductions encode Partition instances through connected graph constructions whose feasible allocations correspond to partitions.
- The Outer Connected Fair Division of Graphs problem asks whether a graph admits an EF1outer allocation for its agents and valuations.
- Theorem 30 establishes NP-completeness for blow-ups of subdivided stars with common binary additive valuations and for bounded-bandwidth graphs with common additive valuations.
- The problem belongs to NP because every agent pair can be checked by exhaustive search for an outer item whose removal eliminates envy.
- The reduction from Partition uses connected chains, railings, and value-zero vertices so that allocations correspond to partitions of the chains.
- NP-hardness persists for graphs of treewidth and pathwidth 2, bounded treedepth under general additive valuations, and planar graphs.
7 Conclusion and Future Work
The paper resolves open questions about connected EF1outer allocations while identifying remaining gaps beyond the proved valuation and graph classes. Its results establish non-traceable guarantees and characterize tree thresholds for common binary valuations.
- Traceability is not necessary for universal EF1outer guarantees under common valuations, through an infinite family of non-traceable graphs.
- For common binary additive valuations on trees, bad sets characterize the spectrum threshold.
- The threshold beyond binary valuations remains unresolved even for common additive valuations with only two possible vertex values.
- For general graphs, fully characterizing the spectrum threshold remains an open question, although bad sets provide negative instances.
A The case of subdivided claws with all branches of even size
For subdivided claws with even-sized branches, the proof modifies the partitioning step to handle the extra subtree created by the branching node. It then preserves the existing merging and splitting argument.
- When V0 ≠ ∅, the partitioning step creates k subtrees: one size-3 subtree intersecting V0 and k − 1 subtrees of size 2.
- After this modified partitioning, the merging and splitting steps remain exactly the same as in the preceding proof.
- The size-3 subtree is formed on an odd path containing a vertex of V0, while the remaining even paths are partitioned into size-2 subtrees.
- When V0 = ∅, each even branch is partitioned into size-2 subtrees and the branching node is added to one adjacent subtree.
- The resulting allocation has one size-3 subtree and k − 1 size-2 subtrees, with all vertices in V1, and is EF1outer.
B Deferred reduction from Section 6
The paper reduces 3-Partition to Outer Connected Fair Division on blow-ups of subdivided stars with common binary additive valuations. The construction represents partition items as chains attached to a value-bearing clique.
- 3-Partition reduces to Outer Connected Fair Division on blow-ups of subdivided stars with common binary additive valuations.
- The construction starts with a clique of size m whose vertices receive infinite or sufficiently large value.
- Each item in S becomes a chain whose length equals that item's value, with chain vertices valued 1 and endpoint leaves valued 0.
- The illustrated case uses a center clique of size m = 3 and the 3-Partition instance S = {4, 1, 2}.