Every essay — page 15
Geometry Analysis Algebra Discrete Topology Probability Number Dynamics Logic Computation Applied What's new Ladders Concepts Search
Computation
A fixed set of operations, and the exact question of what it can and cannot build.
Randomness that has to be earned
A generator that resists prediction cannot be built out of a rule anybody can fit. It has to be built out of a computation believed hard to undo, and the belief is the load-bearing part — which makes cryptographic randomness a conditional statement rather than a construction.
Nineteen thousand bits of state
The generator most simulations actually use is not clever. It is a linear recurrence over the two-element field with an enormous state, and its virtues are a proved period, a proved equidistribution and speed — none of which is unpredictability, which it does not have and does not claim.
One circle, and a straightedge
A straightedge alone cannot bisect a segment, so it cannot draw a parallel, so it can construct almost nothing. Draw one circle anywhere and mark its centre and everything a compass could ever have done becomes available — the circle is never needed again.
The compass that will not open
Fix the compass at one opening and never change it. That looks like a serious loss — a circle of a given radius through a given point is the compass's whole job — and it turns out to cost nothing at all, for reasons that are arithmetic rather than geometric.
Applied
A rule for choosing, stated exactly, and what it forces on whoever adopts it.
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.
Four conditions, and no rule that has all of them
The rung below shows five reasonable rules returning five different winners, 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.
A lie that pays
Three rungs of this ladder have read a ballot 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.
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 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.
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.
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 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 ladder 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 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 a constraint is worth
The rung below settled that a linear program and its dual reach the same number. This one asks what the dual's variables are, 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 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 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 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.
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.
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 asserts a combination no member of it holds, and no rearrangement of the procedure removes the problem.
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.