Network creation games: think global -- act local
From MaRDI portal
Abstract: We investigate a non-cooperative game-theoretic model for the formation of communication networks by selfish agents. Each agent aims for a central position at minimum cost for creating edges. In particular, the general model (Fabrikant et al., PODC'03) became popular for studying the structure of the Internet or social networks. Despite its significance, locality in this game was first studied only recently (Bil`o et al., SPAA'14), where a worst case locality model was presented, which came with a high efficiency loss in terms of quality of equilibria. Our main contribution is a new and more optimistic view on locality: agents are limited in their knowledge and actions to their local view ranges, but can probe different strategies and finally choose the best. We study the influence of our locality notion on the hardness of computing best responses, convergence to equilibria, and quality of equilibria. Moreover, we compare the strength of local versus non-local strategy-changes. Our results address the gap between the original model and the worst case locality variant. On the bright side, our efficiency results are in line with observations from the original model, yet we have a non-constant lower bound on the price of anarchy.
Recommendations
Cites work
- A bounded budget network creation game
- A Noncooperative Model of Network Formation
- A strategic model of social and economic networks
- Algorithmic Game Theory
- Asymmetric swap-equilibrium: a unifying equilibrium concept for network creation games
- Local matching dynamics in social networks
- Network creation games with traceroute-based strategies
- Network creation games: think global -- act local
- On a network creation game
- On dynamics in basic network creation games
- On nash equilibria for a network creation game
- Potential games
- The design of approximation algorithms
- The price of anarchy in network creation games
- The Price of Anarchy in Network Creation Games Is (Mostly) Constant
- The price of selfish behavior in bilateral network formation
- The Price of Stability for Network Design with Fair Cost Allocation
- Worst-case equilibria
Cited in
(21)- On the tree conjecture for the network creation game
- Geometric spanner games
- Dynamics in tree formation games
- On selfish creation of robust networks
- Network creation games: think global -- act local
- Celebrity games
- On the tree conjecture for the network creation game
- Efficient equilibrium concepts in non-cooperative network formation
- Towards network games with social preferences
- Basic network creation games with communication interests
- Selfish versus unselfish optimization of network creation
- Network Creation Games with Local Information and Edge Swaps
- Network movement games
- Network creation games with traceroute-based strategies
- An improved bound for the tree conjecture in network creation games
- Geometric Network Creation Games
- The Impact of Cooperation in Bilateral Network Creation
- Network creation games with 2-neighborhood maximization
- One n remains to settle the tree conjecture
- Speaking of opinions: comparing approaches to modelling opinion manipulation
- Some results of Maria Serna on strategic games: complexity of equilibria and models
This page was built for publication: Network creation games: think global -- act local
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2946395)
