2017/10/04 by Bilò, Davide, Lenzner, Pascal · 1 citation
#Computer Science and Game Theory (cs.GT) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #G.2.2 #Social and Information Networks (cs.SI)
paper · doi:10.48550/arxiv.1710.01782
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 α 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 α and that for α≥ n all equilibrium networks are trees. We introduce a novel technique for analyzing stable networks for high edge-price α and employ it to improve on the best known bounds for both conjectures. In particular we show that for α> 4n-13 all equilibrium networks must be trees, which implies a constant price of anarchy for this range of α. Moreover, we also improve the constant upper bound on the price of anarchy for equilibrium trees.