In classic fair division problems—such as dividing a continuous "cake" or allocating a set of discrete items—we typically assume the resource can be partitioned along a simple, one-dimensional line. On a line, boundaries slide smoothly, and we can easily guarantee properties like envy-freeness (where no agent prefers another's bundle).
However, real-world resources are rarely linear. Road networks, utility grids, and structurally dependent tasks are inherently graph-structured. When we introduce the constraint that allocations must respect this underlying network topology, the mathematical landscape changes completely. Recent research reveals that the transition from a one-dimensional line to a complex graph introduces severe topological obstructions that can cause standard fairness guarantees to collapse.
The Constraint of Connected Bundles
The most intuitive way to map fair division to a graph is to treat the vertices as items and require that each agent receives a connected subgraph. Imagine dividing a network of land plots or a set of contiguous time slots; giving an agent a fragmented, disconnected bundle is often useless.
On a simple path graph, this constraint is manageable. Bilò et al. (2019) demonstrated that for items arranged in a line, an allocation that is Envy-Free up to One item (EF1) is always guaranteed to exist for up to four agents. The intuition here mirrors the 1D continuous case: you can move partition boundaries along the path to balance valuations.
Path Graph (Easy to balance):
( Item A ) --- ( Item B ) --- ( Item C ) --- ( Item D )
But as soon as the graph branches, this geometric freedom vanishes. Deligkas et al. (2021) showed that even on basic star graphs, finding connected fair allocations becomes computationally daunting. The presence of a central "hub" vertex means that whoever receives the hub might instantly become the target of intense envy, yet removing the hub disconnects the remaining items for everyone else.
To understand exactly why certain networks resist fair division, Chen et al. (2024) investigated structural bottlenecks like vertex cutsets and non-traceable graphs (graphs without a Hamiltonian path). They discovered that traditional connectivity gaps are not the only culprits; some graphs lack obvious bottlenecks but still possess subtle topological properties that inherently block equitable distribution.
Continuous Graphical Cakes
A parallel challenge arises when the resource is continuous but structured as a network, such as dividing a highway system or a fiber-optic grid among different jurisdictions. This is known as graphical cake cutting, where the resource to be divided lies along the edges of an undirected graph.
In standard cake cutting, proportionality (getting at least $1/n$ of the total value) and envy-freeness are closely linked. On graphs, they decouple. Bei and Suksompong (2021) and Suksompong et al. (2025) established that while we can guarantee every agent a connected piece worth at least $1/(2n-1)$ of the total value, achieving true envy-freeness is a much steeper hurdle.
The core issue is that agents have non-identical valuations over different parts of the network. As Yuen and Suksompong (2023) point out, approximation algorithms that successfully bound envy on simple star graphs fail to generalize to arbitrary networks. On a complex graph, you cannot easily shift a boundary to appease an envious neighbor without simultaneously altering the connectivity and value of another agent's share.
Envy Cycles and Graph Orientations
Perhaps the clearest view of how topology obstructs fairness comes from a different framing: treating the edges of a graph as indivisible items and the vertices as the agents. In this setup, an item (edge) can only be allocated to one of the two agents (vertices) it connects. This maps the fair division problem directly onto graph orientation, where assigning an edge to a vertex is equivalent to directing the edge toward that vertex.
Graph Orientation as Allocation:
( Agent 1 ) <====== Item (Edge) ======> ( Agent 2 )
In this domain, the primary barrier to fairness is the propagation of envy cycles. If Agent A envies Agent B's items, Agent B envies Agent C, and Agent C envies Agent A, the allocation is inherently unstable.
The structural properties of the graph dictate whether these cycles can be avoided. Afshinmehr et al. (2024) and Sotiriou (2025) demonstrated that Envy-Free up to any good (EFX) allocations are guaranteed to exist on bipartite multi-graphs. The intuition is elegant: bipartite graphs inherently lack odd cycles. Without odd cycles, the network restricts how envy can propagate, allowing algorithms to strategically assign items without creating unresolvable loops.
When a graph is dense and contains short odd cycles, this guarantee shatters. Zeng and Mehta (2025) formalized this boundary by linking fairness directly to a fundamental topological invariant: the chromatic number ($\chi(G)$).
The authors proved a sharp threshold for fairness:
- Graphs with $\chi(G) \le 2$ (bipartite graphs) are always strongly EFX orientable, meaning a fair allocation exists regardless of how agents value the items.
- Graphs with $\chi(G) \ge 3$ introduce topological obstructions (odd cycles) that allow envy to propagate in unresolvable loops, meaning universal fairness guarantees are mathematically impossible.
By shifting the focus from global preference profiles to local graph properties like chromatic numbers, cutsets, and cycle lengths, this body of work exposes the deep truth of graphical fair division: the geometry of the network itself sets the ultimate limits of economic fairness.
Key Foundational Work
Almost envy-free allocations with connected bundles (2019) — contributed 2 concept elements to this direction.
Dividing a Graphical Cake (2021) — contributed 1 concept elements to this direction.
The Parameterized Complexity of Connected Fair Division (2021) — contributed 1 concept elements to this direction.