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

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

Source-linked AI summary

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

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

arXiv:1401.3888v1Jan 16, 2014cs.GT

TL;DR

Security defenders face uncertainty about whether attackers can observe their committed randomized strategies, leaving the appropriate Stackelberg or simultaneous-move recommendation unresolved. The paper analyzes Nash and Stackelberg equilibria in security games theoretically and experimentally, finding broad equivalence under SSAS, exceptions with multiple attacker resources, and a future extensive-form model for observation uncertainty.

Problem
Previous work does not resolve how a defender should choose a strategy when the attacker’s ability to observe her mixed strategy is unclear.
Method
The paper combines theoretical equilibrium analysis, counterexamples, experiments, and an extensive-form model for explicit uncertainty about attacker observation.
Results
Under SSAS, defender SSE strategies are also NE strategies; exceptions occur without SSAS or with multiple attacker resources, while experiments find mismatches vanishingly rare in the tested non-SSAS games.
Takeaways & Limitations
For many security games, the defender can use an SSE strategy without sacrificing best-response status when attacker observation is uncertain.
Takeaways & Limitations
The paper does not resolve how defenders should play when SSE strategies are not necessarily Nash strategies and attacker observation is unclear.

Abstract

from arXiv · show

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.

1. Introduction

Security games use a leader-follower Stackelberg model, but uncertainty about attackers’ ability to observe the defender’s strategy creates a dilemma over which strategy to adopt. The paper analyzes this dilemma theoretically and experimentally, identifying conditions under which Stackelberg and Nash strategies coincide.

1. Introduction: Stackelberg security applications model defenders committing first to randomized patrol or inspection strategies, after which attackers choose targets.ARMOR at LAX and IRIS for FAMS are major deployed applications.
1. Introduction: Uncertainty about whether attackers observe security strategies makes the defender’s choice between Stackelberg and simultaneous-move recommendations unresolved.Previous work had not resolved how the defender should choose when attacker observation capability is unclear.
1. Introduction: Nash equilibria are interchangeable in security games, alleviating the equilibrium-selection problem for simultaneous-move analysis.The paper establishes this as a theoretical contribution for the studied class of games.
1. Introduction: Under the SSAS property, every defender Stackelberg strategy is also a Nash equilibrium strategy, while counterexamples arise without SSAS or with multiple attacker targets.The paper also reports uniqueness for an important subclass represented by ARMOR.
1. Introduction: The paper combines formal equilibrium analysis, counterexamples, experiments, and an extensive-form model for explicit uncertainty about attacker observation.The proposed extensive-form model is presented as a direction for future research.

2. Definitions and Notation

The paper formalizes security games as defender-attacker resource-allocation games with target coverage, utility changes from coverage, and operational scheduling constraints. It then defines simultaneous-move Nash and leader-follower Strong Stackelberg equilibria for these games.

2. Definitions and Notation: A security game has a defender covering targets with resources and an attacker choosing a target from the target set.The model is motivated by security-resource allocation applications.
2. Definitions and Notation: Adding resources to cover a target helps the defender and hurts the attacker, represented by positive coverage-related utility differences.The model assumes ∆Ud(ti) > 0 and ∆Ua(ti) > 0.
2. Definitions and Notation: Resource and scheduling constraints let resources cover feasible schedules containing multiple targets, including FAMS flight tours and LAX single-target schedules.Heterogeneous resources encode timing and location restrictions; LAX uses homogeneous resources and schedules of size 1.
2. Definitions and Notation: The defender’s pure strategies are feasible resource-to-schedule assignments, which can be represented by binary coverage vectors when schedules cover targets.Not every coverage vector is feasible because of resource and schedule constraints.
2. Definitions and Notation: In Nash equilibrium, both players’ strategies are mutual best responses in the simultaneous-move game.The attacker does not observe a defender commitment in this model.
2. Definitions and Notation: In Strong Stackelberg equilibrium, the defender commits first, the attacker best responds after observation, and ties are resolved in the defender’s favor.The defender’s SSE utility is at least as high as her utility in any Nash profile because she can commit to a Nash strategy.
2. Definitions and Notation: SSE computation requires the defender to know the attacker’s utility function, whereas Nash analysis requires the attacker to know the defender’s utility function.The paper notes that the latter information requirement may be harder to justify in practice.

3. Equilibria in Security Games

Security games have interchangeable Nash equilibria, and under SSAS the defender’s SSE strategies are also minimax and Nash strategies. Restricted games can additionally yield unique defender solutions, whereas arbitrary scheduling constraints and attacker multi-target actions can break these properties.

