How to Protect a City: Strategic Security Placement in Graph-Based Domains


Jason Tsai, Zhengyu Yin, Jun-young Kwak, David Kempe, Christopher Kiekintveld, and Milind Tambe. 2010. “How to Protect a City: Strategic Security Placement in Graph-Based Domains .” In Extended Abstract for International Conference on Autonomous Agents and Multiagent Systems (AAMAS).


Protecting targets against potential attacks is an important problem for security forces worldwide. The general setting we study is as follows: An attacker assigns different values to reaching (and damaging or destroying) one of multiple targets. A defender is able to allocate resources (such as patrol cars or canine units) to capture the attacker before he reaches a target. In many of these situations, the domain has structure that is naturally modeled as a graph. For example, city maps can be modeled with intersections as nodes and roads as edges, where nodes are targets for attackers. In order to prevent attacks, security forces can schedule checkpoints on edges (e.g., roads) to detect intruders. For instance, in response to the devastating terrorist attacks in 2008 [1], Mumbai police deploy randomized checkpoints as one countermeasure to prevent future attacks [2]. The strategy for placing these checkpoints must necessarily be decided in advance of attack attempts, should account for targets of differing importance, and should anticipate an intelligent adversary who can observe the strategy prior to attacking. In light of these requirements, game-theoretic approaches have been developed to assist in generating randomized security strategies in several real-world domains, including applications in use by the Los Angeles International Airport [12] and the Federal Air Marshals Service [13]. To account for the attacker’s ability to observe deployment patterns, these methods model the problem as a Stackelberg game and solve for an optimal probability distribution over the possible deployments to ensure unpredictability. Novel solvers for classes of security games have recently been developed [3, 11, 4]. However, these solvers take time at least polynomial in the number of actions of both players. In our setting, every path from an entry point to a target is an attacker action, and every set of r or fewer edges is a defender action. (r is the maximum number of checkpoints.) Since the attacker’s actions grow exponentially with the size of the network, and the defender’s actions grow exponentially with r, existing methods quickly become too slow when applied to large real-world domains. Therefore, our goal is to develop faster methods for these settings and evaluate them theoretically and empirically.
See also: 2010