Computing Optimal Randomized Resource Allocations for Massive Security Games
Christopher D. Kiekintveld, Manish Jain, Jason Tsai, James Pita, Fernando Ivan Ordonez, Milind Tambe · Cambridge University Press eBooks · 2011
Introduction Providing security for transportation systems, computer networks, and other critical infrastructure is a large and growing problem. Central to many of these security problems is a resource allocation task. For example, a police force may have limited personnel to conduct patrols, operate checkpoints, and conduct random searches. Other scarce resources including bomb-sniffing canines, vehicles, and security cameras. The key question is how to efficiently allocate these resources to protect against a wide variety of potential threats. The adversarial aspect of security domains poses unique challenges for resource allocation. A motivated attacker can gather information about security measures using surveillance and plan more effective attacks. Predictable resource allocations may be exploited by an attacker, greatly reducing resource effectiveness. A better approach for deploying security resources is to use randomization to increase the uncertainty of potential attackers. We develop new computational methods that use game-theoretic analysis to generate optimal randomized resource allocations for security domains. Game theory offers a more sophisticated approach to randomization than simply “rolling dice.” It allows the analyst to factor differential risks and values into the game model, and incorporates game-theoretic predictions of how the attacker will respond to a given security policy. Recent work by Paruchuri et al. uses a game-theoretic approach to create randomized security policies for traffic checkpoints and canine patrols at the Los Angeles International Airport (LAX), which are deployed in the daily airport-security operations (Paruchuri et al., 2008; Pita et al., 2008).