Every essay — page 25
Geometry Analysis Algebra Discrete Topology Probability Number Dynamics Logic Computation Applied What's new Series Concepts Search
Applied
A rule for choosing, stated exactly, and what it forces on whoever adopts it.
The reading that is almost right
Every account of simultaneous choice so far has assumed the payoffs are known to both choosers and known to be known. Replace that with each chooser seeing a private reading off by a little, and a band of equilibria closes to a single point — so the assumption nobody states decides the answer.
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.
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.
The people every stable answer leaves out
Let the lists be short and let one side take several partners. Stable matchings still exist and there can be many of them — but every one leaves out exactly the same people, and a member who is left with an empty place holds exactly the same partners in every one. A three-line count proves it.
A ring that no pairing can break
Put everybody in one pool and a stable pairing may not exist. Allow rings as well as pairs and something stable always exists — and the pairs-only answer fails exactly when that stable arrangement contains a ring of odd length. Two sides make every ring even, which is the whole reason the two-sided theorem holds.
When one of the two numbers is missing
The duality theorem is usually quoted as an equality: a linear program and its dual reach the same number. That is one of four cases. A program can run away to infinity, or have no feasible point at all, and then its dual is forced into a matching failure. Every small program with coefficients from minus one to one has been classified, and the table has exactly four occupied cells out of nine.
The lines the optimum lies under
Change the resources a linear program is given and its best value changes too, tracing a graph. Every solution of the dual is a straight line lying above that graph, and the graph is exactly the lowest of those lines — a bent roof of finitely many planks. Require the answer to be in whole numbers and the roof stays where it was while the graph falls away beneath it in steps, and the space between is the part of the problem no price can see.