The price of anarchy in network creation games is (mostly) constant (Q372985): Difference between revisions

A network creation game is played by \(n\) players \(\{1,2,\dots,n\}\), each identified with a vertex of a graph (network). The strategy of player/vertex \(i\), for \(i=1,\dots,n\), is to build some edges incident to vertex \(i\). The cost of building an edge is a fixed positive parameter \(\alpha\). The strategy profile of the players define a graph. The goal of each player is to minimize its \textit{creation cost} plus its \textit{usage cost}. The creation cost of a vertex is \(\alpha\) times the number of built edges. In the \textsc{SumGame} variant, the usage cost of a vertex is the sum of its distances to other vertices in the resulting graph. In the \textsc{MaxGame} variant, the usage cost of a vertex is its maximum distance to other vertices in the resulting graph. The authors improve bounds on the price of anarchy and give new insights into the structure of equilibrium graphs in both variants of this game. The authors show the following results for the \textsc{MaxGame} variant. First, computing a best response of a player is NP-hard. Then, it is proved that if \(\alpha>129\), every equilibrium graph is a tree (this is a strong structural result), and this implies that the price of anarchy is \(O(1)\). Using a different technique, it is shown that the price of anarchy is always \(\exp\left\{O\left(\sqrt{\log n}\right)\right\}\), and is \(O(1)\) for \(\alpha = O\left(1/\sqrt{n}\right)\). For the \textsc{SumGame} variant, similar techniques to those used for the \textsc{MaxGame} variant give that for \(\alpha > 273n\), every equilibrium graph is a tree (another nice structural result), and this implies the price of anarchy is \(O(1)\) for such \(\alpha\). An important open question in this area is whether the price of anarchy is bounded by a constant for all \(\alpha\). For the \textsc{SumGame}, this paper and previous work imply the answer is ``yes'' as long as \(\alpha \neq C n^{1-\varepsilon(n)}\), where \(C=\Theta(1)\) and \(0 \leq \varepsilon(n) \rightarrow 0\) as \(n\rightarrow \infty\). For the \textsc{MaxGame}, for \(\omega(1/\sqrt{n}) \leq \alpha \leq 129\) the answer is unknown, and the answer is ``yes'' for all other \(\alpha\). It would be interesting to resolve this question for all \(\alpha\), and also to determine whether all equilibrium graphs have logarithmic diameters.