Logo image
Back
Strategic Network Formation with Attack and Immunization
Book chapter   Open access   Peer reviewed

Strategic Network Formation with Attack and Immunization

Sanjeev Goyal, Shahin Jabbari, Michael Kearns, Sanjeev Khanna and Jamie Morgenstern
Web and Internet Economics, pp 429-443
2016
DOI: https://doi.org/10.1007/978-3-662-54110-4_30
url
https://arxiv.org/pdf/1511.05196View
SubmittedarXiv.org - Non-exclusive license to distribute,  Open

Abstract

Edge Density Equilibrium Network Nash Equilibrium Original Game Vulnerable Region
Strategic network formation arises in settings where agents receive some benefit from their connectedness to other agents, but also incur costs for forming these links. We consider a new network formation game that incorporates an adversarial attack, as well as immunization or protection against the attack. An agent’s network 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 can be viewed as a stylized model of settings where reachability rather than centrality is the primary interest (as in many technological networks such as the Internet), and vertices may be vulnerable to attacks (such as viruses), but may also reduce risk via potentially costly measures (such as an anti-virus software). Our main theoretical contributions include a strong bound on the edge density at equilibrium. In particular, we show that under a very mild assumption on the adversary’s attack model, every equilibrium network contains at most only 2n-4\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2n-4$$\end{document} edges for n≥4\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n \ge 4$$\end{document}, where n denotes the number of agents and this upper bound is tight. We also show that social welfare does not significantly erode: every non-trivial equilibrium with respect to several adversarial attack models asymptotically has social welfare at least as that of any equilibrium in the original attack-free model. We complement our sharp theoretical results by 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.

Metrics

13 Record Views
32 citations in Scopus

Details

Logo image