Introduction

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.

Cut and Choose

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">Two players value the same cake differently. Set how much each of them likes the <b>left</b> end versus the <b>right</b> end. The <b>cutter</b> cuts where the two pieces look equal to <i>them</i>; the <b>chooser</b> takes their favorite piece. The verdict checks: does anyone envy the other?</p>

<div class="row">
  <label>Cutter likes left vs right
    <input id="p1" type="range" min="0" max="100" value="30">
  </label>
  <label>Chooser likes left vs right
    <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> left flavor
  <span class="sw right"></span> right flavor
  <span class="cutmark">|</span> the cut
</div>

<div class="btns">
  <button id="run" type="button">Cut &amp; choose</button>
  <button id="rand" type="button" class="ghost">Randomize tastes</button>
</div>
<div id="verdict" class="verdict">Press "Cut &amp; choose".</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// CUT-AND-CHOOSE, the classic two-person envy-free protocol.
//
// Model the cake as the interval [0,1]. Each player p has a value DENSITY:
// d_p(x) rises linearly from a "left taste" to a "right taste". The value a
// player assigns to a sub-interval is the integral of their density over it,
//
// Step 1 (cut): the CUTTER finds the point c where their own value of [0,c]
//   equals their value of [c,1] — i.e. each half is worth 1/2 to the cutter.
// Step 2 (choose): the CHOOSER takes whichever piece they value more.
// Claim: the result is ENVY-FREE for both. The chooser obviously doesn’t envy
//   (they picked their favourite). The cutter values BOTH pieces at exactly 1/2, so whichever is left is worth 1/2 to them — they never envy either.

// value of [a,b] for a player with left/right weights wL,wR (density is the
// line from wL at x=0 to wR at x=1). Closed form of the integral, normalised.
function value(a, b, wL, wR) {
  const F = x => wL * x + (wR - wL) * x * x / 2;   // antiderivative of the density
  const total = F(1) - F(0);
  return total === 0 ? (b - a) : (F(b) - F(a)) / total;
}

// cutter’s fair cut: solve value(0,c)=1/2 by bisection (value is monotone in c).
function fairCut(wL, wR) {
  let lo = 0, hi = 1;
  for (let i = 0; i < 60; i++) {
    const mid = (lo + hi) / 2;
    if (value(0, mid, wL, wR) < 0.5) lo = mid; else hi = mid;
  }
  return (lo + hi) / 2;
}

const p1 = document.getElementById('p1');   // cutter slider (0..100 -> taste)
const p2 = document.getElementById('p2');   // chooser slider
const cake = document.getElementById('cake');
const verdict = document.getElementById('verdict');

// map a 0..100 slider to (wL,wR) densities. 0 = loves left, 100 = loves right.
function taste(slider) {
  const t = slider.value / 100;             // 0..1
  return { wL: 2 * (1 - t) + 0.15, wR: 2 * t + 0.15 };
}

function run() {
  const A = taste(p1), B = taste(p2);
  const c = fairCut(A.wL, A.wR);            // cutter’s fair line

  // chooser’s value of each piece
  const left  = value(0, c, B.wL, B.wR);
  const right = value(c, 1, B.wL, B.wR);
  const chooserTakesLeft = left >= right;

  // each player’s value of the piece they end up with
  const chooserGot = chooserTakesLeft ? left : right;
  const cutterGot  = chooserTakesLeft
    ? value(c, 1, A.wL, A.wR)              // cutter keeps the right piece
    : value(0, c, A.wL, A.wR);             // cutter keeps the left piece
  const cutterOther  = chooserTakesLeft ? value(0, c, A.wL, A.wR) : value(c, 1, A.wL, A.wR);
  const chooserOther = chooserTakesLeft ? right : left;

  // draw cake + cut
  cake.innerHTML = '<div class="cut" style="left:' + (c * 100) + '%"></div>';

  const envyFree = cutterGot >= cutterOther - 1e-9 && chooserGot >= chooserOther - 1e-9;
  const pct = v => Math.round(v * 100);
  verdict.className = 'verdict' + (envyFree ? ' ok' : '');
  verdict.innerHTML =
    fmt('Cut at <b>%pct%%</b>. Chooser takes the <b>%v%</b> piece.<br>Cutter values its piece at <b>%pct2%%</b> (the other at %pct3%%). Chooser values its piece at <b>%pct4%%</b> (the other at %pct5%%).<br>%v2%', { pct: pct(c), v: chooserTakesLeft ? 'left' : 'right', pct2: pct(cutterGot), pct3: pct(cutterOther), pct4: pct(chooserGot), pct5: pct(chooserOther), v2: envyFree ? '✓ <b>Envy-free</b> — each got a piece worth at least as much as the one they didn’t.'
              : '✗ Someone envies the other.' });
  console.log('cut', c.toFixed(3), 'cutterGot', cutterGot.toFixed(3),
              'chooserGot', chooserGot.toFixed(3), 'envyFree', envyFree);
}

document.getElementById('run').addEventListener('click', run);
document.getElementById('rand').addEventListener('click', () => {
  p1.value = Math.floor(Math.random() * 101);
  p2.value = Math.floor(Math.random() * 101);
  run();
});
p1.addEventListener('input', run);
p2.addEventListener('input', run);
run();
Result
Console

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.

The Real Complexity

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.

Where It Matters

"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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/fair-division/Content licensed under CC BY-NC 4.0.