Fair Division

Two children, one cake, and a single rule everyone has used: one cuts, the other chooses. The cutter, knowing the chooser grabs first, has every reason to split the cake as evenly as they see it. Whatever happens, neither child can complain they got the worse piece — each ends up with a share they value at least as much as the other's.

This isn't just folk wisdom. Cut-and-choose is a mathematical theorem: for two people it always produces a division that is both proportional (each feels they got at least half) and envy-free (neither would swap). And it works even when the two of them value the cake completely differently — one loves frosting, the other loves the strawberries.

The deep question is what happens when there are three people. Or ten. Suddenly the friendly trick falls apart, and finding an envy-free split becomes one of the most surprising hard problems in mathematics.

Below is a cake whose left and right halves are worth different amounts to two players — drag the sliders to set each player's tastes. The cutter then finds the spot that splits the cake into two pieces they value equally, and the chooser takes whichever piece they prefer.

<p class="hint">{{hint}}</p>

<div class="row">
  <label>{{label_cutter}}
    <input id="p1" type="range" min="0" max="100" value="30">
  </label>
  <label>{{label_chooser}}
    <input id="p2" type="range" min="0" max="100" value="80">
  </label>
</div>

<div id="cake" class="cake"></div>
<div class="legend">
  <span class="sw left"></span> {{legend_left}}
  <span class="sw right"></span> {{legend_right}}
  <span class="cutmark">|</span> {{legend_cut}}
</div>

<div class="btns">
  <button id="run" type="button">{{btn_run}}</button>
  <button id="rand" type="button" class="ghost">{{btn_rand}}</button>
</div>
<div id="verdict" class="verdict">{{verdict_init}}</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.row { display: flex; flex-wrap: wrap; gap: 1rem; margin-bottom: .8rem; }
label { font-size: .82rem; font-weight: 600; color: #1d3557; display: flex; flex-direction: column; gap: .3rem; flex: 1 1 180px; }
input[type=range] { width: 100%; }
.cake { position: relative; height: 60px; border-radius: 10px; overflow: hidden;
        border: 1px solid #cdd9e3; background: linear-gradient(90deg, #f4a261, #e76f51); }
.cut { position: absolute; top: -4px; bottom: -4px; width: 3px; background: #1d3557;
       transform: translateX(-50%); transition: left .35s ease; }
.cut::after { content: ""; position: absolute; top: -7px; left: 50%; transform: translateX(-50%);
              border-left: 6px solid transparent; border-right: 6px solid transparent; border-top: 8px solid #1d3557; }
.legend { font-size: .78rem; color: #555; margin: .55rem 0; display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; }
.sw { display: inline-block; width: 14px; height: 14px; border-radius: 3px; vertical-align: -2px; }
.sw.left { background: #f4a261; } .sw.right { background: #e76f51; }
.cutmark { color: #1d3557; font-weight: 700; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-top: .3rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.verdict { font-size: .95rem; margin-top: .7rem; min-height: 3.4em; line-height: 1.5; padding: .6rem .8rem;
           border-radius: 8px; background: #f1f5f9; }
.verdict.ok { background: #e3f5e8; color: #0a5d2a; }
.verdict b { color: inherit; }

// Code not found

Watch the verdict: no matter how differently the two value the cake, the result is always envy-free — each player ends up with a piece worth at least as much to them as the piece they didn't get. That guarantee comes for free with two players. The hard part, as we'll see, is keeping it when more people join the table.

How hard is fair division, really? It depends entirely on how many people share the cake.

• Two players: solved, ancient. Cut-and-choose is provably envy-free and needs just one cut and one choice. Checking a split is trivial; finding it is trivial too.
• Three players: solved, but tricky. The Selfridge–Conway protocol (around 1960) gives an envy-free split for three using at most five cuts — clever, but no longer obvious.
• Any number of players: solved only in 2016. Whether a bounded envy-free protocol existed for general n was open for decades. Haris Aziz and Simon Mackenzie finally found one — but its number of cuts is bounded by a tower of exponentials, roughly n to the n to the n to the n to the n to the n. It's finite, yet astronomically impractical.
• The lower bound bites too. Even just querying the players enough to guarantee envy-freeness provably requires a number of questions that grows faster than any polynomial.

So fair division is a rare creature: provably solvable, yet the only known general method is so expensive it could never run. The friendly two-person trick hides a problem whose difficulty explodes the moment a third person sits down — a flavor of intractability close in spirit to the gap behind P vs NP.

"Divide this resource so everyone feels fairly treated" describes a huge slice of real life, and fair-division theory turns gut feelings into provable guarantees:

• Inheritance and divorce: the Adjusted Winner procedure splits contested assets so both parties end up envy-free, and has been studied for real settlements.
• Rent and chores: sites like Spliddit let roommates split rent across unequal bedrooms so nobody envies another's room-and-price deal.
• Public resources: dividing disputed land, fishing quotas, or airport landing slots are textbook fair-division problems.
• Computing: allocating CPU, memory, and bandwidth among users is "cake cutting" with servers, where dominant resource fairness keeps every tenant content.

The thread is always the same as in assignment and other allocation problems: many parties, one pie, and a demand that the result be defensibly fair rather than merely fast.

Fair division hides a beautiful arc. For two people, a trick older than mathematics itself delivers a guaranteed envy-free split in a single cut. Add one more person and you need the clever Selfridge–Conway dance. Ask for any number of people and the question stayed open until 2016, when Aziz and Mackenzie finally answered "yes — but at a cost that towers beyond all practicality."

So the next time you say "you cut, I choose," savor it: you're using one of the few fairness problems we've completely solved. Just don't invite too many friends — fairness, it turns out, gets harder faster than almost anything, echoing the same wall we meet in P vs NP.