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).
AbstractProtecting 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.