From theorem 3 in http://cgi.di.uoa.gr/~elias/publications/paper-kp09.pdf
Let $w_1$,$w_2$ = 1. I have interpreted the above paper as saying that the social cost is the same thing as the expected cost of the max load over all links (or machines). Later on, it says the social cost is the $\sum_iq_iw_i$, where $q_i$ is called the contribution probability, and it is the probability $i$'s workload goes to the link of maximum load. I do not understand how this can be true.
To see where my confusion is, this is how I calculated the social cost without using the contribution probability $q_i$. Social cost = 3*.5+ 1*.5 = 1.5. From that we see that is a 1/2 a chance of either agent colliding with the other one. So .5*1+.5*1 = 1, which is not the same as 1.5.
I can't claim to have read the paper, and the below may not be accurate :) Still, hope you can make something of it!
You seem be talking specifically about the case of n = m = 2, two agents and two links, in the mixed strategy Nash Equilibrium with each agent choosing each link with probability 1/2.
I assume that you meant to write: Social cost = 2 * .5 + 1 * .5 = 1.5.
As you say, q_i is the probability i's workload goes to the link of maximum load. But see that Theorem 3 goes further, "if there is more than one maximum load link, we consider the lexicographically first such link."
There is a probability 1/2 that agent 1 chooses the same link as does agent 2. That link will be the maximum load link, having load 2. In that case we say that agent 1 has selected the maximum load link.
But there is a probability 1/4 that agent 1 chooses link 1 and agent 2 chooses link 2. Both links will be maximum load links, each having load 1. But we say that agent 1 has selected the lexicographically first such link.
Thus q1 = 1/2 + 1/4 = 3/4 (and equally q2 = 3/4). q1 * w1 + q2 * w2 = 3/4 * 1 + 3/4 * 1 = 3/2.