Abstract
Multi-Defender Stackelberg Security Games (MSSGs) traditionally suffer from payoff discontinuities caused by deterministic attacker tie-breaking rules. These discontinuities often lead to fragile solutions or the total non-existence of equilibria in real-world scenarios where data is noisy. This paper introduces a robust framework for MSSGs by replacing deterministic attacker behavior with a probabilistic Attacker’s Behaviour Function (ABF). By accounting for uncertainty in the attacker’s utility, the authors eliminate payoff jumps, proving that robust, efficient solutions—such as approximate Nash Equilibria and the $\alpha$-core—not only exist but can be computed in polynomial time. Surprisingly, this robust approach often improves defender utilities compared to traditional pessimistic models.
Introduction
In a standard Stackelberg Security Game (SSG), a defender (the leader) commits to a security strategy, and an attacker (the follower) responds optimally. However, when multiple defenders are involved (MSSGs), the strategic landscape becomes significantly more complex. A primary challenge in these games is the reliance on tie-breaking rules. If an attacker is indifferent between two targets, which one do they choose?
In single-defender settings, researchers often assume "optimistic" tie-breaking (the attacker helps the defender). In multi-defender settings, this is impossible because one defender's gain is often another's loss. Previous models turned to "pessimistic tie-breaking," where each defender assumes the worst possible outcome for themselves. This creates a "house of cards" scenario: an infinitesimal change in the attacker’s perceived utility can cause a massive, discontinuous jump in a defender's payoff. Because real-world attacker utilities are never known with 100% precision, these traditional solutions are often too fragile to be practical.
A Robust Framework for Attacker Behavior
To address these instabilities, the authors propose a Robust MSSG model that shifts from deterministic best-responses to probabilistic behavior. The core of this model is the Attacker’s Behaviour Function (ABF), denoted as $\omega$. Instead of the attacker selecting a single target with certainty, $\omega$ assigns a probability to each target based on its utility.
The authors specifically focus on $(\delta, \epsilon)$-Robustness. In this regime, any target offering a utility significantly lower (by a margin of $\delta$) than the optimal target is attacked with a very low probability (less than $\epsilon$). This captures the reality of an attacker who is "mostly" rational but subject to noise, observation errors, or bounded rationality. By using a continuous probability distribution, the "jumps" in defender payoffs disappear, making the game mathematically well-behaved and ensuring that stable solutions exist.
Algorithmic Solutions: The ALLOC Procedure
To find equilibria in this smoothed landscape, the authors introduce the ALLOC Algorithm. This is a greedy allocation procedure where defenders iterate through targets based on a specific preference order derived from their own rewards. Defenders fill these targets with security resources until a specific attacker utility level (or "height") is reached.
The paper analyzes two primary solution concepts:
- Non-cooperative settings: Searching for a $\zeta$-Nash Equilibrium, where no defender can significantly improve their utility by unilaterally changing their strategy.
- Cooperative settings: Searching for the $\alpha$-core, a state where no coalition of defenders can deviate and guarantee themselves a better outcome, regardless of how the remaining defenders respond.
Key Insights and Results
Smoothing the Discontinuity
The transition to a probabilistic model provides a single, unified reality for all defenders. The authors argue against traditional robust optimization that assumes a worst-case scenario for each player independently, which effectively forces defenders to plan against different attackers in "parallel universes." The ABF model ensures all defenders are responding to the same stochastic attacker.
Robustness as a "Free Lunch"
One of the paper's most striking findings is that robust solutions can lead to higher utilities for defenders than pessimistic non-robust ones. Because the model does not assume the absolute worst-case tie-break at every infinitesimal point, defenders can identify more efficient resource distributions that were previously obscured by the mathematical artifacts of the pessimistic model.
Computational Efficiency and Stability
The authors prove that every robust MSSG possesses a robust approximate Nash Equilibrium and a robust approximate $\alpha$-core. Crucially, they provide polynomial-time algorithms to compute these solutions, making the framework applicable to large-scale security problems. Furthermore, Theorem 5.2 (The Robustness Theorem) formally proves that any equilibrium found in this model remains an approximate equilibrium even if the underlying game parameters (such as rewards or penalties) are slightly perturbed.
Limitations and Future Directions
While the framework is robust, it primarily focuses on "non-saturated" games—scenarios where defenders do not have enough resources to reduce the attacker's utility to zero across all targets. While extensions for saturated games are suggested, they require further detailed analysis. Additionally, the model assumes the attacker has perfect knowledge of the defenders' coverage. Future research could explore "doubly robust" models where the attacker also faces imperfect information. Finally, the specific shape of the ABF—how quickly the attack probability drops for sub-optimal targets—remains an empirical question that will vary based on the specific real-world attacker being modeled.
Summary updated