Paper by Erik D. Demaine
- Noga Alon, Erik D. Demaine, MohammadTaghi Hajiaghayi, and Tom Leighton, “Basic Network Creation Games”, in Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2010), Santorini, Greece, June 13–15, 2010, pages 21–29.
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 described 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.
- This paper is also available from the ACM Digital Library.
- Unfortunately the proof of Theorem 5 is flawed, but the theorem is still true. Read our erratum for a correct proof.
- The paper is 8 pages.
- The paper is available in PostScript (388k), gzipped PostScript (155k), and PDF (263k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- BasicNetworkCreation_SIDMA (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
Last updated May 5, 2015 by