Defender-Attacker Stackelberg games are the foundations of toolsdeployed for computing optimal patrolling strategies in adversarialdomains such as the United states Federal Air Marshals Service and the UnitedStates Coast Guard, among others.In Stackelberg game models of these systems the attacker knows only theprobability that each target is covered by the defender, but isoblivious to the detailed timing of the coverage schedule.In many real-world situations, however, the attacker can observe thecurrent location of the defender and can exploit this knowledge toreason about the defender's future moves.We study Stackelberg security games in which the defender sequentiallymoves between targets, with moves constrained by an exogenouslyspecified graph, while the attacker can observe the defender's currentlocation and his (stochastic) policy concerning future moves. We offerfive contributions: (1) We model this adversarial patrolling game (APG) as a stochastic game with special structure and presentseveral alternative formulations that leverage the general non-linearprogramming (NLP) approach for computing equilibria in zero-sumstochastic games. We show that our formulations yield significantlybetter solutions than previous approaches. (2) We extend theNLP formulation for APG allow for attacks that may take multiple timesteps to unfold.(3) We provide anapproximate MILP formulation that uses discrete defender moveprobabilities. (4) We experimentally demonstrate the efficacy of anNLP-based approach, and systematically study the impact of networktopology on the results.(5) We extend our model to allow the defender to construct the graph constraining his moves, at some cost, and offer novel algorithms for this setting, finding that a MILP approximation is much more effective than the exact NLP in this setting.
Shieh, Eric Anyung (University of Southern California) | An, Bo (University of Southern California) | Yang, Rong (University of Southern California) | Tambe, Milind (University of Southern California) | Baldwin, Craig (United States Coast Guard) | DiRenzo, Joseph (United States Coast Guard) | Maule, Ben (United States Coast Guard) | Meyer, Garrett (United States Coast Guard)
Building upon previous security applications of computational game theory, this paper presents PROTECT, a game-theoretic system deployed by the United States Coast Guard (USCG) in the port of Boston for scheduling their patrols. USCG has termed the deployment of PROTECT in Boston a success, and efforts are underway to test it in the port of New York, with the potential for nationwide deployment. PROTECT is premised on an attacker-defender Stackelberg game model and offers five key innovations. First, this system is a departure from the assumption of perfect adversary rationality noted in previous work, relying instead on a quantal response (QR) model of the adversary's behavior - to the best of our knowledge, this is the first real-world deployment of the QR model. Second, to improve PROTECT's efficiency, we generate a compact representation of the defender's strategy space, exploiting equivalence and dominance. Third, we show how to practically model a real maritime patrolling problem as a Stackelberg game. Fourth, our experimental results illustrate that PROTECT's QR model more robustly handles real-world uncertainties than a perfect rationality model. Finally, in evaluating PROTECT, this paper provides real-world data: (i) comparison of human-generated vs PROTECT security schedules, and (ii) results from an Adversarial Perspective Team's (human mock attackers) analysis.
Carthy, Sara Marie Mc (University of Southern California) | Tambe, Milind (University of Southern California) | Kiekintveld, Christopher (University of Texas at El Paso) | Gore, Meredith L. (Michigan State University) | Killion, Alex (Michigan State University)
Green security — protection of forests, fish and wildlife — is a critical problem in environmental sustainability. We focus on the problem of optimizing the defense of forests againstillegal logging, where often we are faced with the challenge of teaming up many different groups, from national police to forest guards to NGOs, each with differing capabilities and costs. This paper introduces a new, yet fundamental problem: SimultaneousOptimization of Resource Teams and Tactics (SORT). SORT contrasts with most previous game-theoretic research for green security — in particular based onsecurity games — that has solely focused on optimizing patrolling tactics, without consideration of team formation or coordination. We develop new models and scalable algorithms to apply SORT towards illegal logging in large forest areas. We evaluate our methods on a variety of synthetic examples, as well as a real-world case study using data from our on-going collaboration in Madagascar .
Stackelberg security games have been widely deployed in recent years to schedule security resources. An assumption in most existing security game models is that one security resource assigned to a target only protects that target. However, in many important real-world security scenarios, when a resource is assigned to a target, it exhibits protection externalities: that is, it also protects other “neighbouring” targets. We investigate such Security Games with Protection Externalities (SPEs). First, we demonstrate that computing a strong Stackelberg equilibrium for an SPE is NP-hard, in contrast with traditional Stackelberg security games which can be solved in polynomial time. On the positive side, we propose a novel column generation based approach—CLASPE—to solve SPEs. CLASPE features the following novelties: 1) a novel mixed-integer linear programming formulation for the slave problem; 2) an extended greedy approach with a constant-factor approximation ratio to speed up the slave problem; and 3) a linear-scale linear programming that efficiently calculates the upper bounds of target-defined subproblems for pruning. Our experimental evaluation demonstrates that CLASPE enable us to scale to realistic-sized SPE problem instances.
Stackelberg security games form the backbone of systems like ARMOR, IRIS and PROTECT, which are in regular use by the Los Angeles International Police, US Federal Air Marshal Service and the US Coast Guard respectively. An understanding of the runtime required by algorithms that power such systems is critical to furthering the application of game theory to other real-world domains. This paper identifies the concept of the deployment-to-saturation ratio in random Stackelberg security games, and shows that problem instances for which this ratio is 0.5 are computationally harder than instances with other deployment-to-saturation ratios for a wide range of different equilibrium computation methods, including (i) previously published different MIP algorithms, and (ii) different underlying solvers and solution mechanisms. This finding has at least two important implications. First, it is important for new algorithms to be evaluated on the hardest problem instances. We show that this has often not been done in the past, and introduce a publicly available benchmark suite to facilitate such comparisons. Second, we provide evidence that this computationally hard region is also one where optimization would be of most benefit to security agencies, and thus requires significant attention from researchers in this area. Furthermore, we use the concept of phase transitions to better understand this computationally hard region. We define a decision problem related to security games, and show that the probability that this problem has a solution exhibits a phase transition as the deployment-to-saturation ratio crosses 0.5. We also demonstrate that this phase transition is invariant to changes both in the domain and the domain representation, and that the phase transition point corresponds to the computationally hardest instances.