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.

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

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

the cutter's measure, segment by segmentthe chooser's measure, segment by segment52530201553010552030cut at 4/9the left piecethe right piecethe cutterthe chooser5050130/3≈ 43.33170/3≈ 56.67the cutter's piecethe chooser's piecethe cutter's running total crosses 50 inside segment 3, 2/3 of the way through it, so the cut is at 4/9both pieces are worth exactly 50 to the cutter; the chooser takes the right one at 170/3 ≈ 56.67 andgains 20/3 ≈ 6.67 over half

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 person 1 cuts three pieces of equal value to person 1piece 1piece 2piece 3person 2 trims the largest of them down to a tie with the secondthe trimming: 140/3 ≈ 46.67 to person 2person 3 chooses, then person 2, then person 1person 1person 3person 2person 3 cuts the trimming in three; person 2 chooses first, then person 1person 1person 2person 3the trimming, drawn at full widtheach person's value of each share — the diagonal is their ownperson 1's shareperson 2's shareperson 3's shareperson 1 valuesperson 2 valuesperson 3 values140/3≈ 46.6740/3≈ 13.33402040403540/3≈ 13.33155/3≈ 51.67own sharethe trimmingperson 1 cuts three pieces worth 100/3 each; person 2 trims 140/3 ≈ 46.67 off the largest, andperson 3 chooses firstthe verdict is the whole 3×3 matrix, not its diagonal: all nine comparisons hold, 1 of them as anexact tie

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 what each person would pay for each item, out of 100 for the setitem aitem bitem cperson 1person 2403525304525allocations: 8envy-free: 0up to one item: 4the control — the same search, on a matrix that has an answeritem aitem bitem cperson 1person 2503020203050allocations: 8envy-free: 2up to one item: 4round-robin pickingan envy-free allocationall 8 allocations of 3 items to 2 people were formed: 0 are envy-free, 4 are envy-free up to one itemround-robin picking, shaded, gives person 1 items a and c; person 2 item b — person 2 stopsenvying person 1 once item a is set asidethe control matrix underneath is searched by the same code and has 2 envy-free allocations, so anempty answer above is a finding rather than a broken search

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