Network Formation under Random Attack and Probabilistic Spread

Yu Chen, Shahin Jabbari, Michael J. Kearns, Sanjeev Khanna, Jamie Morgenstern

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.

Introduction

In standard network formation games, agents (nodes) strategically purchase edges to maximize their reachability within the network. However, real-world connections—whether in digital infrastructure or social circles—are a double-edged sword. While they provide access to resources and information, they also serve as conduits for contagious shocks, such as malware or biological pathogens.

This research addresses the trade-off between the benefits of connectivity and the risks of probabilistic, cascading attacks. Unlike previous models that assumed deterministic spread, this work employs the independent cascade model, where an infection spreads across an edge with a fixed probability $p$. This introduces significant complexity, as calculating an agent's expected utility becomes a #P-complete problem. The study focuses on characterizing the structural properties of Nash equilibria in this computationally challenging environment.

Methods

Due to the #P-completeness of utility calculations, standard algorithmic approaches for finding Nash equilibria are inapplicable. Instead, the authors utilize tools from extremal graph theory and probabilistic analysis. They analyze pure strategy Nash equilibria by identifying "beneficial deviations." For instance, they demonstrate that if a network's density exceeds a certain threshold, the risk of a catastrophic cascade outweighs the benefits of additional edges, prompting selfish agents to delete connections. This self-regulating behavior allows for the derivation of hard structural bounds using techniques like Erdős-Rényi random graph theory and Galton-Watson branching processes.

Key Results and Structural Insights

The analysis reveals that strategic behavior naturally limits network density while preserving high-level connectivity.

Edge Density and Self-Correction

A primary finding is that equilibrium networks are inherently sparse. The authors prove that any equilibrium network on $n$ vertices contains at most $O(n \log n / p)$ edges. In regimes where the spread probability $p$ is very small ($p < 1/n$), this bound tightens to $O(n)$. This sparsity arises because "over-building" creates dense clusters where any single attack likely leads to total infection, incentivizing agents to drop edges to mitigate risk.

Figure 1: Examples of candidate equilibrium structures, such as stars and cycles, which balance connectivity and risk.

Component Size and Social Welfare

Despite the threat of cascading attacks, equilibrium networks do not fragment into insignificance. The research proves that any non-trivial equilibrium (one with at least one edge) maintains a massive connected component containing at least one-third of all nodes.

Figure 2: A structural representation of how a central component $C_0$ can connect multiple sub-components $C_1, \dots, C_k$ to maintain high social welfare.

Furthermore, the presence of attacks does not drastically reduce the overall value of the network. For sparse equilibrium networks, the total social welfare—the sum of all agents' utilities—remains $\Omega(n^2)$, which is asymptotically optimal and comparable to networks formed in the absence of any attack risk. While the Price of Anarchy is $\Theta(n)$ due to trivial empty-graph equilibria, the Price of Stability is $\Theta(1)$, indicating that the best equilibria are highly efficient.

Conclusion and Future Work

This work demonstrates that even under complex, probabilistic risks, strategic network formation leads to sparse yet highly functional structures. However, several open questions remain:

  • Closing the Density Gap: There is a logarithmic gap between the $O(n \log n)$ upper bound and the $O(n)$ examples found. Future work aims to determine if the $O(n)$ bound holds universally.
  • Immunization Strategies: The current model only allows agents to manage risk by removing edges. Incorporating "vaccination" or node-level security costs would add another layer of realism.
  • Bilateral Consent: Moving from unilateral edge creation to bilateral agreements (where both nodes must agree to a link) would better model human social networks and could lead to different equilibrium properties.

Summary updated

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.
BibTeX
@inproceedings{chen2019network,
  author = {Yu Chen and Shahin Jabbari and Michael J. Kearns and Sanjeev Khanna and Jamie Morgenstern},
  title = {{Network Formation under Random Attack and Probabilistic Spread}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  url = {https://openreview.net/forum?id=gp7Ftqb3fsJ},
}
Figure