Applied — page 4

Tours within half again of the best

Nobody can find the shortest tour through many cities quickly, but a tour at most half as long again as the best can be built in a few steps: the shortest tree, a cheapest pairing of the cities where the tree branches oddly, an Euler circuit, and shortcuts. Nicos Christofides found it in 1976, and for forty-five years nobody could guarantee better. A strip of cities shows the half is really lost, and Laurence Wolsey's reading of the same argument shows it bounds the linear programme too.

What the agenda leaves standing

Ask for a rule that settles each question from the votes on that question, follows a unanimous court and never contradicts itself, and search every such rule for three judges. On a ranking of three options, three survive: one dictator per judge. On two premises and their conjunction, seven survive: every rule in which a fixed set of judges must all agree. On a chain of thresholds, a hundred and twenty-nine, majority among them. The difference is not in the rules. It is in which answers force which, and whether that forcing ever runs back.

Three splits that answer every other

When any two of three people can take a pound, no division of it is safe from a pair walking off. Von Neumann and Morgenstern's answer was not a division but a set of them: three half-and-half splits that never beat one another and between them beat everything else. It is a solution — and so is the line on which one player is held at any fixed share below a half, so the same game has infinitely many, each describing a different settled way of treating the third player.

Prices for things wanted only together

When every buyer wants one thing, there are always prices at which everyone is content with what they get. Let one buyer want two things together and there may be none — and whether there are is decided exactly by whether the market's best fractional allocation beats its best whole one.

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.

Two auctions that earn the same

In one sealed-bid auction the winner pays its own bid; in the other it pays the second-highest bid. Bidders behave completely differently — in the second they bid what the object is worth to them, in the first they shade their bids down by exactly a fraction — and the seller's revenue is spread differently. Yet the seller expects to collect precisely the same amount, (n − 1)/(n + 1) for n bidders with values spread evenly, and so does an auction in which everybody pays. The equality breaks the moment bidders dislike risk, and it says nothing about how much a reserve price can add.

A vote worth nothing until it was outnumbered

From 1958 to 1973 Luxembourg held one vote of seventeen in the Council of the European Communities and could never once change an outcome. When the Council grew, Luxembourg's share of the votes fell and its share of the power rose from nothing. Power is not a quantity a member holds; it is a property of the whole assembly, and changing the assembly moves it in directions nobody would guess.

A third kind of member

Two sides always have a stable matching, and the proof is a procedure. Add a third kind of member — capitals who rank numbers, numbers who rank letters, letters who rank capitals — and every market small enough to check still has a stable grouping. Ten million markets of three have at least ten each. Nobody can prove it continues, because the structure the two-sided proof stands on is gone.

Which vote finds the truth more often

A court that must decide two premises and their conjunction can vote on the premises or on the conclusion, and the two votes sometimes disagree. Suppose there is a right answer and each judge is more often right than wrong. Then the question has an exact answer: for three judges the conclusion vote is more often right when competence is below √½ and the premise vote above it, and in a large court the premise vote wins at any competence — while the conclusion vote turns out to be a built-in standard of proof.

One glove too many

Give some people left gloves and others right ones, and let any group sell the pairs it can make. If the two sides are equal, the core — the splits no group can beat by walking out — is every price at once. If one side has a single glove more, the core is one split: the scarce side takes the whole of every pair and the other side gets nothing, however large the market. The average over orders of arrival barely notices the difference, and the two rules disagree about almost everything a market is.

A market too large to bargain in

Two traders swapping goods can settle anywhere along a stretch of possible deals; nothing forces a price. Bring in a second pair of the same traders and some of those deals can be refused by a group of three. With thirty of each, the only deals no group can refuse lie within a few thousandths of the one a price would produce. Edgeworth guessed in 1881 that competition shrinks bargaining to prices; Debreu and Scarf proved it, and the shrinking can be computed.

Every premise makes the verdict vote stricter

