zbMATH — the first resource for mathematics

On strong equilibria and improvement dynamics in network creation games. (English) Zbl 1405.91077
Devanur, Nikhil R. (ed.) et al., Web and internet economics. 13th international conference, WINE 2017, Bangalore, India, December 17–20, 2017. Proceedings. Cham: Springer (ISBN 978-3-319-71923-8/pbk; 978-3-319-71924-5/ebook). Lecture Notes in Computer Science 10660, 161-176 (2017).
Summary: We study strong equilibria in network creation games. These form a classical and well-studied class of games where a set of players form a network by buying edges to their neighbors at a cost of a fixed parameter $$\alpha$$. The cost of a player is defined to be the cost of the bought edges plus the sum of distances to all the players in the resulting graph. We identify and characterize various structural properties of strong equilibria, which lead to a characterization of the set of strong equilibria for all $$\alpha$$ in the range $$(0,2)$$. For $$\alpha>2$$, N. Andelman et al. [Games Econ. Behav. 65, No. 2, 289–317 (2009; Zbl 1156.91419)] prove that a star graph in which every leaf buys one edge to the center node is a strong equilibrium, and conjecture that in fact any star is a strong equilibrium. We resolve this conjecture in the affirmative. Additionally, we show that when $$\alpha$$ is large enough $$(\geq 2n)$$ there exist non-star trees that are strong equilibria. For the strong price of anarchy, we provide precise expressions when $$\alpha$$ is in the range $$(0,2)$$, and we prove a lower bound of 3/2 when $$\alpha\geq 2$$. Lastly, we aim to characterize under which conditions (coalitional) improvement dynamics may converge to a strong equilibrium. To this end, we study the (coalitional) finite improvement property and (coalitional) weak acyclicity property. We prove various conditions under which these properties do and do not hold. Some of these results also hold for the class of pure Nash equilibria.
For the entire collection see [Zbl 1381.68004].

MSC:
 91A43 Games involving graphs 91A06 $$n$$-person games, $$n>2$$ 05C90 Applications of graph theory
Full Text: