Computing optimal randomized resource allocations for massive security games

By Christopher Kiekintveld, Manish Jain, Jason Tsai, James Adam Pita, Fernando Ordóñez, Milind Tambe. Adaptive Agents and Multi-Agent Systems, 2009

425 citations recorded by the source corpus.

Predictable allocations of security resources such as police officers, canine units, or checkpoints are vulnerable to exploitation by attackers. Recent work has applied game-theoretic methods to find optimal randomized security policies, including a fielded application at the Los Angeles International Airport (LAX). This approach has promising applications in many similar domains, including police patrolling for subway and bus systems, randomized baggage screening, and scheduling for the Federal Air Marshal Service (FAMS) on commercial flights. However, the existing methods scale poorly when the security policy requires coordination of many resources, which is central to many of these potential applications. We develop new models and algorithms that scale to much more complex instances of security games. The key idea is to use a compact model of security games, which allows exponential improvements in both memory and runtime relative to the best known algorithms for solving general Stackelberg games. We develop even faster algorithms for security games under payoff restrictions that are natural in many security domains. Finally, introduce additional realistic scheduling constraints while retaining comparable performance improvements. The empirical evaluation comprises both random data and realistic instances of the FAMS and LAX problems. Our new methods scale to problems several orders of magnitude larger than the fastest known algorithm.

View Paper: https://www.semanticscholar.org/paper/40c38a2f33bce74a9681a58f2b2bcb1e0b9ecd23

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

Refinement of Strong Stackelberg Equilibria in Security Games (2011, background): “Formally, the defender’s mixed strategy can be compactly represented as a coverage vector c= 〈ct〉 where ct is the probability that target t is covered (Kiekintveld et al. 2009; Yin et al. 2010).”
From physical security to cybersecurity (2015, background): “A key assumption of SSG (we will sometimes refer to them as simply security games) is that the payoff of an outcome depends only on the target attacked, and whether or not it is “covered” (protected) by the defender [12].”
Solving Partially Observable Stochastic Games with Public Observations (2019, methodology): “Game-theoretic strategies are used to protect critical infrastructures (Pita et al. 2008; Kiekintveld et al. 2009; Shieh et al. 2012), secure computer networks (Vanek et al. 2012; Nguyen, Wellman, and Singh 2017; Durkota et al. 2017) or wildlife (Fang, Stone, and Tambe 2015; Fang et al. 2016).”
Stackelberg vs. Nash in Security Games: An Extended Investigation of Interchangeability, Equivalence, and Uniqueness (2011, methodology): “…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, 2010).”