3.1 Equivalence of NE and Minimax: Security games’ defender minimax strategies exactly equal their Nash equilibrium strategies.
3.2 Interchangeability of Nash Equilibria: Nash equilibria are interchangeable: pairing either player’s strategy from two equilibria produces another Nash equilibrium.
3.2 Interchangeability of Nash Equilibria: The attacker receives the same expected utility in every Nash equilibrium, although the defender’s expected utility can vary with attacker strategy selection.
3.3 SSE Strategies Are Also Minimax/NE Strategies: Without SSAS, schedule constraints can make the defender’s SSE strategy differ from the unique Nash strategy, with arbitrarily large payoff differences possible.
3.3 SSE Strategies Are Also Minimax/NE Strategies: Under the SSAS property, every defender SSE strategy is also a minimax and Nash strategy, allowing safe SSE commitment when observation capability is uncertain.
3.4 Uniqueness in Restricted Games: In restricted homogeneous-resource games, the defender has a unique minimax, Nash, and SSE strategy, although the attacker’s Nash strategy need not be unique.

4. Multiple Attacker Resources

Allowing attackers to use multiple resources changes the relationship between Stackelberg and Nash strategies: some games retain equivalence, while others do not. The paper gives sufficient conditions and exhaustive examples describing these possibilities.

Model: The extended model allows attackers to use multiple resources to attack multiple targets simultaneously.The model uses homogeneous resources and schedules of size 1.
SSE and NE equivalence: In some multiple-resource games, the defender’s SSE strategy is also an NE strategy, including when all targets are interchangeable.Equal-probability defense and attack can produce an NE profile in this case.
SSE and NE divergence: In other games, the defender’s SSE strategy is not part of any NE profile because NE defense responds to attack probabilities rather than influencing the attacker’s choice.With multiple attacker resources, another target may be more valuable to defend than a target the SSE strategy protects to deter attack.
Sufficient condition: Proposition 4.2 gives a sufficient condition for SSE and NE equivalence when SSAS holds and the scaled attacker strategy remains feasible.If d is an SSE strategy for both one- and L-resource games and L a_i <= 1 for every target, then the scaled profile is an NE.
Examples: The paper identifies exhaustive patterns in which the strategies cS,2, cN,2, and cS,1 = cN,1 are all equal, all different, or exactly two are equal.The examples show that SSE and NE can coincide for two resources, differ only when resources change, or differ between solution concepts.
Examples: Examples include distinct unique profiles: one has NE ⟨(0, .5, .5), (1, .5, .5)⟩, while another has NE ⟨(0, 3/4, 1/4), (1, 7/10, 3/10)⟩.These examples illustrate concrete departures between SSE and NE strategies with two attacker resources.

5. Experimental Results

Experiments vary attacker and defender resources, schedule size, and schedule count across random security games, testing whether computed SSE strategies are also NE strategies. The results confirm equivalence in the single-resource, size-1 case but find more divergences with multiple attacker resources and, less often, larger schedules.

Experimental method: The method computes an SSE strategy with DOBSS, then uses a linear feasibility program to test whether some attacker response makes it part of an NE profile.The feasibility constraints restrict attacker support to best responses and require the defender strategy to be a best response.
Experimental design: The study varies attacker resources, homogeneous defender resources, schedule size, and the number of schedules.Figure 2 reports the percentage of games where the SSE strategy is not an NE strategy.
Experimental design: The experiments generate 1000 random games with 10 targets for each parameter setting.Payoffs are sampled uniformly, schedules have a specified common size plus an empty schedule, and schedules are randomly selected from target subsets.
Results: For one attacker resource and schedule size 1, the SSE strategy is always an NE strategy, matching the theoretical result because SSAS holds.Increasing either attacker resources or schedule size produces games where SSE is not NE.
Results: The number of divergences increases significantly as attacker resources increase, especially from 1 to 2, and remains common across many parameter settings with 2 or 3 resources.The figure presents these outcomes across defender resources, schedule sizes, and schedule counts.
Results: With one attacker resource, increasing schedule size produces generally fewer than 6% divergent games, while adding more random schedules can reduce the divergence rate to zero.When attacker resources are multiple, increasing schedule size can either increase or decrease the number of divergent games.
Conclusion: The experiments conclude that SSE strategies are usually also NE strategies with one attacker resource, but often are not with multiple attacker resources.This supports continued use of SSE in the former setting while leaving the multiple-resource case unresolved.

