Basic network creation games

Noga Alon, Erik D. Demaine, Mohammad Taghi Hajiaghayi, Tom Leighton

Research output: Chapter in Book/Report/Conference proceedingConference contribution

35 Scopus citations

Abstract

We study a natural network creation game, in which each node locally tries to minimize its local diameter or its local average distance to other nodes, by swapping one incident edge at a time. The central question is what structure the resulting equilibrium graphs have, in particular, how well they globally minimize diameter. For the local-average-distance version, we prove an upper bound of 2O( √ lg n), a lower bound of 3, a tight bound of exactly 2 for trees, and give evidence of a general polylogarithmic upper bound. For the local- diameter version, we prove a lower bound of Ω( √n), and a tight upper bound of 3 for trees. All of our upper bounds apply equally well to previously extensively studied network creation games, both in terms of the diameter metric de- scribed above and the previously studied price of anarchy (which are related by constant factors). In surprising contrast, our model has no parameter α for the link creation cost, so our results automatically apply for all values of α without additional effort; furthermore, equilibrium can be checked in polynomial time in our model, unlike previous models. Our perspective enables simpler and more general proofs that get at the heart of network creation games.

Original languageEnglish (US)
Title of host publicationSPAA'10 - Proceedings of the 22nd Annual Symposium on Parallelism in Algorithms and Architectures
Pages106-113
Number of pages8
DOIs
StatePublished - 2010
Externally publishedYes
Event22nd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA'10 - Thira, Santorini, Greece
Duration: Jun 13 2010Jun 15 2010

Publication series

NameAnnual ACM Symposium on Parallelism in Algorithms and Architectures

Other

Other22nd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA'10
CountryGreece
CityThira, Santorini
Period6/13/106/15/10

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture

Keywords

  • Nash equilibrium
  • Network design
  • Price of anarchy
  • Routing

Fingerprint Dive into the research topics of 'Basic network creation games'. Together they form a unique fingerprint.

  • Cite this

    Alon, N., Demaine, E. D., Hajiaghayi, M. T., & Leighton, T. (2010). Basic network creation games. In SPAA'10 - Proceedings of the 22nd Annual Symposium on Parallelism in Algorithms and Architectures (pp. 106-113). (Annual ACM Symposium on Parallelism in Algorithms and Architectures). https://doi.org/10.1145/1810479.1810502