# Communication Complexity of Cake Cutting

arXiv: https://arxiv.org/abs/1709.09876 · HTML: https://mlsanity.com/paper/1709.09876/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Sep 2017.

## Built on by (most cited first, 1 of 1)

- [The Complexity of Envy-Free Graph Cutting](https://mlsanity.com/paper/2312.07043/) (2023)

## Abstract (arXiv)

We study classic cake-cutting problems, but in discrete models rather than using infinite-precision real values, specifically, focusing on their communication complexity. Using general discrete simulations of classical infinite-precision protocols (Robertson-Webb and moving-knife), we roughly partition the various fair-allocation problems into 3 classes: "easy" (constant number of rounds of logarithmic many bits), "medium" (poly-logarithmic total communication), and "hard". Our main technical result concerns two of the "medium" problems (perfect allocation for 2 players and equitable allocation for any number of players) which we prove are not in the "easy" class. Our main open problem is to separate the "hard" from the "medium" classes.