

























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 $α\geq 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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。