6. Uncertainty About the Attacker’s Ability to Observe: A Model for Future Research

The paper proposes an extensive-form model for uncertainty about whether an attacker observes the defender’s committed distribution, and derives sanity checks connecting it to Stackelberg and Nash models. The model supports equilibrium correspondence in important special cases but leaves general solution methods for future research.

Open problem: When the Stackelberg strategy is not a Nash equilibrium strategy, the paper does not resolve how the defender should choose under uncertain observability.This occurs in many games with multiple attacker resources and some single-resource games without SSAS; better-solving algorithms are left for future research.
Model: The model gives the attacker probability pobs of observing the defender’s mixed strategy and probability 1−pobs of not observing it.The defender commits first; the attacker’s observation capability is uncertain after that commitment.
Model: The extensive-form game has infinite size because the defender can choose distributions continuously, so discretization is proposed as a straightforward solution approach.The paper notes that standard extensive-form algorithms cannot be applied directly.
Sanity checks: If pobs = 1, every subgame-perfect equilibrium corresponds to an SSE of the underlying security game.Observation is guaranteed, so the attacker best-responds to the committed distribution and the defender optimizes against that response.
Sanity checks: If pobs = 0, every Nash equilibrium of the extensive-form game corresponds to a Nash equilibrium of the underlying security game.With no observation, the attacker can assign positive probability only to best responses to the defender’s induced distribution.
Intermediate observation: At intermediate pobs values, an extensive-form equilibrium may correspond to neither an SSE nor an NE in sufficiently general settings.When a Stackelberg strategy is also a Nash equilibrium strategy, Proposition 6.3 shows it remains the defender’s strategy in a subgame-perfect equilibrium.
Intermediate observation: If SSAS holds with one attacker resource, any Stackelberg strategy is the defender’s strategy in a subgame-perfect equilibrium of the extensive-form game.This follows from the paper’s earlier result that such a Stackelberg strategy is also a Nash equilibrium strategy.

7. Additional Related Work

The paper situates its security-game results within research on observability, commitment, safety-level strategies, extensive-form robustness, and related security applications. It emphasizes that its interchangeability, equivalence, and uniqueness results rely on the structure of real-world security games rather than general Stackelberg games.

Observability and commitment: Prior work studies observability and commitment in Stackelberg games, including noisy observations and the value of committing to mixed strategies.The cited literature debates commitment to pure strategies while finding that mixed-strategy commitment retains a leader advantage.
Security applications: Security-game applications span electric grids, subways, airports, and other critical infrastructure, alongside research on terrorist planning and target selection.These studies indicate that terrorist attacks may be planned with some sophistication.
Relation to game theory: The paper contrasts its security-game results with general Stackelberg research, where subset, equivalence, interchangeability, and uniqueness properties do not generally exist.It relates its interchangeability result to the minimax theorem for two-player zero-sum games while emphasizing the security-game setting.
Safety-level strategies: Safety-level strategies maximize a player’s utility against an opponent minimizing that utility, and can differ substantially from Nash or Stackelberg solutions.The cited example describes a defender’s safety-level choice that yields lower utility than the minimax/Stackelberg/Nash solution.
Extensive-form robustness: Related work also examines robustness of equilibria to changes in extensive-form move order as the number of players increases.The paper places this work alongside studies of strategically zero-sum and unilaterally competitive games.
Observability and commitment: Experimental work on observability tests defender strategies against human attackers with limited observations and reports advantages for strategies modeling anchoring bias.The paper presents this work as complementary to its own analysis.

8. Summary

The paper studies how defenders should compute mixed strategies in security games inspired by real-world applications. It establishes interchangeability and Stackelberg–Nash relationships under SSAS, identifies failures with multiple attacker resources, and proposes implications for applications and future research.

Summary: Nash equilibria in security games are interchangeable, alleviating the defender’s equilibrium selection problem in simultaneous-move games.This result exploits the structure of the security-game class.
Summary: Under SSAS, any Stackelberg strategy is also a Nash equilibrium strategy, and the strategy is unique in a class exemplified by ARMOR.The result directly addresses the defender’s choice between Stackelberg and simultaneous-move recommendations.
Summary: When the attacker can attack multiple targets, many of these interchangeability, equivalence, and uniqueness properties no longer hold.The paper identifies this setting as a direction for future research.
Summary: Experiments show positive properties in many games that do not satisfy SSAS, although the paper’s summary does not claim these properties hold universally.The practical implications include defender strategy selection in applications such as ARMOR and IRIS.