Abstract
There has been significant recent interest in game-theoretic approaches to security, with much of the recent research focused on utilizing the leader-follower Stackelberg game model. Among the major applications are the ARMOR program deployed at LAX Airport and the IRIS program in use by the US Federal Air Marshals (FAMS). The foundational assumption for using Stackelberg games is that security forces (leaders), acting first, commit to a randomized strategy; while their adversaries (followers) choose their best response after surveillance of this randomized strategy. Yet, in many situations, a leader may face uncertainty about the follower's surveillance capability. We provide five contributions in the context of a general class of security games, investigating the interchangeability, equivalence, and uniqueness of Nash and Stackelberg equilibria.
Introduction: The Challenge of Surveillance Uncertainty
In high-stakes security environments, game-theoretic models like the Strong Stackelberg Equilibrium (SSE) have become standard for optimizing resource allocation. Systems such as ARMOR and IRIS rely on the assumption that attackers (followers) perform surveillance to observe the defender's (leader's) randomized patrol strategy. However, a critical vulnerability exists: if an attacker strikes without surveillance, the interaction is better modeled as a Nash Equilibrium (NE), where moves are effectively simultaneous.
This paper addresses the "defender's dilemma": if the SSE and NE strategies differ, which should the defender deploy? By investigating the relationship between these solution concepts, we demonstrate that in many common security scenarios, the Stackelberg strategy is inherently robust, serving as a valid Nash Equilibrium strategy even when surveillance is absent.
The Security Game Model
We define a general class of security games characterized by specific payoff structures. In these games, covering a target increases the defender's utility and decreases the attacker's utility compared to leaving it uncovered. This relationship is formalized by the requirement that the change in utility for covering a target ($\Delta U$) must be positive for both players.
As shown in Figure 1, the utility for a covered target $U^c$ is always greater than the utility for an uncovered target $U^u$ for the defender, while the inverse is true for the attacker. This fundamental structure allows us to map security games to zero-sum games, facilitating the proof of key properties like the interchangeability of Nash equilibria.
Theoretical Equivalence and the SSAS Property
A central contribution of this work is the identification of the Subsets of Schedules Are Schedules (SSAS) property. This property assumes that if a security resource can cover a specific set of targets, it can also cover any subset of those targets. This is a natural fit for many real-world deployments, such as airport checkpoints where a unit can be assigned to any combination of available gates.
Under the SSAS property, we prove that any SSE strategy is also an NE strategy ($\Omega_{SSE} \subseteq \Omega_{NE}$). This means that defenders can commit to Stackelberg strategies without fear that a lack of attacker surveillance will render their strategy sub-optimal. Furthermore, in restricted models like ARMOR, which feature homogeneous resources and single-target schedules, the defender's strategy is shown to be unique across minimax, NE, and SSE concepts.
Experimental Validation and the Multi-Attacker Gap
To test the limits of these theoretical guarantees, we conducted experiments on 1,000 randomly generated games where the SSAS property does not necessarily hold (e.g., complex flight tours). The results were striking:
- Single-Attacker Resource: Even without SSAS, the SSE strategy remained a Nash Equilibrium strategy in over 94% of cases.
- Multiple Attacker Resources: The equivalence breaks down when attackers can strike multiple targets simultaneously. In these scenarios, the percentage of games where SSE failed to be an NE strategy rose to between 20% and 60%.
Conclusion and Future Directions
Our findings suggest that for most current security applications, the Stackelberg model is remarkably robust to surveillance uncertainty. However, the breakdown of equivalence in multi-attacker scenarios highlights a critical area for future research. We propose an extensive-form game model that explicitly accounts for the probability of attacker observation ($p_{obs}$), providing a path toward more sophisticated models that bridge the gap between Stackelberg and Nash dynamics in complex, multi-resource environments.
Summary updated