cut the cake

what is "fair"?

Two competing definitions for dividing a resource among n players:

• Proportional. Each player values their piece at ≥ 1/n of the total cake. Everyone gets at least their "fair share."
• Envy-free. No player values another player's piece more than their own. Strictly stronger than proportionality when n ≥ 3.

the protocols

• n = 2: cut-and-choose. Known since antiquity (Genesis 13). One player cuts the cake into two pieces they value equally. The other picks. The cutter gets the remainder. Both are guaranteed ≥ 1/2 by their own valuation.
• n players: last diminisher (Banach and Knaster, published by Steinhaus in 1948). One player cuts a piece they think is worth 1/n. It passes around, and anyone who thinks it is worth more trims it back to 1/n. The last to trim takes it. Remaining players repeat. The moving-knife version is Dubins-Spanier (1961): a knife sweeps across the cake, and the first player to shout "stop" takes the piece so far. Both guarantee proportionality but not envy-freeness.
• n = 3, envy-free: Selfridge-Conway (1960s). Player 1 cuts three equal pieces (by their measure). Player 2 trims the largest to tie the second-largest. Player 3 picks first, then 2, then 1, and if player 3 left the trimmed piece, player 2 must take it. The trimming is divided separately. Bounded and envy-free.
• n players: Brams-Taylor (1995). First envy-free protocol for any number of players. It always terminates, but the number of steps is unbounded: it depends on the valuations. A bounded protocol for any n came only with Aziz-Mackenzie (2016), and its step count is astronomical. Before that, it was open whether bounded envy-free division was even possible for n ≥ 4.

computational complexity

In general, finding an envy-free division (with contiguous pieces) is PPAD-complete.

• A solution always exists (Stromquist, 1980, for contiguous pieces on a line).
• But computing it is as hard as computing Nash equilibria (a choice for every player in a game where no one gains by switching alone) or Brouwer fixed points (a continuous map from a disk to itself must leave some point where it was; finding that point is the hard part).
• No polynomial-time algorithm is known for the general problem, and PPAD-hardness is strong evidence that none exists. That is a statement about how the work grows with the instance, not about any one small cake.

PPAD is the class of search problems whose answers are guaranteed to exist by a parity argument, a kind of "an odd number of these must exist, so at least one does." The existence proof here relies on Sperner's lemma: chop a triangle into small triangles and color the corners by a rule along the edges, and at least one small triangle must get all three colors. For cake, each point of the triangle is a way to place the cuts, each corner is handed to one player and colored by the piece that player would pick there, and an all-colors small triangle gives nearby cut positions where the three players each want a different piece: an almost envy-free division, which gets exact as the triangles shrink. The proof is constructive but not efficient. The game you just played is a small instance of that problem: fine by hand with a few players, but the general version is believed intractable as the number of players grows.