Dividing a Graphical Cake

Xiaohui Bei, Warut SuksompongAAAI 2021 · DOI

Introduction

In fair division theory, the "cake-cutting" problem serves as a fundamental metaphor for partitioning a heterogeneous, divisible resource among agents with varying preferences. Traditionally, this "cake" is modeled as a one-dimensional line segment $[0, 1]$. Protocols like the Dubins-Spanier "moving-knife" ensure that each of $n$ agents receives a single connected piece valued at least $1/n$ of the total.

However, real-world resources—such as road networks, fiber-optic systems, or power grids—are rarely linear. When these resources are modeled as graphs, a "connected" piece on a flattened line might translate to a disjointed set of edges on the actual network. This research addresses the challenge of fair division when the resource is an undirected graph and agents require their allocated piece to be a connected subgraph.

Methodology: From Graphs to Trees

To extend standard protocols to complex topologies, the authors introduce a cycle-removing operation. This technique transforms any graph into a tree by "splitting" vertices or edges involved in cycles. Because any connected allocation on the resulting tree remains a connected allocation on the original graph, the researchers can simplify the problem by focusing their proofs on tree structures.

The cycle-removing operation splits a vertex (v) to transform a cyclic graph into a tree structure, preserving connectivity properties.

For the specific case of two agents, the authors utilize oriented labeling and bipolar numbering. These graph-theoretic tools define a specific path for a "knife" to traverse the edges, ensuring that the portion cut off remains connected throughout the process.

Key Insights: The Connectivity Penalty

The transition from a 1D line to a graph introduces a "connectivity penalty." While proportionality ($1/n$) is always achievable on a line, the topology of a graph can restrict fair outcomes. The "worst-case" scenario is identified as the star graph, where multiple edges radiate from a single central vertex.

A star graph represents the worst-case topology for fair division, where the central bottleneck limits the value that can be partitioned into connected pieces.

For two agents, the ability to achieve a perfect $1/2$ split depends on whether the graph is "almost bridgeless" (i.e., adding one edge makes it 2-edge-connected). If this property is absent, the guarantee drops to $1/3$.

Key Results and Guarantees

The paper establishes several tight bounds for graphical cake-cutting:

  • General Guarantee: For $n$ agents on any graph, there exists a connected allocation where every agent receives at least $1/(2n-1)$ of the total value. This bound is mathematically tight, as demonstrated by star graphs with $2n-1$ edges.
  • Multi-piece Allocation: If agents are permitted to receive a small number of disconnected components (e.g., $k+1$ connected pieces), the fairness guarantee improves significantly to $1/2 - 1/(2 \cdot 3^k)$ for two agents.
  • Chore Division: When dividing "chores" (negative-value resources like maintenance costs), the authors prove that for $n \le 5$ agents, no one needs to incur more than $2/(n+1)$ of the total cost.

Limitations and Future Work

While this work provides strong foundations for proportionality and egalitarian welfare, envy-freeness—where no agent prefers another's bundle—remains an open challenge for more than two agents in graphical settings. Future research may also explore whether specific graph classes, such as planar graphs or grids, allow for better guarantees than the general $1/(2n-1)$ bound, or investigate "mixed manna" scenarios involving both goods and burdens.

Summary updated

BibTeX
@inproceedings{bei2021dividing,
  author = {Xiaohui Bei and Warut Suksompong},
  title = {{Dividing a Graphical Cake}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i6.16652},
}
Figure