How good is an optimal allocation of randomly-valued goods? Suppose we have $n$ items to be given to $n$ people in some permutation (everyone must receive exactly one item). Each person's value for a given item is an independent draw from the uniform distribution on $[0,1]$.
Let $U_n$ be the expected utility (sum of recipient's item values) if we perform the best possible allocation from all $n!$ options, i.e., the average amount of utility we can expect to provide in this scenario if we distribute well.
I'm curious about the asymptotics of $U_n$. It's fairly easy to see that $\lim_{n\to\infty}U_n/n = 1$, since for sufficiently large $n$ we can be $99\%$ confident that $99\%$ of the items are allocated to people who value them at $0.99$ or higher (just assign each item greedily to the first qualifying person).
What's much less clear to me, however, are the second-order terms: how does $n-U_n$ behave? For all I know, the difference could approach $0$.
Edit: There is an argument that the difference is at least $1$ in the limit. The expected maximum value a given person could receive by obtaining their favorite item is $n/(n+1)$, so even by cloning items we could not hope to do better than $n^2/(n+1)=n-1+O(1/n)$.
$U_1$ is obviously $1/2$, and some calculus shows that $U_2=37/30$, but $U_3$ already seems pretty tedious to solve for exactly. If there happens to be a nice formula, I'd love to know about it.
 A: This suboptimal method might give a good lower bound.
Run in several stages.  In the first stage, assign each object to the highest bidder.  Everyone gets to keep their favourite object, and the rest are distributed to those without.  The number remaining after each stage reduces by a factor $exp(1)$.
The value of the first stage is
$$\sum_{k=1}^{\infty}\frac n{ek!}\frac{kn}{kn+1}\\
\approx n(1-\frac1e)-0.4848+O(1/n)$$
That loses about 0.4848 at every stage, fot $\ln n$ stages .
For a second procedure, where everyone keeps a random choice from the objects they won, the value of the first stage is
$$(1-\frac1e)\frac {n^2}{n+1}\\
\approx n(1-\frac1e)-0.632+O(1/n)$$
In either case, the relative value of bids decreases in stage 2 by a factor $n/(n+1)$ because noone in the second stage was ever highest bidder in the first stage.
When the second procedure is run recursively, I found a limit of
$$n-\ln(0.7 n)$$.  Note  that was by summing the formulas, not doing simulations.
The first procedure should do better than that, although it is still not optimal.
EDIT
I ran simulations for the true maximum for $n=2$ to $9$.  A million for $n=2$ to $7$ and a thousand for $n=8$ and $9$.  I found a good fit in this range of $n-0.9\sqrt{\log n}$.
$$\begin{array}{cccc}
   n &   mean   &   n-0.9\sqrt{\log n}&  std dev  \\
   2 &   1.2333 &   1.2507 &   0.3351  \\
    3 &   2.0640 &   2.0567 &   0.3512  \\
    4 &   2.9461 &   2.9403 &   0.3556  \\
    5 &   3.8601 &   3.8582 &   0.3531  \\
    6 &   4.7963 &   4.7953 &   0.3478  \\
    7 &   5.7462 &   5.7445 &   0.3418  \\
    8 &   6.7040 &   6.7022 &   0.3320  \\
    9 &   7.6603 &   7.6659 &   0.3215  
\end{array}$$
