Abstract: We study the paradigmatic fair division problem of allocating a divisible good among agents with heterogeneous preferences, commonly known as cake cutting. Classical cake cutting protocols are susceptible to manipulation. Do their strategic outcomes still guarantee fairness? To address this question we adopt a novel algorithmic approach, by designing a concrete computational framework for fair division—the class of Generalized Cut and Choose (GCC) protocols—and reasoning about the game-theoretic properties of algorithms that operate in this model. The class of GCC protocols includes the most important discrete cake cutting protocols, and turns out to be compatible with the study of fair division among strategic agents. In particular, GCC protocols are guaranteed to have approximate subgame perfect Nash equilibria, or even exact equilibria if the protocol's tie-breaking rule is flexible. We further observe that the (approximate) equilibria of proportional GCC protocols—which guarantee each of the $n$ agents a $1/n$-fraction of the cake—must be (approximately) proportional. Finally, we design a protocol in this framework with the property that its Nash equilibrium allocations coincide with the set of (contiguous) envy-free allocations.
Introduction
In the classic "cake cutting" problem, a divisible resource must be partitioned among $n$ agents with heterogeneous preferences. While numerous protocols have been developed to ensure fair outcomes—such as proportionality (each agent receives at least $1/n$ of their subjective value) or envy-freeness (no agent prefers another's piece)—these protocols typically assume that agents follow the rules honestly.
In reality, agents are strategic. If an agent knows the preferences of others, they may deviate from the protocol's instructions to secure a more valuable piece. This raises a fundamental question in algorithmic game theory: do the fairness guarantees of classic protocols survive strategic manipulation? This research addresses this by introducing a formal computational framework to analyze the equilibria of cake-cutting games.
The Generalized Cut and Choose (GCC) Framework
To analyze a wide class of protocols systematically, the authors introduce Generalized Cut and Choose (GCC) protocols. A GCC protocol is modeled as a decision tree where each node represents an action by an agent:
- Cut Nodes: An agent is instructed to place a mark between two existing points on the cake.
- Choose Nodes: An agent selects a piece from a set of already demarcated segments.
- If-Else Logic: The protocol’s path is determined by the relative ordering of the cuts made by agents.
This framework is highly expressive, capturing nearly all classic discrete protocols, including Dubins-Spanier, Selfridge-Conway, and Even-Paz. By representing these protocols as extensive-form games of perfect information, the authors can rigorously evaluate how strategic behavior influences the final allocation.
Existence of Equilibria
Analyzing equilibria in cake cutting is challenging because the strategy space—where to place a cut—is continuous and infinite. The authors overcome this using two primary methods:
- Discretization for $\epsilon$-SPNE: By breaking the cake into tiny "cells," the authors prove that every GCC protocol possesses an approximate subgame perfect Nash equilibrium ($\epsilon$-SPNE) for any $\epsilon > 0$.
- Informed Tie-Breaking for Exact SPNE: To prove the existence of exact equilibria, the authors introduce "informed tie-breaking" rules. These rules allow the protocol to handle cases where two agents cut at the exact same location by considering the history of play. Under these conditions, every GCC protocol is guaranteed to have an exact subgame perfect Nash equilibrium.
Does Strategy Preserve Fairness?
One of the paper's most significant findings is the distinction between how different fairness notions hold up under strategic play.
Proportionality is Robust
The authors demonstrate that proportionality is remarkably resilient. If a GCC protocol is proportional when agents are honest, its strategic equilibria are also proportional. In other words, strategic play does not allow agents to be "cheated" out of their fair $1/n$ share, provided the underlying protocol is designed to guarantee it.
Envy-Freeness is Fragile
In contrast, envy-freeness is more susceptible to manipulation. The authors show that strategic play can actually induce envy in protocols that are envy-free under honest behavior (such as the Selfridge-Conway protocol). This suggests that designing protocols that remain envy-free in equilibrium is a much steeper challenge.
Implementing Envy-Freeness: The "Thieves Protocol"
To address the fragility of envy-freeness, the authors design a specific GCC protocol where the Nash Equilibrium outcomes perfectly coincide with the set of contiguous envy-free allocations. This result is a major contribution to implementation theory: it shows that it is possible to design a game where the only stable, strategic outcomes are those that are inherently fair. If agents play optimally for themselves in this "Thieves Protocol," they are guaranteed to reach an envy-free division.
Conclusion and Future Work
This research provides the first robust computational model for analyzing strategic behavior across a broad class of fair division protocols. While it establishes that proportionality is preserved in equilibrium and provides a mechanism for envy-free implementation, several questions remain.
Future work may explore whether envy-freeness can be implemented via the stronger Subgame Perfect Nash Equilibrium (SPNE) rather than standard Nash Equilibrium. Additionally, extending these results to non-contiguous allocations—where pieces may consist of multiple disjoint intervals—would further generalize the framework's applicability to complex real-world resource division.
Summary updated