An assignment problem at high temperature (Q1394528)

The aim of this paper is to prove rigorously some physicists predictions on the so called stochastic assignment problem: given an independent sequence of \(N^2\) i.i.d. (uniform in \([0,1]\)) positive numbers \((a_{i,j})_{i,j \leq N}\), one wants to find \(\min_\sigma \sum_{i \leq N} a_{i,\sigma(i)}\) where the minimum runs over all the permutations \(\sigma\) of \(\{1, \dots, N\}\). Originally, the numbers \(a_{i,j}\) is the cost of assigning a job \(j\) to a worker \(i\). Introducing a Hamiltonian \(H_N(\sigma)=N \sum_{i \leq N} a_{i,\sigma(i)} \) and an inverse temperature \(\lambda\), physicists used ideas from statistical mechanics and spin-glasses theory to predict its behavior. They have in particular predicted that this minimal cost is asymptotically \(\pi^2/6\), and this result has been recently proved by Aldous. This asymptotic behavior is not the only interesting feature of this model and, like in many other spin-glass models, another physicists prediction is that this model is in a high temperature phase for all values of \(\lambda\), i.e. the so called replica-symmetry solution holds and the random variables are in some sense nearly independent under the Gibbs measure defined by the above Hamiltonian. This problem is very difficult to prove rigorously and in similar problems a first step is to prove a ``very high temperature regime'', i.e. that it is true for temperature less than a given \(\lambda_0\). According to the author, this is also very difficult to prove, but he managed to prove a weaker result for a modified model presenting the same features as the original one; in the new model, the Hamiltonian is given for integers \(M,N\) by \(H_{M,N}(\sigma)=N \sum_{i \leq N} a_{i,\sigma(i)}\) where the configuration is now a map \(\sigma\) from \(\{1, \dots, N\}\) to \(\{1 \dots M\}\), with \(N,M\) goes to infinity with a fixed ratio (\(M=[(1+\alpha N)]\), with \(\alpha >0\)). This model appears to be easier and in this case the author proves the very high temperature regime for \(\lambda \leq \lambda_0(\alpha)\) using a new adaptation of the so called cavity method. This method leads to a precise expression of the (infinite volume) free energy, providing thus a rather complete description of the model. According to the author, removing the dependence on \(\alpha\) seems unfortunately to be as difficult as the original problem.