Geometric Network Creation Games
From MaRDI portal
Abstract: Network Creation Games are a well-known approach for explaining and analyzing the structure, quality and dynamics of real-world networks like the Internet and other infrastructure networks which evolved via the interaction of selfish agents without a central authority. In these games selfish agents which correspond to nodes in a network strategically buy incident edges to improve their centrality. However, past research on these games has only considered the creation of networks with unit-weight edges. In practice, e.g. when constructing a fiber-optic network, the choice of which nodes to connect and also the induced price for a link crucially depends on the distance between the involved nodes and such settings can be modeled via edge-weighted graphs. We incorporate arbitrary edge weights by generalizing the well-known model by Fabrikant et al.[PODC'03] to edge-weighted host graphs and focus on the geometric setting where the weights are induced by the distances in some metric space. In stark contrast to the state-of-the-art for the unit-weight version, where the Price of Anarchy is conjectured to be constant and where resolving this is a major open problem, we prove a tight non-constant bound on the Price of Anarchy for the metric version and a slightly weaker upper bound for the non-metric case. Moreover, we analyze the existence of equilibria, the computational hardness and the game dynamics for several natural metrics. The model we propose can be seen as the game-theoretic analogue of a variant of the classical Network Design Problem. Thus, low-cost equilibria of our game correspond to decentralized and stable approximations of the optimum network design.
Recommendations
Cites work
- 8/7-approximation algorithm for (1,2)-TSP
- A Noncooperative Model of Network Formation
- A strategic model of social and economic networks
- Algorithms, games, and the internet
- Asymmetric swap-equilibrium: a unifying equilibrium concept for network creation games
- Basic network creation games
- Computing and Combinatorics
- Efficient best response computation for strategic network formation under attack
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Local Search Heuristics for k-Median and Facility Location Problems
- Near-optimal network design with selfish agents
- Network creation games with traceroute-based strategies
- Network creation games: think global -- act local
- New approximation algorithms for \((1,2)\)-TSP
- On a network creation game
- On dynamics in basic network creation games
- On nash equilibria for a network creation game
- On selfish creation of robust networks
- On the History of the Minimum Spanning Tree Problem
- On the price of anarchy for high-price links
- On the topologies formed by selfish peers
- On the tree conjecture for the network creation game
- Potential games
- Quality of service in network creation games
- Reducibility among combinatorial problems
- Selfish network creation with non-uniform edge cost
- Strategic network formation with attack and immunization
- The complexity of the network design problem
- The max-distance network creation game on general host graphs
- The price of anarchy for network formation in an adversary model
- The price of anarchy in cooperative network creation games
- The price of anarchy in network creation games
- The Price of Anarchy in Network Creation Games Is (Mostly) Constant
- The Price of Stability for Network Design with Fair Cost Allocation
- The Steiner tree problem
- Worst-case equilibria
Cited in
(3)
This page was built for publication: Geometric Network Creation Games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6141862)
