One, plus a quarter, plus a ninth

The assignment problem has already been solved several ways: as a price for every person and task, where a set of prices certifies the cheapest pairing; as an auction in prices the bidders raise; and as a corner of the polytope of lotteries over whole assignments. Each of those essays took one table of costs and found its best assignment. This one takes a table of random costs, finds its best assignment exactly, and asks what that best cost is on average — and the answer is one of the most surprising exact results in probability.

Draw every one of the $n^2$ costs independently from the exponential distribution with mean one. The best total, averaged over all such tables, is exactly

$$1 + \frac14 + \frac19 + \cdots + \frac1{n^2}.$$

For one worker and one job that is the mean of a single cost, one. For two it is $5/4$, and for three it is $49/36$. As $n$ grows it climbs towards $\pi^2/6 \approx 1.645$ and never gets there. A table of a million workers and a million jobs, a trillion random costs, has a best assignment that costs on average less than $1.645$ in total, although each worker’s own cheapest job costs on average one millionth and the obvious ways of pairing them up cost far more.

Solving each table exactly #

Every figure below rests on solving many random tables exactly, and the method is the one a price for every person and task explained: the Hungarian method, in the shortest-augmenting-path form that runs in time proportional to $n^3$. It keeps a price on every row and every column and adds workers one at a time, rerouting along the cheapest chain of reassignments, and when it finishes the prices are a certificate. Every cost, minus its row’s price and its column’s price, is at least nought, and the costs used are exactly nought after subtraction. By duality that proves no other assignment is cheaper, without comparing it with any of the others. The first twenty tables at every size were checked against their certificates, and the hero table, small enough for the alternative, was checked against all 5,040 permutations.

The tables in the figure above show what the method is up against. The seven-by-seven table has seven cells below a tenth, but three of them are in the same column — job 2 is the cheapest job for workers 1, 2 and 3 alike — so the cheapest assignment cannot use them all. The best total, $0.748$, is a compromise in which some workers get their cheapest job and others their second or third, and the average over all seven-by-seven tables is $1.5118$. Each figure below averages thousands of these compromises: forty thousand tables at the smallest sizes, three hundred at size one hundred, every one solved to optimality.

The formula, size by size #

The next figure is the test of the formula. At each of thirteen sizes from one to a hundred, the average best total of many random tables is plotted with bars of two standard errors, against Parisi’s sum.

Every average lies on the curve. At size two the sample mean is $1.2509$ against $1.25$; at size seven, $1.5131$ against $1.5118$; at size fifty, $1.6259$ against $1.6251$. Measured in standard errors, the largest gap at any of the thirteen sizes is $1.5$, which is what sampling alone produces, and the gaps go both ways. The figure cannot prove the formula, since a sample mean never pins down an expectation exactly, but it rules out every nearby alternative: a formula that differed from Parisi’s by as little as half a per cent at size thirty would have shown up as a gap of several standard errors.

The history of the formula is the reason to test it. Giorgio Parisi, working on the statistical physics of disordered systems, computed the expectation for $n = 1$, 2 and 3 exactly in 1998 and noticed that the answers were $1$, $1 + 1/4$ and $1 + 1/4 + 1/9$. He conjectured that the pattern continues. It is the kind of conjecture that usually fails, since three terms of a sequence fit many formulas, and a stronger version was proposed, by Don Coppersmith and Gregory Sorkin, covering partial assignments of $k$ workers to $k$ jobs in a larger table. Both were proved in 2004, independently, by Svante Linusson and Johan Wästlund and by Chandra Nair, Balaji Prabhakar and Mayank Sharma, by arguments that compute the expectation of the optimum one augmenting step at a time.

Two workers, exactly #

The smallest interesting case can be done by hand, and doing it shows why the formula is surprising rather than obvious.

With two workers there are two assignments, worker one to job one with worker two to job two, or the crossed pair. Each total is a sum of two independent exponential costs, which exceeds $x$ with probability $(1 + x)e^{-x}$, and the best total exceeds $x$ only if both do, with probability $(1 + x)^2 e^{-2x}$. The expected value is the integral of that probability over all $x$,

$$\int_0^\infty (1 + x)^2 e^{-2x}\,dx = \frac12 + \frac12 + \frac14 = \frac54,$$

and forty thousand random tables average $1.25088$. The calculation produces exactly $1 + 1/4$, but it produces it as $1/2 + 1/2 + 1/4$, and there is nothing in it that suggests $1/9$ comes next. At $n = 3$ there are six assignments sharing costs in complicated ways, and the exact calculation that gives $49/36$ is already long. The formula is not visible in the cases; it is a pattern among their answers. That is what made Parisi’s guess bold, and why the proofs, when they came, had to find a structure the brute-force calculations did not display.

