A compositional game to fairly divide homogeneous cake

Abel JansmaarXiv 2023 · DOI · arXiv

Abstract

Fair division of resources among multiple agents is a central challenge in game theory. While simple protocols exist for two players, scaling to $n$ players often introduces significant inequality or requires centralized oversight. This paper introduces the "Biggest Player" rule, a decentralized protocol for dividing a homogeneous resource. By leveraging compositional game theory, we demonstrate that designating the player with the largest share as the next cutter creates a self-correcting mechanism. This protocol achieves a stable Nash equilibrium where every player receives an exact $1/n$ share, resulting in perfect fairness (Gini coefficient of 0) and optimal efficiency (Price of Anarchy of 1).

Introduction

The classic "I cut, you choose" protocol provides a perfect solution for fair division between two players. However, extending this to $n$ players is non-trivial. Most existing $n$-player solutions rely on a "benevolent dictator" or complex moving-knife algorithms that may produce non-contiguous pieces. This paper explores how decentralized, sequential interactions can be structured to ensure fairness without external intervention.

The Failure of Vanilla Sequential Division

A naive approach to multi-player division is "Vanilla Composition," where players sequentially cut and pass remainders. For example, Player 1 cuts a piece for Player 2, then Player 2 cuts their remaining portion for Player 3, and so on.

This method fails spectacularly in terms of fairness. In such a chain, the first player typically secures 50% of the resource, the second 25%, and subsequent players receive exponentially smaller shares. As the number of players increases, the Gini coefficient—a standard measure of statistical dispersion representing inequality—rapidly approaches 1, indicating total inequality.

Inequality in the vanilla sequential division method increases rapidly with the number of players, as shown by the Gini coefficient approaching 1.

The "Biggest Player" Protocol

To solve the inequality of sequential division, this paper proposes the "Biggest Player" rule. The protocol proceeds as follows:

  1. Start with two players using "I cut, you choose."
  2. For each new player entering the game, the player currently holding the largest piece of the resource is designated as the "cutter."
  3. The cutter must divide their own piece, and the new player chooses one of the two resulting segments.

This rule turns the largest slice into a "hot potato." If a player attempts to take more than their fair share ($1/n$), they become the target for the next player, who will naturally take the excess.

Incentives and Nash Equilibrium

Using the Open Game engine and compositional game theory, the author verifies the incentive structures of this rule. The game is modeled as a series of "lenses" where players' strategies are interdependent.

The analysis shows that the "Biggest Player" rule creates a payoff structure where any deviation from cutting a $1/n$ share results in a lower final payoff for the cutter in subsequent rounds. Consequently, the fair distribution of $1/n$ for all players is the unique stable Nash equilibrium.

The 'Biggest Player' rule creates a payoff structure where the optimal strategy for any player is to cut a fair share of 1/n.

Key Results

The "Biggest Player" rule offers several theoretical and practical advantages:

  • Perfect Fairness: It achieves a Gini coefficient of 0 at equilibrium, regardless of the number of players.
  • Optimal Efficiency: The Price of Anarchy (PoA) remains 1, meaning the decentralized outcome is as efficient as one mandated by a perfect central authority. In contrast, the PoA of the vanilla method grows linearly with $n$.
  • Contiguity: Every player receives a single, contiguous piece, avoiding the "crumbs" produced by many other fair-division algorithms.
  • Low Complexity: The protocol requires only $n-1$ cuts, making it highly efficient for real-world applications.

Conclusion

The "Biggest Player" rule demonstrates that fairness in decentralized systems is a product of the topology of interactions. By structuring the game so that the "strongest" player is always the one to give up resources, we can achieve perfect equality without a dictator. Future work may extend this model to heterogeneous resources where players have differing valuation functions.

Summary updated

Abstract

The central question in the game theory of cake-cutting is how to fairly distribute a finite resource among multiple players. Most research has focused on how to do this for a heterogeneous cake in a situation where the players do not have access to each other's valuation function, but I argue that even sharing homogeneous cake can have interesting mechanism design. Here, I introduce a new game, based on the compositional structure of iterated cake-cutting, that in the case of a homogeneous cake has a Nash equilibrium where each of $n$ players gets $1/n$ of the cake. Furthermore, the equilibrium distribution is the result of just $n-1$ cuts, so each player gets a contiguous piece of cake. Naive composition of the `I cut you choose' rule leads to an exponentially unfair cake distribution with a Gini-coefficient that approaches 1, and suffers from a high Price of Anarchy. This cost is completely eliminated by the proposed \textit{Biggest Player} rule for composition which achieves decentralised and asynchronous fairness at linear Robertson-Webb complexity. After introducing the game, proving the fairness of the equilibrium, and analysing the incentive structure, the game is implemented in Haskell and the Open Game engine to make the compositional structure explicit.
BibTeX
@misc{jansma2023compositional,
  author = {Abel Jansma},
  title = {{A compositional game to fairly divide homogeneous cake}},
  year = {2023},
  eprint = {2301.02281},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2301.02281},
}
Figure