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

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.

References in corpus (1)

• Competitive Safety Analysis: Robust Decision-Making in Multi-Agent Systems

Cited by in corpus (13)

• Randomized Prediction Games for Adversarial Machine Learning
• Single-Leader-Multiple-Followers Stackelberg Security Game with Hypergame Framework
• Dynamic Signaling Games with Quadratic Criteria under Nash and Stackelberg Equilibria
• Information Leakage Games
• On Stackelberg Mixed Strategies
• Optimal Secure Control with Linear Temporal Logic Constraints
• Hypothesis Testing under Subjective Priors and Costs as a Signaling Game
• Augmented Probability Simulation Methods for Sequential Games
• A Game-Theoretic Approach to Information-Flow Control via Protocol Composition
• Leakage and Protocol Composition in a Game-Theoretic Perspective
• A Stochastic Surveillance Stackelberg Game: Co-Optimizing Defense Placement and Patrol Strategy
• Equalizer zero-determinant strategy in discounted repeated Stackelberg asymmetric game
• Bayesian hypergame approach to equilibrium stability and robustness in moving target defense