Who Should Pay the Cost: A Game-theoretic Model for Government Subsidized Investments to Improve National Cybersecurity

Xinrun Wang, Bo An, Hau Chan

Abstract

Cybersecurity investments often suffer from a "tragedy of the commons" effect, where private firms under-invest because they do not internalize the social benefits of preventing network-wide contagion. This paper introduces the Stackelberg Cybersecurity Investment Game (SCIG), a framework for governments to strategically allocate subsidies to maximize national security. We model the problem as a two-stage game involving a budget-constrained government leader, self-interested users, and a strategic attacker. We provide computational solutions for various attacker capabilities, ranging from single-target to all-user attacks. Our results demonstrate that the proposed allocation strategies significantly outperform traditional baselines and reveal critical "tipping points" in security investment where small budget increases trigger widespread private defense.

Introduction

In modern interconnected economies, the security of one entity often depends on the security of its neighbors. This interdependence creates negative externalities: a breach in one firm can propagate through a network, yet firms rarely account for this social risk when budgeting for cybersecurity. Governments have begun intervening with grants and subsidies to bridge this gap, but the optimal allocation of these limited resources remains a complex challenge. This challenge is further exacerbated by strategic attackers who adapt their targets based on defensive investments, leading to a "whack-a-mole" scenario if defenses are not coordinated.

The Stackelberg Cybersecurity Investment Game (SCIG)

We model the interaction as a two-stage Stackelberg game. In the first stage, the government (the leader) allocates a fixed budget of subsidies to a set of users. In the second stage, the users and a strategic attacker (the followers) simultaneously decide their strategies. Users decide whether to invest in protection, aided by the government's subsidy, while the attacker chooses which users to target based on their remaining vulnerabilities.

The SCIG model illustrating the flow of subsidies (x), user investments (y), attack targets (z), and risk interdependencies (q).

The model explicitly accounts for indirect risk propagation, where an attack on one user can compromise another. The authors analyze three specific scenarios based on the attacker's capability ($K$):

  • All-user Attack ($K \geq N$): The attacker can hit everyone. Finding the optimal subsidy here is NP-hard; the authors propose a linear reverse convex program to solve it.
  • Single-user Attack ($K = 1$): The attacker hits only one target. An exact polynomial-time algorithm is provided for this case.
  • Multiple-user Attack ($1 < K < N$): The attacker hits a subset of targets. Since finding a Nash Equilibrium is computationally difficult, a heuristic based on Best-Response Gradient Dynamics (BRGD) is used to find an effective allocation.

Key Insights and Results

The researchers evaluated their models using synthetic data and real-world network data (e.g., the gamapos and sampson social networks) as proxies for business ecosystems.

The Subsidy Tipping Point

A key finding is the existence of "phase transitions" in national security. As the government budget increases, there are specific points where a small additional investment leads to a disproportionately large jump in both government utility and the number of users who choose to invest. This occurs because the subsidy pushes a critical mass of interdependent users to protect themselves simultaneously, creating a virtuous cycle of reduced network risk.

Government utility and user investment levels as a function of budget, showing clear phase transitions and the superiority of the proposed heuristic.

Strategic Shifting and Interdependence

Naive allocation strategies, such as subsidizing the most vulnerable or high-value targets, often fail because strategic attackers simply shift to the next most profitable target. The optimal strategy must account for this behavior. Furthermore, the most effective allocations target "central" nodes in the network—those whose protection provides the greatest reduction in potential contagion—rather than just those with the highest individual loss values.

Performance and Robustness

The proposed BRGD heuristic significantly outperformed standard baselines, including Uniform Allocation and Proportional Allocation. In the all-user attack scenario, global solvers found optimal strategies for 50-user networks in about 5 minutes. Additionally, the model proved robust to uncertainty regarding attack propagation probabilities and attacker capabilities, maintaining high effectiveness even with imperfect information.

Conclusion and Future Work

This research provides a rigorous foundation for government intervention in cybersecurity markets. By accounting for strategic attackers and network interdependencies, the SCIG model offers a more effective path to national security than simple proportional grants. Future work will address challenges of asymmetric information, where companies may misrepresent vulnerabilities to gain more subsidies, and the development of dynamic models for multi-round cyber-conflicts.

Reference: Wang, X., An, B., & Chan, H. (2019). Who Should Pay the Cost: A Game-theoretic Model for Government Subsidized Investments to Improve National Cybersecurity. Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19).

Summary updated

Abstract

Due to the recent cyber attacks, cybersecurity is becoming more critical in modern society. A single attack (e.g., WannaCry ransomware attack) can cause as much as $4 billion in damage. However, the cybersecurity investment by companies is far from satisfactory. Therefore, governments (e.g., in the UK) launch grants and subsidies to help companies to boost their cybersecurity to create a safer national cyber environment. The allocation problem is hard due to limited subsidies and the interdependence between self-interested companies and the presence of a strategic cyber attacker. To tackle the government's allocation problem, we introduce a Stackelberg game-theoretic model where the government first commits to an allocation and the companies/users and attacker simultaneously determine their protection and attack (pure or mixed) strategies, respectively. For the pure-strategy case, while there may not be a feasible allocation in general, we prove that computing an optimal allocation is NP-hard and propose a linear reverse convex program when the attacker can attack all users. For the mixed-strategy case, we show that there is a polynomial time algorithm to find an optimal allocation when the attacker has a single-attack capability. We then provide a heuristic algorithm, based on best-response-gradient dynamics, to find an effective allocation in the general setting. Experimentally, we show that our heuristic is effective and outperforms other baselines on synthetic and real data.
BibTeX
@inproceedings{wang2019who,
  author = {Xinrun Wang and Bo An and Hau Chan},
  title = {{Who Should Pay the Cost: A Game-theoretic Model for Government Subsidized Investments to Improve National Cybersecurity}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/834},
}
Figure