An improved bound for the tree conjecture in network creation games

DOI10.1007/978-3-031-15714-1_14MaRDI QIDQ6109522zbMATH OpenOpenAlexFDO

Authors Jack Dippel, Adrian Vetta

Publication date 28 July 2023

Published in Algorithmic Game Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2106.05175

zbMATH Keywords

algorithmic game theorynetwork creation gamestree conjecture

Mathematics Subject Classification ID

Games involving graphs (91A43) Algorithmic game theory and complexity (91A68)

Abstract: We study Nash equilibria in the network creation game of Fabrikant et al.[10]. In this game a vertex can buy an edge to another vertex for a cost of $alpha$, and the objective of each vertex is to minimize the sum of the costs of the edges it purchases plus the sum of the distances to every other vertex in the resultant network. A long-standing conjecture states that if $alphagen$ then every Nash equilibrium in the game is a spanning tree. We prove the conjecture holds for any $alpha>3n-3$.

Recommendations

• On the tree conjecture for the network creation game
• On the tree conjecture for the network creation game
• On tree equilibria in max-distance network creation games

Cites work

• Basic network creation games
• Network creation games with traceroute-based strategies
• Network creation games: think global -- act local
• On a network creation game
• On the price of anarchy for high-price links
• On the tree conjecture for the network creation game
• Selfish network creation with non-uniform edge cost
• The price of anarchy in network creation games
• The price of anarchy in network creation games is (mostly) constant

Cited in

(6)

• On the tree conjecture for the network creation game
• The max-distance network creation game on general host graphs
• On the tree conjecture for the network creation game
• On tree equilibria in max-distance network creation games
• On the PoA Conjecture: Trees versus Biconnected Components
• One n remains to settle the tree conjecture

This page was built for publication: An improved bound for the tree conjecture in network creation games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6109522)