Playing games for security: an efficient exact algorithm for solving Bayesian Stackelberg games

By Praveen Paruchuri, J. Pearce, Janusz Marecki, Milind Tambe, Fernando Ordóñez, Sarit Kraus. Adaptive Agents and Multi-Agent Systems, 2008

516 citations recorded by the source corpus.

In a class of games known as Stackelberg games, one agent (the leader) must commit to a strategy that can be observed by the other agent (the follower or adversary) before the adversary chooses its own strategy. We consider Bayesian Stackelberg games, in which the leader is uncertain about the types of adversary it may face. Such games are important in security domains, where, for example, a security agent (leader) must commit to a strategy of patrolling certain areas, and a robber (follower) has a chance to observe this strategy over time before choosing its own strategy of where to attack. This paper presents an efficient exact algorithm for finding the optimal strategy for the leader to commit to in these games. This algorithm, DOBSS, is based on a novel and compact mixed-integer linear programming formulation. Compared to the most efficient algorithm known previously for this problem, DOBSS is not only faster, but also leads to higher quality solutions, and does not suffer from problems of infeasibility that were faced by this previous algorithm. Note that DOBSS is at the heart of the ARMOR system that is currently being tested for security scheduling at the Los Angeles International Airport.

View Paper: https://www.semanticscholar.org/paper/a97f12e2d7e5881b6db790b7883618340bed87cf

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Optimal randomized classification in adversarial settings (2014, result): “As our results predict, randomization can be quite effective in reducing the accuracy of reverse engineering attempts, but there is a caveat: when the learner uses a larger sample size, the advantage of randomization fades away.”
Computing optimal randomized resource allocations for massive security games (2009, methodology): “A new algorithm for solving Bayesian Stackelberg games (DOBSS) is central to the LAX application [11].”
Toward Proactive, Adaptive Defense: A Survey on Moving Target Defense (2019, methodology): “games [126], [127] have been used in modeling an attackdefense game to solve various cybersecurity problems.”
Monte Carlo Tree Search: a review of recent modifications and applications (2021, methodology): “Solving SSG consists in finding the Stackelberg Equilibrium (SE), which is typically approached by solving the Mixed Integer-Linear Program (MILP) corresponding to a given SSG instance (Paruchuri et al., 2008).”
Deployed ARMOR protection: the application of a game theoretic model for security at the Los Angeles International Airport (2008, methodology): “In AAMAS, 2007.”
Behavioral Experiments in Email Filter Evasion (2016, background): “Finally, our results have signiﬁcant bearing on the substantial literature preoccupied with designing high-quality randomization schemes in security (Paruchuri et al. 2008; Pita et al. 2009; 2010; Jajodia et al. 2012) and machine learning (Vorobeychik and Li 2014; Li and Vorobeychik 2015).”
Scalable Optimization of Randomized Operational Decisions in Adversarial Classification Settings (2015, methodology): “Extensive experiments demonstrate the efficacy of our approach.”
Learning Adversary Behavior in Security Games: A PAC Model Perspective (2015, background): “An SSG is a two player Stackelberg game between a defender (leader) and an adversary (follower) [27].”
Stackelberg vs. Nash in Security Games: An Extended Investigation of Interchangeability, Equivalence, and Uniqueness (2011, methodology): “…work to model interactions between the security forces and attackers and to compute strategies for the security forces (Conitzer & Sandholm, 2006; Paruchuri et al., 2008; Kiekintveld et al., 2009; Basilico, Gatti, & Amigoni, 2009; Letchford, Conitzer, & Munagala, 2009; Korzhyk, Conitzer, & Parr,…”