Suppose there are $N$ agents each to be assigned one of $N$ objects. The utility an agent gets for a particular object is drawn uniformly, i.i.d., from the set of integers between $0$ and $100$ inclusive, i.e. $\{0,1,2,\ldots,100\}$, and all of this information is known to us. Our goal as a social planner is simply to assign the objects to people (each agent must receive exactly one object) so as to maximize total social welfare (i.e. the sum of the agent's utilities). The maximum possible total social welfare is then $100N$, but the randomization would have to be very favorable to allow this.
In solving this problem (and similar ones) in Gurobi a few times, I've made the following observations:
As $N$ increases, the expected social welfare of the optimal assignment becomes a larger share of the maximum possible social welfare, that is: $$\frac{d}{dN} \frac{E[\text{Optimal Social Welfare]}}{100N} > 0$$
As $N$ increases, the variance of the optimal social welfare decreases. In particular, for $N=1000$, I have run it five times and each time found an optimal social welfare of $99000$.
The intuition for each of these is fairly straightforward. In the first, we're just benefitting from having more chances to draw a $100$ for each object. The decreasing variance is surely just a direct consequence of LLN. But, two questions:
Why $99000$? Such a nice round number. Is there a way to come up with it explicitly?
Do you think $$\lim_{N \rightarrow \infty} \frac{E[\text{Optimal Social Welfare]}}{100N}=1 ?$$