Upper bound for network connection game when $\alpha > n^2$

16 Views Asked by At

I have proven that when $\alpha > n^2$ every equilibrium must be a tree and that the lower bound for the social cost is $\Omega(\alpha n + n^2)$. I know that the PoA = $O(1)$, so the upper bound must be $O(\alpha n + n^2)$ but I can't prove it. Any kind of help is appreciated.

1

There are 1 best solutions below

0
On

Since $\alpha > n^2$, the lower bound actually is $\Omega(\alpha n)$. As for the upper bound, overestimating the distance for every node we get also $O(\alpha n)$. So, PoA=O(1).