Matpic
mathematics, in pictures
Concept

Envy-freeness

The property of a division that nobody values another's share above their own. It is a stronger requirement than each person getting a fair share by their own reckoning, and for three or more people it is much harder to achieve.

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

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 about fair cutting 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 Maximising the product of two people's values. The frontier of value pairs from dividing 4 goods between two people, with the points maximising the product, the sum and the smaller value. The product's maximum is (65.0, 54.2) and is envy-free.

The product that makes a division fair

Divide goods to make the total happiness as large as possible and the result can be monstrously unfair; make the least happy person as happy as possible and it can waste. Multiply the people's values together and maximise the product instead, and something unexpected happens — nobody envies anybody when goods can be split, and nobody envies by more than one item when they cannot.

applied · Fair division

Named alongside it

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

Fair divisionValuation measureDivide and chooseProportionalityCounting argumentIndivisible goodsAllocationConvexityDualityEfficiencyEnvy matrixExistence proof

All concepts