Geometric Network Creation Games

DOI10.1137/20m1376662zbMath1529.91017arXiv1904.07001OpenAlexW2951525813WikidataQ130169112 ScholiaQ130169112MaRDI QIDQ6141862

Pascal Lenzner, Davide Bilò, Tobias Friedrich, Anna Melnichenko

Publication date: 23 January 2024

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

geometrycommunication networksnetwork designexistence of equilibriaprice of anarchyalgorithmic game theorynetwork creation gamesgame dynamics

Mathematics Subject Classification ID

Games involving graphs (91A43) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithmic game theory and complexity (91A68) Equilibrium refinements (91A11)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Selfish network creation with non-uniform edge cost
• Efficient best response computation for strategic network formation under attack
• On the price of anarchy for high-price links
• The Steiner tree problem
• Potential games
• On the tree conjecture for the network creation game
• The price of anarchy for network formation in an adversary model
• A strategic model of social and economic networks
• On Selfish Creation of Robust Networks
• Basic Network Creation Games
• Asymmetric Swap-Equilibrium: A Unifying Equilibrium Concept for Network Creation Games
• Quality of Service in Network Creation Games
• Tree Nash Equilibria in the Network Creation Game
• On a network creation game
• Network Creation Games: Think Global – Act Local
• Strategic Network Formation with Attack and Immunization
• On Dynamics in Basic Network Creation Games
• The Price of Anarchy in Network Creation Games Is (Mostly) Constant
• The price of anarchy in network creation games
• The Price of Stability for Network Design with Fair Cost Allocation
• 8/7-approximation algorithm for (1,2)-TSP
• On nash equilibria for a network creation game
• The complexity of the network design problem
• A Noncooperative Model of Network Formation
• Local Search Heuristics for k-Median and Facility Location Problems
• On the History of the Minimum Spanning Tree Problem
• The Max-Distance Network Creation Game on General Host Graphs
• Reducibility among Combinatorial Problems
• New Approximation Algorithms for (1,2)-TSP
• Algorithms, games, and the internet
• On the topologies formed by selfish peers
• The Price of Anarchy in Cooperative Network Creation Games
• Network Creation Games with Traceroute-Based Strategies
• Computing and Combinatorics

This page was built for publication: Geometric Network Creation Games