Paper by Erik D. Demaine

Noga Alon, Erik D. Demaine, MohammadTaghi Hajiaghayi, and Tom Leighton, “Basic Network Creation Games”, SIAM Journal on Discrete Mathematics, volume 27, number 2, 2013, pages 656–668.

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. 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 previous models. Our perspective enables simpler proofs that get at the heart of network creation games.

This paper is also available from SIAM.

Unfortunately the proof of Theorem 5 is flawed, but the theorem is still true. Read our erratum for a correct proof.

The paper is 13 pages.

The paper is available in PostScript (713k), gzipped PostScript (340k), and PDF (380k).
See information on file formats.
[Google Scholar search]

Related papers:
BasicNetworkCreation_SPAA2010 (Basic Network Creation Games)
CooperativeNetworkCreation_SIGecom (The Price of Anarchy in Cooperative Network Creation Games)
NetworkCreation_TALG (The Price of Anarchy in Network Creation Games)

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated June 13, 2024 by Erik Demaine.