Series

Fair division — the series

11 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 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.

    part 1 · applied
  2. 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.

    part 2 · applied
  3. 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.

    part 3 · applied
  4. Even and Paz's halving, for 4 people. The recursive halving procedure run on a cake valued differently by 4 people: each round's marks and cuts, and the final pieces, each worth at least a 1/4 share to its owner. 8 marks are made.

    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.

    part 4 · applied
  5. 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.

    part 5 · applied
  6. Envy-free up to one item, and up to any: three people, five items. A value matrix for three people, five items with two allocations beneath it: one envy-free up to one item but not up to any, and one envy-free; the counts over all 243 allocations beside it.

    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.

    part 6 · applied
  7. Dividing a rent of 90 three ways, on a 9-step grid. A triangle of possible rent splits, triangulated into 81 small triangles, with each grid point coloured by the room its housemate would pick; 3 small triangles have all three rooms.

    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.

    part 7 · applied
  8. Every envy-free way to split one rent among three rooms. A triangle of rent splits of 90 with the envy-free hexagon (corners 30, 30, 30; 46.7, 21.7, 21.7; 50, 25, 15; 45, 35, 10; 35, 40, 15; 28.3, 33.3, 28.3) and the maximin, equal and grid splits marked.

    A rent nobody envies is not one rent

    Three housemates, three rooms, one rent, and Sperner's lemma promises a split nobody envies. It does not promise one split. For housemates who judge rooms by value for money, the envy-free splits fill a polygon, and in a typical house some room's rent can move across a quarter of the total without anyone envying anyone. Choosing inside it is a second decision. The rule the rent-splitting websites use makes the worst-off housemate as well off as possible, and in almost every house it rewards a housemate who understates what the rooms are worth.

    part 8 · applied
  9. Haggling that ends at the largest product. δ=0.3: player 1 proposes 0.7194, player 2 offers 0.0647; δ=0.6: player 1 proposes 0.5102, player 2 offers 0.1837; δ=0.85: player 1 proposes 0.3887, player 2 offers 0.2809; δ=0.97: player 1 proposes 0.3435, player 2 offers 0.3232; Nash split 0.3333.

    Haggling that ends at the largest product

    Two people split a sum by making offers in turn, each refusal costing both of them a little time. Rubinstein proved in 1982 that the game has exactly one sensible outcome, reached at once — and as the delay between offers shrinks, it is the split that maximises the product of what each gets, the rule Nash had laid down as an axiom thirty years before.

    part 9 · applied
  10. The trades a buyer and seller cannot make. Uniform private values: efficient surplus 1/6; best incentive-compatible, individually rational, budget-balanced mechanism trades iff b − s ≥ 1/4, surplus 9/64 = 27/32 of the efficient.

    Some good trades cannot be made

    A seller who values a car at s meets a buyer who values it at b, and neither knows the other's number. Whenever b is larger, a sale would make both better off. Myerson and Satterthwaite proved in 1983 that no way of haggling, auctioning or brokering can guarantee it: some sales worth making are always lost. With values spread evenly the best possible procedure trades only when the buyer's value beats the seller's by a quarter, loses five thirty-seconds of the surplus — and is reached by two people who simply name prices and split the difference.

    part 10 · applied
  11. Six goods, three people, and no envy. Three people's random values for six goods, with an envy-free allocation shaded: Ada values the bundles at 0.86, 0.85, 0.34; Ben values the bundles at 0.64, 1.83, 0.75; Cy values the bundles at 1.05, 1.24, 1.29.

    Twice as many goods as people

    Indivisible goods with random values cannot always be shared so that nobody envies anybody. With one good each it works only when everyone's favourite is different; with twice as many goods as people it almost always works. Deciding each case exactly shows the chance climbing steeply in between — and a simple draft getting there only when the goods divide evenly.

    part 11 · applied

All series