Stackelberg vs. Nash in Security Games: An Extended Investigation of Interchangeability, Equivalence, and Uniqueness

Dmytro Korzhyk, Zhengyu Yin, Christopher Kiekintveld, Vincent Conitzer, Milind Tambe

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.

Payoff structure in security games showing the utility gains for covering or attacking targets.

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.

Example payoff matrix for three targets under covered (C) and uncovered (U) conditions.

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

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. Previous work fails to address how a leader should compute her strategy given such uncertainty. We provide five contributions in the context of a general class of security games. First, we show that the Nash equilibria in security games are interchangeable, thus alleviating the equilibrium selection problem. Second, under a natural restriction on security games, any Stackelberg strategy is also a Nash equilibrium strategy; and furthermore, the solution is unique in a class of security games of which ARMOR is a key exemplar. Third, when faced with a follower that can attack multiple targets, many of these properties no longer hold. Fourth, we show experimentally that in most (but not all) games where the restriction does not hold, the Stackelberg strategy is still a Nash equilibrium strategy, but this is no longer true when the attacker can attack multiple targets. Finally, as a possible direction for future research, we propose an extensive-form game model that makes the defender's uncertainty about the attacker's ability to observe explicit.
BibTeX
@article{korzhyk2011stackelberg,
  author = {Dmytro Korzhyk and Zhengyu Yin and Christopher Kiekintveld and Vincent Conitzer and Milind Tambe},
  title = {{Stackelberg vs. Nash in Security Games: An Extended Investigation of Interchangeability, Equivalence, and Uniqueness}},
  journal = {J. Artif. Intell. Res.},
  year = {2011},
  url = {https://openreview.net/forum?id=Un3b4pfv4k},
}
Figure