Matpic
mathematics, in pictures
Concept

Divide-and-choose

The two-person rule under which one person cuts the thing in two and the other takes whichever part they prefer. It guarantees each of the two a share they value at half or more, and it needs no agreement about what the parts are worth.

Named by 3 essays across one field — each of them below, with the objects they name alongside it.

Also named here as envy-freeness, valuation measure — the same set of essays touches all of them, so they are one junction rather than several.

One cake, one halving cut at 4/9, and two measures of it. A cake as a bar with two step valuations above and below it, the cutter's halving cut marked, and a table of both people's exact value of each piece.

One cuts and the other chooses

The oldest rule in fair division promises each of two people at least half the cake by their own measure, and it keeps that promise exactly. It does not promise what the word "fair" is usually asked to carry, and the gap opens the moment the two measures disagree across the cut.

applied · Fair division Three people, a trimmed piece, and the nine comparisons that settle it. The four stages of the Selfridge–Conway division drawn along a cake, with the full three-by-three matrix of each person's value of each share.

Three people and a trimmed piece

For two people, one cut and one choice deliver a division nobody would swap out of. For three, the same promise costs a trimming, a residue and a choosing order contrived so that an advantage once given cannot be taken back — and the verdict is not three numbers but a whole three-by-three matrix.

applied · Fair division Every allocation of 3 indivisible items, and not one of them envy-free. A value matrix for indivisible goods with the round-robin allocation shaded, the exhaustive counts of envy-free and EF1 allocations, and a control matrix on which envy-free allocations do exist.

Envy-free, up to one item

A cake can be cut anywhere, and every guarantee in this anchor was bought with that freedom. Take the knife away and the exhaustive search over every allocation of three objects returns nothing envy-free at all — so the subject weakened the word until taking turns was enough to reach it.

applied · Fair division

Named alongside it

The objects these essays reach for when they reach for this one.

Envy-freenessFair divisionProportionalityValuation measureCounting argumentEnvy matrixExistence proofIndivisible goodsMeasureMoving knifeSelfridge conwaySymmetry

All concepts