Introduction
Stackelberg Security Games (SSGs) are a vital framework for modeling strategic interactions between a defender and an attacker. These models are used to protect critical infrastructure, such as airports and flight paths, by determining optimal resource allocation. However, as the complexity of these games grows—either through an increasing number of attacker types or a larger set of possible defender actions—traditional solvers face a "combinatorial explosion" that renders them computationally infeasible.
This paper introduces STACKGRAD, a novel gradient-based approach designed to overcome these scalability hurdles. By shifting from discrete integer programming to continuous, stochastic gradient ascent, STACKGRAD achieves near-constant scaling relative to the number of attacker types and superior performance in massive strategy spaces.
The Scalability Challenge
Standard SSG solvers typically rely on Mixed Integer Linear Programs (MILPs). While effective for small-scale problems, MILPs suffer from exponential runtime growth as the game's dimensions increase. Previous attempts to address this often required restrictive assumptions about the game's structure or the defender's available actions, limiting their real-world applicability.
The STACKGRAD Approach
The authors propose a fundamental shift in how SSGs are solved. Instead of treating the problem as a discrete search, STACKGRAD reformulates it as a differentiable optimization problem.
The STACKGRAD method rests on three key pillars:
- Smoothed Attacker Response: Traditional models assume an attacker perfectly chooses the best target, creating non-differentiable "jumps" in utility. STACKGRAD employs a Quantal Response (QR) model, using a softmax function to assign probabilities to attacker actions, making the defender’s expected utility differentiable.
- Parameterized Policy Classes: Rather than searching the entire space of mixed strategies, the defender is restricted to a rich, parameterized family of policies (e.g., categorical distributions or logistic models).
- Monte-Carlo Gradient Estimation: A stochastic gradient of the defender's utility is derived by sampling attacker types and defender schedules. This ensures that computation time per iteration remains independent of the total number of attacker types.
Experimental Evaluation
The authors evaluated STACKGRAD across two primary domains: a patrolling domain for testing scaling against attacker types, and a large-scale simulation based on the 500 most-trafficked US airports (FAMS-inspired domain) to test combinatorial strategy spaces.
Key Results
- Scaling with Attacker Types: In the patrolling domain, STACKGRAD-I demonstrated near-constant runtime as the number of attacker types increased. In contrast, the state-of-the-art DOBBS algorithm experienced an exponential runtime explosion. STACKGRAD-I achieved a competitive ratio of over 94% of the true optimum within 100 seconds.
- Scaling with Strategy Sets: In the flight network domain, STACKGRAD-L outperformed ASPEN (a leading MILP-based solver) as the number of targets grew. For large networks, STACKGRAD-L found superior solutions because it could implicitly explore the entire structured strategy space, whereas ASPEN was limited to a pre-sampled subset.
Discussion and Future Work
While STACKGRAD offers significant scalability advantages, it is not without limitations. Because the defender's utility function is non-convex, gradient ascent is only guaranteed to find a local maximum. Additionally, the algorithm's performance is inherently tied to the representational power of the chosen parametric policy class.
Future research directions include investigating whether specific parametric classes can provide theoretical performance guarantees and exploring more complex attacker models beyond the Quantal Response framework.
Summary updated