Abstract
The Internet has emerged as perhaps the most important network in modern computing, but rather miraculously, it was created through the individual actions of a multitude of agents rather than by a central planning authority. This motivates the game theoretic study of network formation, and our paper considers one of the most-well studied models, originally proposed by Fabrikant et al. In it, each of n agents corresponds to a vertex, which can create edges to other vertices at a cost of α each, for some parameter α. Every edge can be freely used by every vertex, regardless of who paid the creation cost. To reflect the desire to be close to other vertices, each agent’s cost function is further augmented by the sum total of all (graph theoretic) distances to all other vertices.
Previous research proved that for many regimes of the (α,n) parameter space, the total social cost (sum of all agents’ costs) of every Nash equilibrium is bounded by at most a constant multiple of the optimal social cost. In algorithmic game theoretic nomenclature, this approximation ratio is called the price of anarchy. In our paper, we significantly sharpen some of those results, proving that for all constant non-integral α > 2, the price of anarchy is in fact 1 + o(1), i.e., not only is it bounded by a constant, but it tends to 1 as n → ∞. For constant integral α ≥ 2, we show that the price of anarchy is bounded away from 1. We provide quantitative estimates on the rates of convergence for both results.
Research supported by NSF grants DMS-1201380 and DMS-1041500, an NSA Young Investigators Grant and a USA-Israel BSF Grant.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Fabrikant, A., Luthra, A., Maneva, E., Papadimitriou, C.H., Shenker, S.: On a network creation game. In: Proc. 22nd Symposium on Principles of Distributed Computing, PODC 2003, pp. 347–351 (2003)
Anshelevich, E., Dasgupta, A., Kleinberg, J., Tardos, E., Wexler, T., Roughgarden, T.: The price of stability for network design with fair cost allocation. In: Proc. 45th IEEE Symposium on Foundations of Computer Science, FOCS 2004, pp. 295–304. IEEE Computer Society, Washington, DC (2004)
Anshelevich, E., Dasgupta, A., Tardos, E., Wexler, T.: Near-optimal network design with selfish agents. In: Proc. 35th ACM Symposium on Theory of Computing, STOC 2003, pp. 511–520. ACM, New York (2003)
Czumaj, A., Vöcking, B.: Tight bounds for worst-case equilibria. In: Proc. 13th ACM-SIAM Symposium on Discrete Algorithms, SODA 2002 (2002)
Papadimitriou, C.: Algorithms, games, and the internet. In: Proc. 33rd ACM Symposium on Theory of Computing, STOC 2001, pp. 749–753. ACM, New York (2001)
Roughgarden, T.: The price of anarchy is independent of the network topology. In: Proc. 34th ACM Symposium on Theory of Computing, STOC 2002, pp. 428–437 (2002)
Roughgarden, T.: Selfish Routing and the Price of Anarchy. MIT Press (2005)
Albers, S.: On the value of coordination in network design. In: Proc. 19th ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, pp. 294–303. Society for Industrial and Applied Mathematics, Philadelphia (2008)
Albers, S., Eilts, S., Even-dar, E., Mansour, Y., Roditty, L.: On Nash equilibria for a network creation game. In: Proc. 16th ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, pp. 89–98 (2006)
Alon, N., Demaine, E.D., Hajiaghayi, M., Leighton, T.: Basic network creation games. In: Proc. 22nd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2010, pp. 106–113. ACM, New York (2010)
Andelman, N., Feldman, M., Mansour, Y.: Strong price of anarchy. In: Proc. 18th ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, pp. 189–198. Society for Industrial and Applied Mathematics, Philadelphia (2007)
Corbo, J., Parkes, D.: The price of selfish behavior in bilateral network formation. In: Proc. 24th ACM Symposium on Principles of Distributed Computing, PODC 2005, pp. 99–107. ACM, New York (2005)
Demaine, E.D., Hajiaghayi, M., Mahini, H., Zadimoghaddam, M.: The price of anarchy in network creation games. ACM Transactions on Algorithms 8(2), Paper 13 (April 2012)
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)
Jackson, M.O.: A survey of network formation models: stability and efficiency. In: Demange, G., Wooders, M. (eds.) Group Formation in Economics; Networks, Clubs, and Coalitions. Cambridge University Press (2005)
Tardos, E., Wexler, T.: Network formation games and the potential function method. In: Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.V. (eds.) Algorithmic Game Theory, pp. 487–516. Cambridge University Press (2007)
Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 404–413. Springer, Heidelberg (1999)
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
Graham, R., Hamilton, L., Levavi, A., Loh, PS. (2013). Anarchy Is Free in Network Creation. 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_17
Download citation
DOI: https://doi.org/10.1007/978-3-319-03536-9_17
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-03535-2
Online ISBN: 978-3-319-03536-9
eBook Packages: Computer ScienceComputer Science (R0)