Abstract
We introduce and analyze greedy equilibria (GE) for the well-known model of selfish network creation by Fabrikant et al. [PODC’03]. GE are interesting for two reasons: (1) they model outcomes found by agents which prefer smooth adaptations over radical strategy-changes, (2) GE are outcomes found by agents which do not have enough computational resources to play optimally. In the model of Fabrikant et al. agents correspond to Internet Service Providers which buy network links to improve their quality of network usage. It is known that computing a best response in this model is NP-hard. Hence, poly-time agents are likely not to play optimally. But how good are networks created by such agents? We answer this question for very simple agents. Quite surprisingly, naive greedy play suffices to create remarkably stable networks. Specifically, we show that in the Sum version, where agents attempt to minimize their average distance to all other agents, GE capture Nash equilibria (NE) on trees and that any GE is in 3-approximate NE on general networks. For the latter we also provide a lower bound of \(\tfrac{3}{2}\) on the approximation ratio. For the Max version, where agents attempt to minimize their maximum distance, we show that any GE-star is in 2-approximate NE and any GE-tree having larger diameter is in \(\tfrac{6}{5}\)-approximate NE. Both bounds are tight. We contrast these positive results by providing a linear lower bound on the approximation ratio for the Max version on general networks in GE. This result implies a locality gap of Ω(n) for the metric min-max facility location problem, where n is the number of clients.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Nash Equilibrium
- Approximation Ratio
- Solution Concept
- Facility Location Problem
- Internet Service Provider
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 17th Annual ACM-SIAM Symposium on Discrete Algorithm, SODA 2006, pp. 89–98. ACM, New York (2006)
Albers, S., Lenzner, P.: On Approximate Nash Equilibria in Network Design. In: Saberi, A. (ed.) WINE 2010. LNCS, vol. 6484, pp. 14–25. Springer, Heidelberg (2010)
Alon, N., Demaine, E.D., Hajiaghayi, M., Leighton, T.: Basic network creation games. In: Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2010, pp. 106–113. ACM, New York (2010)
Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., Pandit, V.: Local search heuristics for k-median and facility location problems. SIAM J. Comput. 33(3), 544–562 (2004)
Cord-Landwehr, A., Hüllmann, M., Kling, P., Setzer, A.: Basic Network Creation Games with Communication Interests. In: Serna, M. (ed.) SAGT 2012. LNCS, vol. 7615, pp. 72–83. Springer, Heidelberg (2012)
Demaine, E.D., Hajiaghayi, M., Mahini, H., Zadimoghaddam, M.: The price of anarchy in cooperative network creation games. SIGecom Exch. 8(2), 2:1–2:20 (2009)
Demaine, E.D., Hajiaghayi, M.T., Mahini, H., Zadimoghaddam, M.: The price of anarchy in network creation games. ACM Trans. on Algorithms 8(2), 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: Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2011, pp. 207–214. ACM, New York (2011)
Fabrikant, A., Luthra, A., Maneva, E., Papadimitriou, C.H., Shenker, S.: On a network creation game. In: Proc. of the 22nd Annual Symp. on Principles of Distributed Computing, PODC 2003, pp. 347–351. ACM, New York (2003)
Gulyás, A., Kõrösi, A., Szabó, D., Biczók, G.: On greedy network formation. In: Proceedings of ACM SIGMETRICS Performance W-PIN (2012)
Kariv, O., Hakimi, S.L.: An algorithmic approach to network location problems. ii: The p-medians. SIAM J. on Appl. Math. 37(3), 539–560 (1979)
Lenzner, P.: On Dynamics in Basic Network Creation Games. In: Persiano, G. (ed.) SAGT 2011. LNCS, vol. 6982, pp. 254–265. Springer, Heidelberg (2011)
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.) SAGT 2010. LNCS, vol. 6386, pp. 276–287. Springer, Heidelberg (2010)
Mihalák, M., Schlegel, J.: Asymmetric Swap-Equilibrium: A Unifying Equilibrium Concept for Network Creation Games. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol. 7464, pp. 693–704. Springer, Heidelberg (2012)
Nash, J.F.: Equilibrium points in n-person games. PNAS 36(1), 48–49 (1950)
Vazirani, V.V.: Approximation algorithms. Springer (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lenzner, P. (2012). Greedy Selfish Network Creation. In: Goldberg, P.W. (eds) Internet and Network Economics. WINE 2012. Lecture Notes in Computer Science, vol 7695. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-35311-6_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-35311-6_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-35310-9
Online ISBN: 978-3-642-35311-6
eBook Packages: Computer ScienceComputer Science (R0)