2026-07-22T11:58:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8509 2024-03-06T10:42:17Z ddc:004 open_access

On the Tree Conjecture for the Network Creation Game Bilò, Davide Lenzner, Pascal Algorithmic Game Theory Network Creation Game Price of Anarchy Quality of Nash Equilibria 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.[PODC'03] 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 bounds for both conjectures. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Davide Bilò and Pascal Lenzner 2018 Is Part Of LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2018.14 urn:nbn:de:0030-drops-85092 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.14 eng https://creativecommons.org/licenses/by/3.0/legalcode