Building the assignment a pair at a time #

The calculation for two workers can be reorganised in a way that does generalise, and the reorganisation is the shape of the proofs. Instead of asking for the best complete assignment at once, ask for the best way to place $k$ pairs, for $k = 1, 2, \ldots$, each a partial assignment using $k$ distinct workers and $k$ distinct jobs. Coppersmith and Sorkin’s conjecture, the form that was proved, says that in an $m \times n$ table the cheapest $k$ pairs cost on average

$$\sum_{\substack{i, j \ge 0 \\ i + j < k}} \frac{1}{(m - i)(n - j)}.$$

For a two-by-two table and $k = 2$ the sum has three terms: $i = j = 0$ gives $1/4$, and $i = 1, j = 0$ and $i = 0, j = 1$ give $1/2$ each. That is the $1/2 + 1/2 + 1/4$ of the integral above, term for term. For a three-by-three table and $k = 3$ there are six terms, $1/9 + 1/6 + 1/6 + 1/3 + 1/3 + 1/4$, which add to $49/36$, Parisi’s $1 + 1/4 + 1/9$. In general the terms with a fixed $i + j$ rearrange into reciprocal squares, and the whole double sum telescopes into $\sum 1/k^2$.

The shape of the double sum has a reading that explains why it is small. The cheapest single pair is the minimum of $mn$ exponential costs, whose mean is $1/(mn)$ — the term $i = j = 0$. Adding a second pair means finding the cheapest extension, which may have to reroute the first pair, and the extension’s expected cost is the sum of the terms with $i + j = 1$: the chance that the new worker is fresh, times one over the remaining choices, and so on. Each term corresponds to a way the augmenting step can use up rows and columns. The memorylessness of the exponential is what makes each of these terms a simple reciprocal: given what the cheapest $k - 1$ pairs revealed about the costs, the costs not yet examined are still exponential, shifted but not reshaped.

None of this is how the Hungarian method finds an assignment; it is how a proof averages over all of the method’s possible runs at once. But the method and the proof share the step that matters. Both build the optimum by augmenting a partial assignment one pair at a time, and both rely on linear programming’s guarantee that the cheapest fractional assignment is a whole one, so that prices, rather than a search over permutations, can certify each step.

Nearly fixed, not merely bounded #

The average is bounded, but an average could hide a wide spread. The next figure measures the spread, as the variance of the best total multiplied by the size.

The product settles near $1.77$, which is the limit Johan Wästlund proved in 2005: the variance is about $(4\zeta(2) - 4\zeta(3))/n$, where $\zeta(2) = \pi^2/6$ and $\zeta(3) = 1.2021$ is the sum of reciprocal cubes that a tail too small to be a whole number met as Apéry’s constant. So the standard deviation falls like $1/\sqrt n$, about $0.13$ at size one hundred, and the best total of a single large table is a reliable estimate of $\pi^2/6$ on its own. The optimum is a sum of $n$ costs, each of order $1/n$, chosen from $n^2$ random numbers, and it behaves like an average: large tables all have nearly the same best total, in the way that the law of large numbers makes averages settle.

What the optimum uses #

The total is one number. The assignment that achieves it is $n$ choices, and the next figure looks at what kind of choices they are: for each worker, where the job given ranks among that worker’s own costs.

In large tables, half the workers get their cheapest job, a quarter their second cheapest, an eighth their third, and so on, halving at every step: at size one hundred the shares are $0.503$, $0.254$, $0.126$ and $0.061$. Smaller tables lean further towards the cheapest choice, two thirds of workers getting it at size three, because a small table has fewer conflicts. The halving is a prediction of the object David Aldous built in 2001 to prove that the limit is $\pi^2/6$: an infinite random tree describing what an optimal assignment looks like near one worker in an infinitely large table, in which each worker’s options are the points of a Poisson process and the optimal matching is decided by a recursive equation. That a worker gets their $k$-th cheapest option with probability $2^{-k}$ is one of its consequences, and the figure shows tables of a hundred already obeying it.

The halving also explains why the total is small. Most workers get one of their two or three cheapest jobs, and a worker’s $k$-th cheapest job costs about $k/n$, so each contributes a few multiples of $1/n$ and the $n$ of them together a total of order one.

Greed, and other costs #

The obvious way to pair workers with jobs is to take the cheapest remaining pair, assign it, remove that worker and that job, and repeat. The last figure compares that with the optimum, and also asks whether the exponential distribution matters.

The greedy rule does well at first — the first pairs it takes are the cheapest in the whole table — and then pays for it. As workers and jobs are removed the cheap cells left are in the wrong places, and the last few pairs are forced, at whatever they cost. Its average grows without bound, by roughly two thirds of a unit each time the size doubles: $2.92$ at size ten, $5.25$ at size one hundred, more than three times the optimum. The optimum avoids that by being willing to give a worker a slightly worse job early so that no one is left with an expensive one late, and that willingness is what the prices of the Hungarian method encode.

An even simpler greedy rule makes the contrast exact. Let the workers choose in turn, each taking the cheapest job still free. The first chooses among $n$ fresh costs and pays their minimum, whose mean is $1/n$; the second among $n - 1$ fresh costs in their own row, paying $1/(n - 1)$ on average; and the last worker gets whatever is left, a single cost of mean one. The total averages exactly

$$\frac1n + \frac1{n-1} + \cdots + 1 = 1 + \frac12 + \cdots + \frac1n,$$

the harmonic number, which grows like $\ln n$ and has no limit. Taking turns costs the harmonic series; cooperating optimally costs the series of reciprocal squares. The difference between the two series — one diverging, the other converging to $\pi^2/6$ — is the whole value of solving the assignment problem rather than letting the workers queue.

Uniform costs, spread evenly between nought and one, give a different average at every finite size — $0.494$ at size one, since the mean of a single uniform cost is a half, and $1.604$ at size one hundred — but they approach the same limit. Aldous’s theorem says why: in a large table the optimum only ever uses costs of order $1/n$, so all that matters is how likely costs are to be near nought, and both distributions have density one there. The exact formula, by contrast, belongs to the exponential, whose lack of memory is what the proofs use at every augmenting step.

What the tables cannot show #

The figures are averages over finitely many random tables of size at most a hundred. They establish that the formula fits at thirteen sizes to within the sampling error, and that the variance and the halving behave as the limit theory predicts at the sizes drawn. They do not show what happens at sizes they did not reach, and the convergence to $\pi^2/6$ is slow — at size one hundred the average is still $0.01$ short, since the tail $\sum_{k > n} 1/k^2$ is about $1/n$. A computation could never distinguish $\pi^2/6$ from a nearby constant at the sizes that can be solved; the identification is a theorem.

Nor do the figures show why the answer is a sum of reciprocal squares. The proofs of Linusson and Wästlund and of Nair, Prabhakar and Sharma are computations, organised so that each augmenting step contributes one term, and the term $1/k^2$ arises from the memoryless property of the exponential at each step. They establish the formula and do not make it inevitable. That the same number, $\pi^2/6$, is the sum Euler found by rebuilding the sine from its zeros is a coincidence of the formula rather than a connection anyone has explained geometrically.

Still open: other shapes of problem #

The assignment problem is the one random optimisation problem whose finite-size answer is known exactly. Its neighbours are not so lucky. The random travelling salesman problem on the same kind of table — the cheapest tour visiting every city, with independent random costs between cities — has a limit, about $2.0415$, computed from the same kind of recursive equation Aldous used and proved to be correct by Wästlund in 2010; but no exact formula for finite sizes is known, and the constant has no closed form. The minimum spanning tree with random edge costs has the limit $\zeta(3)$, found by Alan Frieze in 1985, and exact finite formulas only in special cases.

For assignments themselves, the open questions concern costs that are not independent. When the costs are distances between random points in the plane — workers and jobs placed at random in a square, each paired to a job at minimum total distance — the optimum grows in a way governed by geometry rather than by the arithmetic of reciprocals, and its constant is not known exactly in any dimension.

A sum anyone could have guessed #

Parisi’s formula is the kind of result that looks like numerology until it is proved. The cheapest assignment in a random table is a hard object: it depends on all $n^2$ costs at once, the best choice for each worker depends on every other worker’s, and the obvious greedy method gets it wrong by a margin that grows without bound. Yet its average is $1 + 1/4 + 1/9 + \cdots$, a sum that a student meets in the first week of studying series, and its limit is the number Euler found in 1734. The thirteen sizes in the figure, from forty thousand tables of one to three hundred tables of a hundred, sit on that sum to within the error of sampling, and the waiting-for-all-coupons sum that how long until every one turns up found for random draws is, by comparison, the harmonic series itself. Pairing costs a convergent series where collecting costs a divergent one.