Expected behavior of an algorithm to minimize rankings
Finding the minimum matching is known as the assignment problem, and it has efficient solutions.
Your exact problem has been considered by Parviainen, Random assignment with integer costs — it's his &quot;Case I&quot;. Parviainen showed that the expected value is between $\frac{\pi^2}{6} n$ and $2n$, and his simulation results suggest an intermediate value $cn$, where $c \approx 1.830$. See also the survey by Krochmal and Pardalos, Random assignment problems.