On the tree conjecture for the network creation game
type: Item
instance of: scholarly article
title: On the tree conjecture for the network creation game
zbMATH Open document ID: 1443.91071
author: D. Bilò
author: Pascal Lenzner
published in: Theory of Computing Systems
publication date: 2020-04-15T00:00:00Z
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/8509/
review text: The paper focuses on modeling real world networks from a game-theoretic point of view. In the network creation game agents correspond to nodes in a network and buy incident edges for the price of \(\alpha\) per edge to minimize their total distance to all other nodes. The price of anarchy PoA is the ratio of the overall network quality of the worst possible outcome of the uncoordinated network creation process and the network quality of the centrally designed optimal network. It was conjectured that the price of anarchy is constant for all \(\alpha\) and that for \(\alpha\ge n\) all equilibrium networks are trees. Authors introduce a new technique for analyzing stable non-tree networks for high edge-price \(\alpha\) and use it to improve on the current best lower bound for \(\alpha\) for which all stable networks must be trees. They prove that for \(\alpha > 4n-13\) any stable network must be a tree, a significant improvement over the known bound of \(\alpha > 65n\) by \textit{A. Mamageishvili} et al. [Lect. Notes Comput. Sci. 8305, 118--129 (2013; Zbl 1342.05169)] and the recently claimed bound of \(\alpha > 17n\) by \textit{C. Álvarez} and \textit{A. Messegué} [``Network creation games: structure vs anarchy'', Preprint, \url{arXiv:1706.09132}]. Since it is known that the PoA for stable tree networks is constant, this new bound directly implies a constant PoA for \(\alpha > 4n-13\). Their new technique exploits properties of cycles in stable networks by focusing on critical pairs, strong critical pairs and min cycles. The main new contribution is revelation of a rich combinatorial structure within any non-tree Nash equilibrium (NE) network for \(\alpha > 2n-6\). Authors show that in this case any agent in any min cycle with a certain minimum length owns exactly one edge of the respective min cycle. As a result the biconnected component of any non-tree NE network cannot be a cycle and thus must contain two nodes with are situated in a particular critical pair config…
reviewed by: Vladimír Lacko
Mathematics Subject Classification ID: 91A43
Mathematics Subject Classification ID: 91A68
Mathematics Subject Classification ID: 05C90
zbMATH DE Number: 7189479
zbMATH Keywords: algorithmic game theory
zbMATH Keywords: price of anarchy
zbMATH Keywords: network creation games
zbMATH Keywords: tree conjecture
Wikidata QID: Q123278625
MaRDI profile type: Publication
OpenAlex ID: W2967142389
cites work: Basic network creation games
cites work: Celebrity games
cites work: Max celebrity games
cites work: On the price of anarchy for high-price links
cites work: Strong price of anarchy
cites work: Friend of my friend: network formation with two-hop benefit
cites work: A Noncooperative Model of Network Formation
cites work: Q3452868
cites work: Network Creation Games with Traceroute-Based Strategies
cites work: The max-distance network creation game on general host graphs
cites work: On the Tree Conjecture for the Network Creation Game
cites work: Selfish network creation with non-uniform edge cost
cites work: On Selfish Creation of Robust Networks
cites work: The price of selfish behavior in bilateral network formation
cites work: Network Creation Games: Think Global – Act Local
cites work: Quality of Service in Network Creation Games
cites work: Q3651735
cites work: On Strong Equilibria and Improvement Dynamics in Network Creation Games
cites work: The price of anarchy in network creation games
cites work: The Price of Anarchy in Cooperative Network Creation Games
cites work: A Bounded Budget Network Creation Game
cites work: On a network creation game
cites work: Efficient best response computation for strategic network formation under attack
cites work: Strategic Network Formation with Attack and Immunization
cites work: Anarchy Is Free in Network Creation
cites work: Q3063920
cites work: A strategic model of social and economic networks
cites work: The complexity of the network design problem
cites work: An Algorithmic Approach to Network Location Problems. II: Thep-Medians
cites work: The small-world phenomenon
cites work: The price of anarchy for network formation in an adversary model
cites work: Q3409969
cites work: On Dynamics in Basic Network Creation Games
cites work: Tree Nash Equilibria in the Network Creation Game
cites work: Asymmetric Swap-Equilibrium: A Unifying Equilibrium Concept for Network Creation Games
cites work: The price of anarchy in network creation games is (mostly) constant
cites work: Algorithms, games, and the internet
DOI: 10.1007/S00224-019-09945-9
description: scientific article; zbMATH DE number 7189479