Abstract
In the network creation game with n vertices, every vertex (a player) buys a set of adjacent edges, each at a fixed amount α > 0. It has been conjectured that for α ≥ n, every Nash equilibrium is a tree, and has been confirmed for every α ≥ 273·n. We improve upon this bound and show that this is true for every α ≥ 65·n. To show this, we provide new and improved results on the local structure of Nash equilibria. Technically, we show that if there is a cycle in a Nash equilibrium, then α < 65·n. Proving this, we only consider relatively simple strategy changes of the players involved in the cycle. We further show that this simple approach cannot be used to show the desired upper bound α < n (for which a cycle may exist), but conjecture that a slightly worse bound α < 1.3 ·n can be achieved with this approach. Towards this conjecture, we show that if a Nash equilibrium has a cycle of length at most 10, then indeed α < 1.3·n. We further provide experimental evidence suggesting that when the girth of a Nash equilibrium is increasing, the upper bound on α obtained by the simple strategy changes is not increasing. To the end, we investigate the approach for a coalitional variant of Nash equilibrium, where coalitions of two players cannot collectively improve, and show that if α ≥ 41·n, then every such Nash equilibrium is a tree.
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: Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 89–98. ACM, New York (2006)
Alon, N., Demaine, E.D., Hajiaghayi, M.T., Leighton, T.: Basic network creation games. SIAM Journal on Discrete Mathematics 27(2), 656–668 (2013)
Bilò, D., Gualà, L., Proietti, G.: Bounded-distance network creation games. In: Goldberg, P.W. (ed.) WINE 2012. LNCS, vol. 7695, pp. 72–85. Springer, Heidelberg (2012)
Brautbar, M., Kearns, M.: A clustering coefficient network formation game. In: Persiano, G. (ed.) SAGT 2011. LNCS, vol. 6982, pp. 224–235. Springer, Heidelberg (2011)
Demaine, E.D., Zadimoghaddam, M.: Constant price of anarchy in network creation games via public service advertising. In: Kumar, R., Sivakumar, D. (eds.) WAW 2010. LNCS, vol. 6516, pp. 122–131. Springer, Heidelberg (2010)
Demaine, E.D., Hajiaghayi, M., Mahini, H., Zadimoghaddam, M.: The price of anarchy in network creation games. ACM Trans. Algorithms 8(2), 1–13 (2012)
Ehsani, S., Fazli, M., Mehrabian, A., Sadeghian Sadeghabad, S., Safari, M., Saghafian, M., ShokatFadaee, S.: On a bounded budget network creation game. In: Proc. 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 207–214 (2011)
Fabrikant, A., Luthra, A., Maneva, E., Papadimitriou, C.H., Shenker, S.: On a network creation game. In: Proc. 22nd Annual Symposium on Principles of Distributed Computing (PODC), pp. 347–351. ACM, New York (2003)
Mihalák, M., Schlegel, J.C.: The price of anarchy in network creation games is (mostly) constant. Theory Comput. Syst. 53(1), 53–72 (2013)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer International Publishing Switzerland
About this paper
Cite this paper
Mamageishvili, A., Mihalák, M., Müller, D. (2013). Tree Nash Equilibria in the Network Creation Game. In: Bonato, A., Mitzenmacher, M., Prałat, P. (eds) Algorithms and Models for the Web Graph. WAW 2013. Lecture Notes in Computer Science, vol 8305. Springer, Cham. https://doi.org/10.1007/978-3-319-03536-9_10
Download citation
DOI: https://doi.org/10.1007/978-3-319-03536-9_10
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-03535-2
Online ISBN: 978-3-319-03536-9
eBook Packages: Computer ScienceComputer Science (R0)