I am looking at the work by Fabrikant "On a Network Connection Game" (http://webcourse.cs.technion.ac.il/236620/Spring2005/ho/WCFiles/FLMPS_netDesign.pdf). This work presents a game-theoretic analysis of a kind of graph growing game.

The idea is each node in a graph can purchase edges to connect itself to other nodes in the graph. An edge costs a fixed amount $\alpha$. Each node wants to minimize the total distance between itself and all other nodes in the graph, while also minimizing the amount it spends on buying edges.

So for a particular strategy for agent i, a cost is incurred

$u_i = \alpha d_i + \sum_{i \neq j} dist(i,j)$,

where $d_i$ is the number of edges the node bought, and $dist(i,j)$ is the distance between nodes $i$ and $j$.

The "social cost" of the network is the sum of all the local costs $C = \sum_i u_i$.

The price of anarchy is defined as the ratio between the worst Nash equilibrium social cost, and the optimal (minimal) social cost of the problem.

In Fabrikants paper, he proves that the Nash equilibrium is at most $\mathcal{O}(\sqrt{\alpha})$ times the optimal social cost (Theorem 1 in his paper).

I am really struggling with the proof, and hoping maybe to get some guidance in here!

The proof is only a few paragraphs long, and the main difficulty is trying to find a bound for the number of possible edges that can exist in a Nash Equilibrium in terms of the edge cost $\alpha$. The proof argues that


and does so by constructing various counting arguments for the edges that can not exist in a Nash equilibrium. Perhaps my trouble is with grasping the "big-Omega" notation, which are in the last 2 main steps of the proof.

Thanks in advance!

  • 1
    $\begingroup$ I am really struggling with the proof is the wrong kind of question to ask on MO. If you can manage to work out precisely what you are stuck on with this proof, and ask that question instead, you are much more likely to get an interesting answer. $\endgroup$ – Thierry Zell May 25 '11 at 23:00
  • $\begingroup$ Hi Thierry, Yes, I was afraid it might not be the best question. I added a few more words, but am not sure I can do better than the paper itself, as the proof is rather short. But I do understand if this will not get the attention I hope for. Thanks $\endgroup$ – dan May 25 '11 at 23:45
  • $\begingroup$ You can refer to the recent progresses of this problem in the following links. link.springer.com/chapter/10.1007/978-3-319-03536-9_17 link.springer.com/chapter/10.1007/978-3-319-03536-9_10 $\endgroup$ – Rupei Xu Mar 8 '14 at 2:49

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.