Filtern
Volltext vorhanden
- nein (1)
Erscheinungsjahr
- 2019 (1)
Dokumenttyp
Sprache
- Englisch (1)
Gehört zur Bibliographie
- ja (1)
Schlagworte
- tree conjecture (1) (entfernen)
Institut
- Hasso-Plattner-Institut für Digital Engineering gGmbH (1) (entfernen)
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.