Conference proceeding
Network Formation under Random Attack and Probabilistic Spread
PROCEEDINGS OF THE TWENTY-EIGHTH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, pp.180-186
01 Jan 2019
Featured in Collection : UN Sustainable Development Goals @ Drexel
Abstract
We study a network formation game where agents receive benefits by forming connections to other agents but also incur both direct and indirect costs from the formed connections. Specifically, once the agents have purchased their connections, an attack starts at a randomly chosen vertex in the network and spreads according to the independent cascade model with a fixed probability, destroying any infected agents. The utility or welfare of an agent in our game is defined to be the expected size of the agent's connected component post-attack minus her expenditure in forming connections. Our goal is to understand the properties of the equilibrium networks formed in this game. Our first result concerns the edge density of equilibrium networks. A network connection increases both the likelihood of remaining connected to other agents after an attack as well the likelihood of getting infected by a cascading spread of infection. We show that the latter concern primarily prevails and any equilibrium network in our game contains only O(n log n) edges where n denotes the number of agents. On the other hand, there are equilibrium networks that contain Omega(n) edges showing that our edge density bound is tight up to a logarithmic factor. Our second result shows that the presence of attack and its spread through a cascade does not significantly lower social welfare as long as the network is not too dense. We show that any non-trivial equilibrium network with O(n) edges has Theta(n(2)) social welfare, asymptotically similar to the social welfare guarantee in the game without any attacks.
Metrics
2 Record Views
Details
- Title
- Network Formation under Random Attack and Probabilistic Spread
- Creators
- Yu Chen - Univ Penn, Philadelphia, PA 19104 USAShahin Jabbari - Univ Penn, Philadelphia, PA 19104 USAMichael Kearns - Univ Penn, Philadelphia, PA 19104 USASanjeev Khanna - Univ Penn, Philadelphia, PA 19104 USAJamie Morgenstern - Georgia Institute of Technology
- Contributors
- S Kraus (Editor)
- Publication Details
- PROCEEDINGS OF THE TWENTY-EIGHTH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, pp.180-186
- Conference
- TWENTY-EIGHTH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, 28th
- Publisher
- Ijcai-Int Joint Conf Artif Intell
- Number of pages
- 7
- Resource Type
- Conference proceeding
- Language
- English
- Academic Unit
- Computer Science (Computing)
- Identifiers
- 991021868089204721
UN Sustainable Development Goals (SDGs)
This output has contributed to the advancement of the following goals:
InCites Highlights
These are selected metrics from InCites Benchmarking & Analytics tool, related to this output
- Collaboration types
- Domestic collaboration
- Web of Science research areas
- Computer Science, Artificial Intelligence
- Computer Science, Interdisciplinary Applications
- Computer Science, Theory & Methods