Abstract
We initiate the study of game dynamics in the Sum Basic Network Creation Game, which was recently introduced by Alon et al.[SPAA’10]. In this game players are associated to vertices in a graph and are allowed to “swap” edges, that is to remove an incident edge and insert a new incident edge. By performing such moves, every player tries to minimize her connection cost, which is the sum of distances to all other vertices. When played on a tree, we prove that this game admits an ordinal potential function, which implies guaranteed convergence to a pure Nash Equilibrium. We show a cubic upper bound on the number of steps needed for any improving response dynamic to converge to a stable tree and propose and analyse a best response dynamic, where the players having the highest cost are allowed to move. For this dynamic we show an almost tight linear upper bound for the convergence speed. Furthermore, we contrast these positive results by showing that, when played on general graphs, this game allows best response cycles. This implies that there cannot exist an ordinal potential function and that fundamentally different techniques are required for analysing this case. For computing a best response we show a similar contrast: On the one hand we give a linear-time algorithm for computing a best response on trees even if players are allowed to swap multiple edges at a time. On the other hand we prove that this task is NP-hard even on simple general graphs, if more than one edge can be swapped at a time. The latter addresses a proposal by Alon et al..
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Albers, S., Eilts, S., Even-Dar, E., Mansour, Y., Roditty, L.: On nash equilibria for a network creation game. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, SODA 2006, pp. 89–98. ACM, New York (2006)
Alon, N., Demaine, E.D., Hajiaghayi, M., Leighton, T.: Basic network creation games. In: SPAA 2010: Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures, pp. 106–113. ACM, New York (2010)
Baumann, N., Stiller, S.: The price of anarchy of a network creation game with exponential payoff. In: Monien, B., Schroeder, U.-P. (eds.) SAGT 2008. LNCS, vol. 4997, pp. 218–229. Springer, Heidelberg (2008)
Demaine, E.D., Hajiaghayi, M., Mahini, H., Zadimoghaddam, M.: The price of anarchy in network creation games. In: Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing, PODC 2007, pp. 292–298. ACM, New York (2007)
Fabrikant, A., Luthra, A., Maneva, E., Papadimitriou, C.H., Shenker, S.: On a network creation game. In: Proceedings of the Twenty-Second Annual Symposium on Principles of Distributed Computing, PODC 2003, pp. 347–351. ACM, New York (2003)
Jackson, M.O.: A survey of models of network formation: Stability and efficiency. Group Formation in Economics: Networks, Clubs and Coalitions (2003)
Kariv, O., Hakimi, S.L.: An algorithmic approach to network location problems. ii: The p-medians. SIAM Journal on Applied Mathematics 37(3), 539–560 (1979)
Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 404–413. Springer, Heidelberg (1999)
Lin, H.: On the price of anarchy of a network creation game. Class final project (2003)
Mihalák, M., Schlegel, J.C.: The price of anarchy in network creation games is (mostly) constant. In: Kontogiannis, S., Koutsoupias, E., Spirakis, P.G. (eds.) Algorithmic Game Theory. LNCS, vol. 6386, pp. 276–287. Springer, Heidelberg (2010)
Monderer, D., Shapley, L.S.: Potential games. Games and Economic Behavior 14(1), 124–143 (1996)
Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.V.: Algorithmic Game Theory. Cambridge University Press, New York (2007)
Voorneveld, M.: Best-response potential games. Economics Letters 66(3), 289–295 (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lenzner, P. (2011). On Dynamics in Basic Network Creation Games. In: Persiano, G. (eds) Algorithmic Game Theory. SAGT 2011. Lecture Notes in Computer Science, vol 6982. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-24829-0_23
Download citation
DOI: https://doi.org/10.1007/978-3-642-24829-0_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-24828-3
Online ISBN: 978-3-642-24829-0
eBook Packages: Computer ScienceComputer Science (R0)