The $\zeta(2)$ Limit in the Random Assignment Problem
David Aldous
The random assignment (or bipartite matching) problem asks about
$ A_n = \min_\pi \sum_{i=1}^n c(i,\pi(i)) $,
where $(c(i,j))$ is a $n \times n$ matrix with i.i.d. entries,
say with exponential(1) distribution, and the minimum is over
permutations $\pi$. M\'{e}zard and Parisi (1987)
used the replica method from statistical physics to argue
non-rigorously that $EA_n \to \zeta(2) = \pi^2/6$.
Aldous (1992) identified the limit in terms of a matching problem
on a limit infinite tree. Here we construct the optimal matching
on the infinite tree. This yields a rigorous proof of the $\zeta(2)$
limit and of the conjectured limit distribution of edge-costs and
their rank-orders in the optimal matching.
It also yields the asymptotic essential uniqueness property:
every almost-optimal matching coincides with the optimal matching
except on a small proportion of edges.