A court that must find several things true before it finds liability can vote on each of them or on the verdict. With two elements, judges right seven times in ten are enough for either. With five, the verdict vote needs judges right eighty-seven times in a hundred, or a larger court makes it worse — while the premise vote still needs only better than even. And when any one ground is enough instead of all, the two procedures swap their failures.

A third of random games have no pure equilibrium

Fill a game's payoff table with random numbers and ask whether some cell is each player's best reply to the other. Exactly one cell is expected to be, at every size, and the chance that none is climbs from one in eight to 1/e — the same constant that counts the shuffles in which nobody gets their own hat back, and for the same reason.

Every random game has an odd number of equilibria

Find every equilibrium of eleven thousand random games — pure and mixed, by trying every pair of strategy sets the players might mix over — and the totals are 1, 3, 5, 7, … and never an even number. The count is a sum of signs: equilibria of index +1 outnumber those of −1 by exactly one in every game. The average grows about 28% with each strategy added, and searching for the game with the most turns up the coordination game's 2ⁿ − 1, a pattern that holds only up to five strategies.

One, plus a quarter, plus a ninth

Give n workers n jobs with every cost drawn at random, average one, and find the cheapest way to pair them. However large n is, the cheapest total averages less than π²/6, and for every n it is exactly 1 + 1/4 + 1/9 + … + 1/n². Parisi guessed the formula in 1998 from n = 1, 2 and 3; thirteen sizes of random tables, solved exactly, land on it within sampling error.

A best reply to the past

Let two players each answer the whole history of the other's play as though it were a fixed plan. In a zero-sum game the history closes in on the equilibrium, as Julia Robinson proved in 1951. In Lloyd Shapley's three-by-three game it never does: play runs round six profiles for ever, each run the one before plus the one three before plus two, so the runs grow by the real root of x³ = x² + 1 and every run is a fixed share of all the history.

Sellers on a street stand back to back

Put two ice-cream sellers on a beach and they end up side by side in the middle, though customers would walk half as far if they stood at the quarter marks. Three sellers never settle at all: whoever is squeezed in the middle leaps outside, for ever. Four stand in pairs, five in pairs with one alone in the centre, six in endlessly many ways. Let them set prices too, with travel costing the square of the distance, and the conclusion reverses: the two sellers move as far apart as the beach allows.

A party that loses every issue can win

Two parties take opposite sides on three issues, and every voter backs the party they agree with on more of them. The party that wins the election can be on the losing side of all three issues — in a fifth of random electorates it loses most of them, and in about one in a hundred it loses every one. A majority of voters can even find themselves outvoted on most of the questions decided. Only when issues are settled by three-to-one majorities on average is that ruled out.

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.

Houses traded in cycles

Everyone owns a house and would rather have someone else's. Let each point at the owner of the house they want most, follow the arrows into a cycle, and trade around it; repeat. The result is the only allocation no group can improve with its own houses, and nobody can gain by lying about what they want — the two guarantees stable matching could not give together.

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.

The cheapest tree costs ζ(3)

Join n towns by every possible road, give each road a cost drawn at random between nought and one, and find the cheapest network of n − 1 roads that connects them all. However many towns there are, the bill tends to 1 + 1/8 + 1/27 + 1/64 + … = 1.2020569. The proof watches the cheap roads arrive one at a time and turns the cost into the area under a curve that counts the pieces of a growing random graph.

A relaxation that answers in halves

The cheapest set of points touching every edge of a graph is hard to find. Allow each point to be taken fractionally and the problem becomes a linear programme — and its best answers are never messier than halves. Every point gets 0, ½ or 1, the 0s and 1s can always be trusted, and the proof is a picture: double the graph into a bipartite one, where a matching decides everything exactly.

A block in an ocean of small holders

A shareholder with 30% of a company whose other shares are scattered among thousands of small holders has, by the average over every order of arrival, 43% of the power to decide — 3/7 exactly, in the limit. The reason is a window of moments: if everyone arrives at a random time, the dispersed shares trickle in at a steady rate, and the block decides every vote in which it turns up while the trickle sits within 30% of the quota. The same picture, run along a diagonal, turns the average over orders into an integral and puts the two classic power indices on one curve.