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 = 3: Steinhaus, Banach, Knaster (1944). The "last diminisher" protocol. A knife moves across the cake. When any player shouts "stop," that piece is cut and the shouter takes it. Remaining players repeat. Guarantees 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 from the trimmed pieces, then 2, then 1. The trimming is divided separately. Bounded and envy-free.
• n players: Brams-Taylor (1995). First bounded envy-free protocol for any number of players. The step count can be astronomical, but it always terminates. Before this result, it was open whether bounded envy-free division was even possible for n ≥ 4.

computational complexity

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 or Brouwer fixed points.
• No polynomial-time algorithm is known, and (under standard complexity assumptions) none exists.

The existence proof relies on Sperner's lemma applied to simplicial subdivisions of the division space. The proof is constructive but not efficient. The game you just played is literally a computationally hard problem.