Cutting a Cake Is Not Always a "Piece of Cake": A Closer Look at the Foundations of Cake-Cutting Through the Lens of Measure Theory

Peter Kern, Daniel Neugebauer, Jörg Rothe, René L. Schilling, Dietrich Stoyan, Robin WeishauptarXiv 2021 · arXiv

Introduction

Cake-cutting is a fundamental metaphor in artificial intelligence, economics, and mathematics for the fair division of a divisible, heterogeneous resource. While algorithms for dividing such resources are heavily scrutinized, the foundational mathematical rules—specifically what constitutes a "piece" of cake—are often treated informally. This lack of rigor can lead to mathematical paradoxes, especially when protocols require an unbounded or infinite number of cuts to achieve guarantees like envy-freeness.

This paper applies the tools of measure theory and functional analysis to evaluate these foundational assumptions. By formalizing the "cake" as the interval $[0,1]$, the authors identify the Borel $\sigma$-algebra as the most robust framework for defining admissible pieces.

The Mathematical Definition of a "Piece"

A central question in fair division is: what set of subsets of the cake should be considered "admissible"? The literature varies wildly, from single contiguous intervals to arbitrary subsets. The authors demonstrate a strict hierarchy of these sets:

Finite intervals $\subsetneq$ Countable unions of intervals $\subsetneq$ Borel sets $\subsetneq$ Lebesgue sets $\subsetneq$ The Power set.

Allowing any arbitrary subset (the power set) introduces unmeasurable sets, such as the Vitali set, which break standard valuation functions. Conversely, assuming pieces are merely countable unions of intervals is also problematic; the authors prove this family is not an algebra. This means the complement of a valid piece (the "leftover" cake) might not be a valid piece itself.

The construction of the Cantor set illustrates how an infinite sequence of cuts leads to complex sets that are Borel sets but not finite unions of intervals.

As shown in the construction of the Cantor set (Figure 1), infinite cutting processes quickly move beyond simple interval unions. The authors argue that the Borel $\sigma$-algebra is the "Goldilocks" choice: it is closed under countable unions and complements, avoids unmeasurable paradoxes, and allows standard preferences to be uniquely extended to complex pieces.

Valuation Functions and Divisibility

Beyond the definition of pieces, the paper examines how agents value them. A key property in fair division is "divisibility"—the ability to divide a piece into any exact proportion. The authors prove that for a finitely additive valuation, being "sliceable" (divisible) is mathematically equivalent to being atom-free (having no single points with positive value).

The Cantor function (Devil's Staircase) provides a rigorous example of an atom-free valuation that is continuous but singular, demonstrating the complexity of divisibility.

Using the Cantor function (Figure 5) as an example, the authors illustrate valuations that are continuous (atom-free) yet singular. They show that standard "box-based" valuation functions used in AI literature can be rigorously extended to the entire Borel $\sigma$-algebra using Carathéodory's extension theorem, providing a solid foundation for future algorithmic design.

Conclusion

While naive approaches using finite unions of intervals suffice for simple protocols, they fail as algorithms become more complex. By adopting the Borel $\sigma$-algebra and measure-theoretic valuations, researchers can avoid the "leftover cake" problem and ensure their fair division protocols are mathematically sound. The authors suggest that existing infinite or open-ended algorithms should be re-evaluated through this rigorous lens to ensure their underlying assumptions hold.

Summary updated

Abstract

Cake-cutting is a playful name for the fair division of a heterogeneous, divisible good among agents, a well-studied problem at the intersection of mathematics, economics, and artificial intelligence. The cake-cutting literature is rich and edifying. However, different model assumptions are made in its many papers, in particular regarding the set of allowed pieces of cake that are to be distributed among the agents and regarding the agents' valuation functions by which they measure these pieces. We survey the commonly used definitions in the cake-cutting literature, highlight their strengths and weaknesses, and make some recommendations on what definitions could be most reasonably used when looking through the lens of measure theory.
BibTeX
@misc{kern2021cutting,
  author = {Peter Kern and Daniel Neugebauer and Jörg Rothe and René L. Schilling and Dietrich Stoyan and Robin Weishaupt},
  title = {{Cutting a Cake Is Not Always a "Piece of Cake": A Closer Look at the Foundations of Cake-Cutting Through the Lens of Measure Theory}},
  year = {2021},
  eprint = {2111.05402},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2111.05402},
}
Figure