I'm trying to distill the arguments in the paper "Worst-Case Equilibria" (http://cgi.di.uoa.gr/~elias/publications/paper-kp09.pdf). But there are some things I do not understand and would appreciate some help.
Theorem 1: The price of anarchy for $m$ links is $\Omega(\log(n)/\log(\log(n)))$. For $m = 2$ links, it is at least $\frac{3}{2}$. (note: number of agents $n$ = $m$)
I understand that the social cost (expected maximum amount of traffic) is equal to the problem of throwing $m$ balls into $m$ bins. The paper states $\Theta(\log m/\log\log m)$.
Now here is the part I don't understand: (a) "Given that the optimal solution has cost 1, the lower bound follows." I just don't understand what this sentence means. Maybe someone could reword it. (b) "For $m = 2$, this gives a lower bound of $\frac{3}{2}$." How do you show this? I've tried plugging in $m =2$ into $(\log m/\log \log m)$ but you don't get $\frac{3}{2}$. How do you show how to arrive at lower bound of $\frac{3}{2}$?
One more question (for now): There is a proof that says the expected cost of $c_i$ for agent $i$ is at most $2 - \frac{1}{m}$. But it seems what they prove is: $c_i \leq \frac{\sum_kw_k}{m} + \frac{m-1}{m}w_i$ (Aside: can't get the summation symbol to work.)
I don't see how to go from $c_i \leq \frac{\sum_kw_k}{m} + \frac{m-1}{m}w_i$ to $2 - \frac{1}{m}$.
a)
In this setting, the price of anarchy is
$$\frac{\max_{s \in \mathrm{NE}}\mathrm{cost}(s)}{\mathrm{cost}(\mathrm{OPT})},$$
and to show it is $\Omega(\mathrm{something})$ you need both the nominator and the denominator of appropriate order. The nominator bound $\Omega\left(\frac{\log n}{\log \log n}\right)$ is not enough by itself, you need also that the denominator is $O(1)$. So the bound (also) follows from the fact, that $\mathrm{cost}(\mathrm{OPT}) = 1$, and this is what that sentence means.
b)
The symbols $\Omega$ and $\Theta$ and $O$ notations describe only the order (see e.g. Big $O$ notation), so plugging numbers there isn't very meaningful (at least if you have only one variable). The $\frac{3}{2}$ comes from direct calculation, namely throwing $2$ balls into $2$ bins you have maximum of $2$ and $1$ both with probability $\frac{1}{2}$, hence the expected value is $\frac{2}{2} + \frac{1}{2} = \frac{3}{2}$.
I hope this helps $\ddot\smile$