Matpic
mathematics, in pictures
Concept

Proportionality

The property of a division among n people that each of them values their own share at a full nth of the whole or more. It is the weaker of the two standard fairness conditions, and unlike envy-freeness it can be achieved by a simple moving-knife procedure.

Named by 6 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 Seats to districts and to parties at once. A 4 by 3 table of seats, with every row total and every column total prescribed. The entries come from scaling the votes by one factor per row and one per column and rounding, and all the totals come out exactly right.

Seats to parties and places at once

Seats can be given to regions in proportion to one list of populations, and no rule does it perfectly. Ask for seats to regions and to parties simultaneously and the object stops being a list — and the impossibility that closed the subject does not apply.

applied · Apportionment Biproportional seats against their fair shares. A table of votes for 3 districts and 4 parties beside the seats the biproportional method gives, each with the fair share from the continuous fit, and the cell whose seats fall outside its quota marked.

The table inside every quota

Give seats to districts and parties at once, and every cell of the table has a fair share it ought to round from. A table rounding every cell to its floor or its ceiling, with every total exact, always exists. The biproportional method does not always choose one: here it gives a party 2 seats where its fair share is 3.088.

applied · Apportionment 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.

applied · Fair division

Named alongside it

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

Divide and chooseFair divisionValuation measureEnvy-freenessApportionmentCounting argumentDivisor methodExistence proofFairnessImpossibilityMatrixMoving knife

All concepts