Basic network creation games

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

Research output: Contribution to journalArticle

29 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, and 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. The same bounds apply, up to constant factors, to the price of anarchy. Our network creation games are closely related to the previously studied unilateral network creation game. The main difference is that our model has no parameter α for the link creation cost, so our results effectively apply for all values of αwithout additional effort; furthermore, equilibrium can be checked in polynomial time in our model, unlike in previous models. Our perspective enables simpler proofs that get at the heart of network creation games.

Original languageEnglish (US)
Pages (from-to)656-668
Number of pages13
JournalSIAM Journal on Discrete Mathematics
Volume27
Issue number2
DOIs
StatePublished - 2013
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

  • Equilibrium
  • Low diameter
  • Network creation
  • Network design
  • Price of anarchy

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. (2013). Basic network creation games. SIAM Journal on Discrete Mathematics, 27(2), 656-668. https://doi.org/10.1137/090771478