3 edited tags

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

$|E|=\mathcal{O}(n^2/\sqrt{\alpha})$

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.

1

# Proof of Upper bound of price of anarchy in local connection game

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!