Applied — page 1

The majority that goes in a circle

Every voter hands in a ranking, and a ranking is transitive by construction. Compare the candidates two at a time and let the majority decide each pair, and the verdicts need not fit together into a ranking at all.

Five rules and five winners

Twenty-seven ranked ballots, five entirely reasonable ways of counting them, and five different candidates declared the winner. Every count is correct, every rule is defensible, and the answer turns out to be a property of the rule rather than of the ballots.

Independence of irrelevant alternatives, broken by Borda. Two profiles that agree on every voter's ranking of two candidates and differ only in where the others sit, with the rule's verdict between the two reversed.

Four conditions, and no rule that has all of them

Five reasonable rules can return five different winners on one set of ballots, which invites the obvious question of which one is right. The answer is that the conditions anybody would write down cannot all hold at once — and here each named rule's own violation is found by search rather than quoted.

Every ballot one voter could submit under instant runoff. One voter's true ranking beside every ranking that voter could submit instead, with the winner each produces and the profitable misreports marked.

A lie that pays

A ballot is usually read as a report of a preference. This one reads it as a move, and walks every move one voter has — all six rankings, the winner each produces, and the ones that beat honesty.

Hamilton's method on 27 seats and 5 regions. A worksheet of populations, exact quotas, floors, remainders and the seats Hamilton's method awards to 5 regions.

The seat that vanishes when the house grows

Twenty-seven whole seats have to be divided between five regions whose exact shares are 15.417, 7.209, 1.755, 1.431 and 1.188. Every rule for rounding those five numbers breaks something, and the instance drawn here breaks all three of the classical ways at once.

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.

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.

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.

One matching that is not stable, and all 24 counted by blocking pairs. An unstable matching with its blocking pair ringed and both members' rankings marked, above an exhaustive census of every matching of the instance by how many blocking pairs it has.

Nobody has a reason to run away

A matching is stable when no two people on opposite sides would both rather have each other than what they have — a condition that names nothing to build and everything to rule out. The surprise is that something always satisfies it, however perverse the rankings are made.

The 4 stable matchings of the instance, ordered by side one's preference. A Hasse diagram of the stable matchings with the best for side one at the top, beside a table giving the join and the meet of every pair.

The side that proposes wins

An instance usually has several stable matchings, and the set of them is not a heap — it is a lattice, closed under taking the better partner and under taking the worse. The two ends of that lattice are exactly what deferred acceptance returns from the two sides, so whoever proposes decides which end the instance lands on.

No stable rule is safe from a lie

A stable matching always exists, and the side that proposes gets the best one it could hope for. This essay closes the story with the result that spoils it — one participant's whole strategy space searched, four submissions found that beat the truth, and a theorem saying no rule anywhere escapes.

Two polytopes, two optima, one number. The feasible regions of a linear program and of its dual, side by side, each with its optimal vertex, and a number line on which the gap between the two optima closes to nothing.

Two numbers that have to meet

Every linear program has a shadow — a second program built from the same numbers read the other way, whose minimum can never fall below the first's maximum. That much is a one-line calculation; the theorem is that the two numbers are always exactly equal.

What one more unit of constraint 1 is worth. The optimum of a linear program plotted against one of its right-hand sides, as an exact piecewise linear graph, with the breakpoints marked and each piece's slope named as a dual variable.

What a constraint is worth

A linear program and its dual reach the same number. What the dual's variables are is a separate question, and the answer converts a solution into a rate for every constraint — piecewise constant, zero on the constraints that are not doing any work.

The value of a 2×3 zero-sum game, named from both sides. The row chooser's expected payoff against each column as a line over the mixing probability, with the lower envelope and its maximum, beside the same construction from the column chooser's side. Both give 19/15.

The value from both sides

Two choosers move at the same instant, and each asks the cautious question — how much can be guaranteed, whatever the other does. With pure choices the two answers are usually different numbers; allow a probability and they are forced to be the same one.

The link that makes every traveller later. Four nodes and two routes, with the equilibrium flow and travel time before a zero-cost link is added between A and B and after. The travel time rises from 10 to 12.

The road that makes everyone later

An equilibrium is a state nobody can improve alone, which is a much weaker thing than a state anybody would choose. Adding a link that costs nothing to use makes every traveller in this network strictly slower, and the arithmetic says by exactly how much.

A table of shares written as a lottery over 3 whole assignments. A doubly stochastic table of shares, and beneath it the permutation matrices and weights that add up to it exactly, each drawn as a grid with one marked cell per row.

A lottery over whole assignments

A table of shares in which every person's shares add to one task and every task is exactly covered is never anything more than a mixture of whole assignments — and finding the mixture is a matter of taking one complete assignment out at a time.

The order everybody arrives in

Three people jointly earn nine, and the question is what each is owed. Ask instead what each adds on walking into a room the others are already in, average that over every order they could have arrived in, and four modest conditions leave no other answer.

The splits no group can beat, for three partners. The triangle of ways to split a fixed total between three players, with each coalition's demand drawn as a straight cut across it, and the region surviving every cut shaded.

A split nobody can walk away from

Every way of dividing what a group earns is a point of a triangle, and every coalition's threat to leave cuts a straight line across it. What survives all the cuts is the set of stable divisions — and for one three-player game there is nothing left.

3 consistent judges, and a majority that is not. A table of judges against three questions, every judge's row internally consistent, with the majority answer to each question underneath forming a combination no judge holds.

The court that contradicts itself

Three judges each answer three questions, and each answers them consistently. Take the majority on each question separately and the answers no longer hang together — the body as a whole endorses a combination no member of it holds, and no rearrangement of the procedure removes the problem.

The quietest loudest complaint in any two of three decide. The triangle of all splits of what a three-player group is worth, with the split minimising the largest excess marked, the average split beside it, and the loudest complaint named.

The objection nobody can make louder

When no split of the winnings survives every group's objection, the core is empty and the question changes — which split makes the loudest objection as quiet as it can be? Sorting the complaints and minimising them in dictionary order picks exactly one split, always, whether or not the core exists.

Drop one condition, and something else satisfies the rest. A column for each of the four conditions, holding a sharing rule that breaks that one and keeps the other three, with the split each rule gives on a stated four-player game.

None of the four conditions is spare

Four conditions pick out one sharing rule. The half that is usually shown is that they are enough; the other half is that each is needed — drop any one and a different rule satisfies the rest, so the list cannot be shortened.

A share of the votes is not a share of the power

Give three members four, four and one vote, with five needed to pass. Every winning coalition needs exactly two of them, so all three have equal power — and one of them holds a ninth of the votes.

Sampling the orders, and how fast the answer arrives. The largest error in the estimated shares against the number of orderings sampled, both on logarithmic axes, with the square-root rate drawn through the first point.

Too many orders to list

The rule is an average over every order the players could have arrived in. At seven players that is five thousand orders and at twenty it is more than there are seconds in the age of the universe — so the average is sampled, and the error falls at a rate that can be measured.

Sharing a cost that is not the sum of its parts

Three users need capacities three, six and twelve of one shared thing, and serving any group costs the largest of them. Averaging what each adds over every order of arrival divides the bill — and for this family the average collapses to a rule anybody could apply by hand.