Matpic
mathematics, in pictures
Concept

Fair division

The problem of splitting one resource among people who value its parts differently, judged against a property the split must have. The properties usually asked for are proportionality and envy-freeness, and the difficulty is that they are not the same requirement.

Named by 5 essays across 3 fields — 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 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 One line, and both shapes halved. Two shapes and the single straight cut that divides each of them into two equal areas. The direction was found by sweeping every angle and watching the imbalance change sign.

One line that halves them both

Two shapes lying anywhere on a page, of any sizes and any shapes at all. There is always a single straight line that cuts both of them into two equal halves at once — and finding it needs no cleverness, only the observation that a quantity which reverses sign has to pass through zero.

topology · Borsuk ulam A three-coloured triangulation, and the walk that finds a rainbow triangle. A triangle cut into 36 smaller ones, its corners coloured under Sperner's rule. The 9 small triangles carrying all three colours are shaded, and a path enters through a door on one edge and ends inside one of them.

Three colours force a triangle

Cut a triangle into small ones and colour the corners under one restriction. However the cutting and the colouring are done, some small triangle ends up with all three colours — and the number of them is always odd.

discrete · Fixed points

Named alongside it

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

Counting argumentDivide-and-chooseEnvy-freenessExistence proofProportionalityValuation measureBrouwerFixed pointAntipodal pairBisectionContinuityDegree

All concepts