Strategic network formation with attack and immunization
From MaRDI portal
Abstract: Strategic network formation arises where agents receive benefit from connections to other agents, but also incur costs for forming links. We consider a new network formation game that incorporates an adversarial attack, as well as immunization against attack. An agent's benefit is the expected size of her connected component post-attack, and agents may also choose to immunize themselves from attack at some additional cost. Our framework is a stylized model of settings where reachability rather than centrality is the primary concern and vertices vulnerable to attacks may reduce risk via costly measures. In the reachability benefit model without attack or immunization, the set of equilibria is the empty graph and any tree. The introduction of attack and immunization changes the game dramatically; new equilibrium topologies emerge, some more sparse and some more dense than trees. We show that, under a mild assumption on the adversary, every equilibrium network with agents contains at most edges for . So despite permitting topologies denser than trees, the amount of overbuilding is limited. We also show that attack and immunization don't significantly erode social welfare: every non-trivial equilibrium with respect to several adversaries has welfare at least as that of any equilibrium in the attack-free model. We complement our theory with simulations demonstrating fast convergence of a new bounded rationality dynamic which generalizes linkstable best response but is considerably more powerful in our game. The simulations further elucidate the wide variety of asymmetric equilibria and demonstrate topological consequences of the dynamics e.g. heavy-tailed degree distributions. Finally, we report on a behavioral experiment on our game with over 100 participants, where despite the complexity of the game, the resulting network was surprisingly close to equilibrium.
Recommendations
Cites work
- A Noncooperative Model of Network Formation
- Connections. An introduction to the economics of networks.
- Definitions of equilibrium in network formation games
- Design of network topology in an adversarial environment
- Efficient best response computation for strategic network formation under attack
- Inoculation strategies for victims of viruses and the sum-of-squares partition problem
- Linear loss function for the network blocking game: an efficient model for measuring network robustness and link criticality
- Network security. A decision and game-theoretic approach.
- On a network creation game
- Optimal attack and reinforcement of a network
- The price of anarchy for network formation in an adversary model
Cited in
(14)- Equilibrium games in networks
- On the tree conjecture for the network creation game
- Free and perfectly safe but only partially effective vaccines can harm everyone
- Geometric spanner games
- Individual security, contagion, and network design
- Network disruption and the common-enemy effect
- On selfish creation of robust networks
- On the tree conjecture for the network creation game
- Social distancing network creation
- Geometric Network Creation Games
- Public goods in networks with constraints on sharing
- Efficient best response computation for strategic network formation under attack
- Network creation games with 2-neighborhood maximization
- Swap equilibria under link and vertex destruction
This page was built for publication: Strategic network formation with attack and immunization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2959849)
