Say you have $n = m$ identical links, where each agent $i$ has a unit of traffic to push from source to sink, that is, $w_i = 1$.
I've seen it stated, but not shown, that the optimal solution has cost 1.
So why does the optimal solution have a cost of 1?
Full context:
Consider the case where there are n = m agents, each with unit trac, i.e., wi = 1. It is easy to see that the set of uniform strategies with $p_i^j$ = 1/m, for i, j = 1 ... m is a Nash equilibrium. To compute the social cost of the equilibrium we see this as the problem of throwing m balls into m bins. The social cost of the equilibrium is equal to the expected maximum number of balls in a bin which is well known to be (log m= log log m). Given that the optimal solution has cost 1, the lower bound follows.
.... Note: the cost is the expected maximum traffic over all edges.
Note: The bigger context is that we are trying to find a bound on the price of anarchy with 2 players. The part that I posted above is trying to show a lower bound. The price of anarchy is defined as the max(social cost/opt). To prove a lower bound, one of the things the authors showed was that the opt was 1. My question is how they arrived at it.
http://cgi.di.uoa.gr/~elias/publications/paper-kp09.pdf (See part right below theorem 1)
Edit: Social (or overall) optimum is defined as the sum of all delays over all agents.
Some Hints: (hoping that I understand your problem correctly)
You assume $n=m$ and $w_i = 1$ for all $i \in \{1,\dots,n\}$.
Suppose that each individual choses a different link to send her traffic load $w_i$. Is this possible given your assumption?
If it is possible, can you think of any "more optimal" way to convey the amount of traffic through the network, given that optimality is defined in terms of the delay endured by the sender?
If not this situation is optimal right? Then what is the individual cost each sender is enduring in this situation (i.e. when each individual choses a different link to send her traffic load $w_i$)?