期刊
SIAM JOURNAL ON DISCRETE MATHEMATICS
卷 27, 期 2, 页码 656-668出版社
SIAM PUBLICATIONS
DOI: 10.1137/090771478
关键词
low diameter; network creation; network design; equilibrium; price of anarchy
资金
- US-Israel BSF grant
- Israel Science Foundation
- ERC Advanced Grant
- Hermann Minkowski Minerva Center for Geometry at Tel Aviv University
- NSF [CCF-1161626, 1053605]
- DARPA/AFOSR grant [FA9550-12-1-0423]
- ONR YIP award [N000141110662]
- University of Maryland Research and Scholarship Award (RASA)
- Division of Computing and Communication Foundations
- Direct For Computer & Info Scie & Enginr [1161626, 1053605] Funding Source: National Science Foundation
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 2(O(root 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 Omega(root 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 a for the link creation cost, so our results effectively apply for all values of alpha 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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据