Generator

One cake, one halving cut at 4/9, and two measures of it

A generator in the applied library, called 47 times across 8 essays. Below: what it draws with nothing chosen and at each mode an essay asks for, what it checks while drawing, and everywhere it is used.

divide is one function. Everything below came out of it during this build, at parameters taken from the essays rather than invented for this page — so a figure here is the same figure a reader meets in an essay, and if the generator changes, this page changes with it.

With nothing chosen

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.

Two rooms, two housemates, one crossing

Dividing a rent of 90 three ways, on a 9-step grid

Envy left at the best fully labelled triangle, as the grid refines

A rent split nobody envies

Every allocation of 3 indivisible items, and not one of them envy-free

What it checks while it draws

Collected by running the family and recording what it asserted, not written here. The count is how many separate times the claim was put to the test while these drawings were made.

person 1's valuation is a list of 6 to 6 numbers ×11
person 2 receives at least a 1/4 share by their own measure ×11
person 1 values their own share at least as highly as person 1's ×9
each entry of person 1's valuation is a whole number between 0 and 100 ×7
person 1's cake totals 100 ×7
the value matrix, person 1's row is a list of 3 to 3 numbers ×7
trimming piece 1 is worth exactly a third of the trimming to person 3 ×6
every random instance with 2 people and 4 items had an allocation envy-free up to any item ×5
person 1's values is a list of 2 to 6 numbers ×5
the control matrix, person 1's row is a list of 3 to 3 numbers ×5
no allocation of these goods is envy-free — all 8 were tested and each failed ×4
person 1 strictly prefers person 3's piece to their own ×4
person 1's own piece is worth at least 25 to person 1 ×4
person 1's valuation of the whole cake is 100 ×4
person 1's values of the 4 pieces account for the whole cake ×4
person 2 receives at least a 1/4 share ×4
person 2's calling mark stays over the bar it belongs to ×4
each entry of person 1's values is a whole number between 0 and 100 ×3
each entry of the control matrix, person 1's row is a whole number between 0 and 100 ×3
each entry of the value matrix, person 1's row is a whole number between 0 and 100 ×3
person 1's items total 100 ×3
person 1's values of the three shares account for the whole cake ×3
person 2 called the knife at exactly 25 ×3
piece 1 is worth exactly a third of the cake to person 1 ×3
the control matrix: person 1 values the whole set at 100 ×3
the valuations are given for 2 to 2 people ×3
the value matrix: person 1 values the whole set at 100 ×3
person 1 buys only goods of the best value for money to them ×2
person 1 spends exactly their budget ×2
person 1's goods total 100 ×2
the number of people is a whole number between 2 and 6 ×2
a knife is asked to pass a non-negative amount of value ×1
a person sent left values the left part at their share or more ×1
a person sent right values the right part at their share or more ×1
a rational is a whole numerator over a non-zero whole denominator ×1
a rational is never divided by zero ×1
an allocation envy-free up to any item exists ×1
an envy-free split exists on the quarter-unit grid ×1
an odd number of fully labelled triangles at every fineness ×1
and each gets at least half by their own measure ×1
and fewer than the last diminisher from four people on ×1
and moves the sum's maximiser ×1
and one envy-free up to one item ×1
and up to any item implies up to one ×1
at each end the free room is chosen ×1
at the product's maximum neither person values the other's bundle more than their own ×1
each generated valuation totals exactly 100 ×1
envy-free implies envy-free up to any item ×1
every envy-free allocation is also envy-free up to one item ×1
every person still waiting gets a calling mark ×1
every small triangle has one corner for each housemate ×1
every way of giving each item to one of the people was formed ×1
halving asks at most n⌈log₂ n⌉ questions ×1
nobody left behind values the slice at more than their share of what remained ×1
on the boundary every choice is a free room ×1
person 2 does not envy person 1's piece before the trimming is divided ×1
person 4, who never called, is left with at least 25 ×1
rescaling one person's values leaves the product's maximiser unchanged ×1
some allocation is envy-free up to one item but not up to any ×1
somewhere two neighbouring points choose different rooms ×1
the chooser envies nobody, having taken the piece it valued higher ×1
the chooser gains strictly more than half — the promise is not tight ×1
the chooser's piece is worth at least half the cake to the chooser ×1
the chooser's values of the two pieces sum to the whole cake ×1
the claim that somebody is left envious is either made or not made ×1
the claim that the chooser strictly gains is either made or not made ×1
the control matrix gives a row of values for two, three or four people ×1
the control was searched over every allocation too ×1
the control: a chooser with the cutter's own measure gains exactly nothing ×1
the control: the same search finds an envy-free allocation where one exists ×1
the cutter is content with either bundle up to any item ×1
the cutter's envy is exactly zero: the piece left behind is worth what the other is ×1
the division being shown is one of cutchoose, trim, items, moving, evenpaz, lastdim, cutcount, nash, scale, prices, mnwitems, mnwsearch, efx, efxcensus, efxcut, rent, rent2, rentrefine, rentexact ×1
the division is proportional and not envy-free: somebody prefers another's piece ×1
the envy left is at most twice the grid step ×1
the exact arithmetic stays inside the safe integer range ×1
the exact value of the left piece and the decimal one agree ×1
the fineness of the triangulation is a whole number between 3 and 24 ×1
the fully labelled small triangles are odd in number ×1
the instance is one of three, noef, two ×1
the largest number of people is a whole number between 16 and 128 ×1
the marks made match the count the recursion predicts ×1
the number of instances is a whole number between 50 and 600 ×1
the number of items in the control matrix is a whole number between 2 and 6 ×1
the number of items in the value matrix is a whole number between 2 and 6 ×1
the number of segments the cake is cut into is a whole number between 2 and 12 ×1
the product-maximising allocation is envy-free up to one item ×1
the product's maximiser is envy-free up to one item on every instance ×1
the rents add up to the whole ×1
the rescaling factor is between 1 and 10 ×1
the result is envy-free up to any item for both ×1
the round-robin allocation is envy-free up to one item ×1
the rule asks n(n+1)/2 − 1 questions ×1
the sum's maximiser is not ×1
the three pieces go to three different people ×1
the trimmed piece ties person 2's second largest exactly ×1
the value asked for is still ahead of the knife ×1
the value matrix gives a row of values for two, three or four people ×1
two calling marks never print on top of one another ×1
two or three people ×1
two people ×1
under the cutter's own measure the two pieces are exactly equal ×1

Where it is called

Every figure on this list is drawn by the same rule, so a change to the rule changes all of them at once. That is why the list is published.

Applied

A rent nobody envies

Three housemates, three rooms that are not alike, one rent. Every way of splitting the rent is a point of a triangle; ask, at each point of a fine grid, which room one housemate would take at those prices, taking turns so that each small triangle has one corner for each of them. Sperner's lemma then promises a small triangle where all three would choose different rooms — and as the grid is refined, the envy at that triangle shrinks to nothing.

Applied

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

Envy that any single item would cure

Envy-free up to one item lets a person's envy be excused if removing the envied bundle's best item would cure it. The stronger standard asks that removing any item would — even the one that person values least. Every allocation of three people's items can be searched, and an allocation meeting the stronger standard was there every time; for two people cut and choose finds one, for three it took until 2020 to prove, and for four nobody knows.

Applied

How many cuts a fair share costs

Every person can be guaranteed a share of a cake worth at least one n-th by their own measure, and the oldest rule that does it asks about n²/2 questions. Splitting the people into halves and the cake at a median mark asks about n log n — and a theorem says nothing can ask fewer. Fairness has a price, and it can be counted.

Applied

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.

Topology

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.

Applied

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

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.

The whole library · What the figures prove