TY - GEN

T1 - Basic network creation games

AU - Alon, Noga

AU - Demaine, Erik D.

AU - Hajiaghayi, Mohammad Taghi

AU - Leighton, Tom

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

KW - Nash equilibrium

KW - Network design

KW - Price of anarchy

KW - Routing

UR - http://www.scopus.com/inward/record.url?scp=77954942810&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77954942810&partnerID=8YFLogxK

U2 - 10.1145/1810479.1810502

DO - 10.1145/1810479.1810502

M3 - Conference contribution

AN - SCOPUS:77954942810

SN - 9781450300797

T3 - Annual ACM Symposium on Parallelism in Algorithms and Architectures

SP - 106

EP - 113

BT - SPAA'10 - Proceedings of the 22nd Annual Symposium on Parallelism in Algorithms and Architectures

T2 - 22nd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA'10

Y2 - 13 June 2010 through 15 June 2010

ER -