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 -