Abstract
We study a network formation game where agents balance the benefits of connectivity against the risks of a probabilistic contagion. In this model, an attack starts at a random vertex and spreads via the independent cascade model. We demonstrate that equilibrium networks are naturally sparse, containing $O(n \log n)$ edges, yet they maintain high social welfare ($\Theta(n^2)$), comparable to networks without attack risks.
The Challenge of Probabilistic Contagion
In traditional network formation games, agents pay to build links to maximize their reachability. However, real-world networks—such as the Internet or social groups—are vulnerable to cascading failures or viral spreads. While previous models often assumed deterministic infection (where an infected neighbor always infects you), this research addresses the more complex Independent Cascade Model. Here, if a node is infected, the contagion spreads to each neighbor independently with a fixed probability $p$.
Calculating expected utility in this probabilistic setting is #P-complete, making direct optimization computationally intractable for agents. This paper investigates whether stable (Nash equilibrium) networks still emerge and what structural properties they possess under such strategic risks.
Methodology
The authors employ a game-theoretic approach to analyze pure strategy Nash equilibria. To overcome the computational hardness of calculating exact utilities, they focus on proving structural properties of the graphs:
- Graph Decomposition: Utilizing decomposition trees to identify subgraphs with high minimum cuts that are prone to "almost certain infection."
- Probabilistic Analysis: Applying random graph theory and branching processes to model infection propagation in the "small $p$" regime.
- Equilibrium Constraints: Proving that if a network is too dense, the risk of infection outweighs the benefits of connectivity, prompting rational agents to drop edges to reduce their risk.
Key Insights: The Tension Between Connectivity and Safety
The research identifies a fundamental trade-off: while more edges increase reachability, they also create more pathways for infection.
- The Sparsity Constraint: The risk of infection eventually dominates as density increases. This forces equilibrium networks to remain sparse ($O(n \log n)$ edges).
- Fragility of Dense Subgraphs: If a subgraph is too well-connected, a single hit anywhere within it likely destroys the entire component. Agents strategically avoid such "fragile" states by limiting their connections.
- Welfare Resilience: Despite the threat of attack, a "giant component" of healthy nodes typically survives in equilibrium, ensuring that total system utility remains high.
Key Results
The study provides several formal bounds on the nature of equilibrium networks and their efficiency:
- Edge Density: Any equilibrium network on $n$ vertices has at most $O(n \log n / p)$ edges. For constant $p$, this is nearly tight.
- Component Size: Every non-trivial equilibrium network is guaranteed to have a giant component containing at least $n/3$ of the agents.
- Social Welfare: In the sparse regime ($O(n)$ edges), social welfare is $\Theta(n^2)$, asymptotically matching the welfare of networks where no attacks occur.
Limitations and Future Directions
While the paper establishes strong upper bounds, a small gap remains between the $O(n \log n)$ upper bound and the $\Omega(n)$ lower bound for edge density. Future work may explore whether $O(n)$ is the true limit. Additionally, the current model does not account for agent "immunization" or bilateral link formation (where both parties must agree to a link), both of which would significantly alter the strategic landscape. Finally, understanding the convergence of best-response dynamics—how agents might reach these equilibria through trial and error—remains an open question.
Summary updated