TY  - GEN
A1  - Bilo, Davide
A1  - Friedrich, Tobias
A1  - Lenzner, Pascal
A1  - Melnichenko, Anna
T1  - Geometric Network Creation Games
T2  - SPAA '19: The 31st ACM Symposium on Parallelism in Algorithms and Architectures
N2  - Network Creation Games are a well-known approach for explaining and analyzing the structure, quality and dynamics of real-world networks like the Internet and other infrastructure networks which evolved via the interaction of selfish agents without a central authority. In these games selfish agents which correspond to nodes in a network strategically buy incident edges to improve their centrality. However, past research on these games has only considered the creation of networks with unit-weight edges. In practice, e.g. when constructing a fiber-optic network, the choice of which nodes to connect and also the induced price for a link crucially depends on the distance between the involved nodes and such settings can be modeled via edge-weighted graphs. We incorporate arbitrary edge weights by generalizing the well-known model by Fabrikant et al. [PODC'03] to edge-weighted host graphs and focus on the geometric setting where the weights are induced by the distances in some metric space. In stark contrast to the state-of-the-art for the unit-weight version, where the Price of Anarchy is conjectured to be constant and where resolving this is a major open problem, we prove a tight non-constant bound on the Price of Anarchy for the metric version and a slightly weaker upper bound for the non-metric case. Moreover, we analyze the existence of equilibria, the computational hardness and the game dynamics for several natural metrics. The model we propose can be seen as the game-theoretic analogue of a variant of the classical Network Design Problem. Thus, low-cost equilibria of our game correspond to decentralized and stable approximations of the optimum network design.
KW  - Network creation games
KW  - edge-weighted networks
KW  - price of anarchy
KW  - Nash equilibrium
KW  - game dynamics
KW  - computational hardness
Y1  - 2019
SN  - 978-1-4503-6184-2
U6  - https://doi.org/10.1145/3323165.3323199
SP  - 323
EP  - 332
PB  - Association for Computing Machinery
CY  - New York
ER  - 
TY  - JOUR
A1  - Bilò, Davide
A1  - Lenzner, Pascal
T1  - On the tree conjecture for the network creation game
JF  - Theory of computing systems
N2  - Selfish Network Creation focuses on modeling real world networks from a game-theoretic point of view. One of the classic models by Fabrikant et al. (2003) is the network creation game, where agents correspond to nodes in a network which buy incident edges for the price of alpha per edge to minimize their total distance to all other nodes. The model is well-studied but still has intriguing open problems. The most famous conjectures state that the price of anarchy is constant for all alpha and that for alpha >= n all equilibrium networks are trees. We introduce a novel technique for analyzing stable networks for high edge-price alpha and employ it to improve on the best known bound for the latter conjecture. In particular we show that for alpha > 4n - 13 all equilibrium networks must be trees, which implies a constant price of anarchy for this range of alpha. Moreover, we also improve the constant upper bound on the price of anarchy for equilibrium trees.
KW  - network creation games
KW  - price of anarchy
KW  - tree conjecture
KW  - algorithmic
KW  - game theory
Y1  - 2019
U6  - https://doi.org/10.1007/s00224-019-09945-9
SN  - 1432-4350
SN  - 1433-0490
VL  - 64
IS  - 3
SP  - 422
EP  - 443
PB  - Springer
CY  - New York
ER  -