The price of anarchy in network creation games is (mostly) constant.

*(English)*Zbl 1293.91031A 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 creation cost plus its usage cost. The creation cost of a vertex is \(\alpha\) times the number of built edges. In the SumGame variant, the usage cost of a vertex is the sum of its distances to other vertices in the resulting graph. In the 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 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 SumGame variant, similar techniques to those used for the 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 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 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.

The authors show the following results for the 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 SumGame variant, similar techniques to those used for the 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 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 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.

Reviewer: Abbas Mehrabian (Waterloo)

##### Keywords:

network creation games; Nash equilibrium; price of anarchy; SumGame; MaxGame; equilibrium graph
PDF
BibTeX
XML
Cite

\textit{M. Mihalák} and \textit{J. C. Schlegel}, Theory Comput. Syst. 53, No. 1, 53--72 (2013; Zbl 1293.91031)

Full Text:
DOI

##### References:

[1] | Albers, S.; Eilts, S.; Even-Dar, E.; Mansour, Y.; Roditty, L., On Nash equilibria for a network creation game, 89-98, (2006), New York · Zbl 1192.91036 |

[2] | Alon, N.; Demaine, E.D.; Tom Leighton, M.H., Basic network creation games, 106-113, (2010), New York |

[3] | Bilò, D.; Gualà, L.; Leucci, S.; Proietti, G., The MAX-distance network creation game on general host graphs, 392-405, (2012) · Zbl 1318.68123 |

[4] | Bilò, D.; Gualà, L.; Proietti, G., Bounded-distance network creation games, 72-85, (2012) |

[5] | Brautbar, M.; Kearns, M., A clustering coefficient network formation game, 224-235, (2011) · Zbl 1233.91066 |

[6] | Demaine, E.D.; Hajiaghayi, M.; Mahini, H.; Zadimoghaddam, M., The price of anarchy in network creation games, ACM Trans. Algorithms, 8, 1-13, (2012) · Zbl 1295.68041 |

[7] | Ehsani, S.; Fazli, M.; Mehrabian, A.; Sadeghian Sadeghabad, S.; Safari, M.; Saghafian, M.; ShokatFadaee, S., On a bounded budget network creation game, 207-214, (2011) |

[8] | Fabrikant, A.; Luthra, A.; Maneva, E.; Papadimitriou, C.H.; Shenker, S., On a network creation game, 347-351, (2003), New York · Zbl 1322.91013 |

[9] | Garey, M.R., Johnson, D.: Computers and Intractability: a Guide to the Theory of NP-completeness. Freeman, San Francisco (1979) · Zbl 0411.68039 |

[10] | Jackson, M.O.: Social and Economic Networks. Princeton University Press, Princeton (2008) · Zbl 1149.91051 |

[11] | Jackson, M.O.; Wolinski, A., A strategic model of social and economic networks, J. Econ. Theory, 71, 44-74, (1996) · Zbl 0871.90144 |

[12] | Kawald, B., Lenzner, P.: On dynamics in selfish network creation. CoRR (2012). arXiv:1212.4797 [cs.GT] |

[13] | Lenzner, P., On dynamics in basic network creation games, 254-265, (2011) · Zbl 1233.91071 |

[14] | Lenzner, P., Greedy selfish network creation, 142-155, (2012) |

[15] | Lin, H.: On the price of anarchy of a network creation game (2003). Final class-project · Zbl 1192.91036 |

[16] | Mihalák, M.; Schlegel, J.C., Asymmetric swap-equilibrium: a unifying equilibrium concept for network creation games, 693-704, (2012) · Zbl 1366.91037 |

[17] | Müller, D.: About constricted cycles in Nash equilibria of the local connection game. Semester thesis, ETH, Zurich (2012) |

[18] | Tardos, E.; Wexler, T.; Nisan, N. (ed.); Rougarden, T. (ed.); Tardos, É. (ed.); Vazirani, V. (ed.), Network formation games, (2007), Cambridge |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.