Urban Security: Game-Theoretic Resource Allocation in Networked Physical Domains
J Tsai, Z Yin, J Kwak, D Kempe, C Kiekintveld, and M Tambe
In Twenty-Fourth Conference on Artificial Intelligence (AAAI 2010).
This is the author's version of the work.
It is posted here by permission of AAAI for personal use, not for redistribution.
Download
Abstract
Law enforcement agencies frequently must allocate limited resources to protect targets embedded in a network, such as important buildings in a city road network. Since intelligent attackers may observe and exploit patterns in the allocation, it is crucial that the allocations be randomized. We cast this problem as an attacker-defender Stackelberg game: the defender's goal is to obtain an optimal mixed strategy for allocating resources. The defender's strategy space is exponential in the number of resources, and the attacke's exponential in the network size. Existing algorithms are therefore useless for all but the smallest networks.
We present a solution approach based on two key ideas: (i) A polynomial-sized game model obtained via an approximation of the strategy space, solved efficiently using a linear program; (ii) Two efficient techniques that map solutions from the approximate game to the original, with proofs of correctness under certain assumptions. We present in-depth experimental results, including an evaluation on part of the Mumbai road network.
Previous versions
How to Protect a City: Strategic Security Placement in Graph-Based Domains (Extended Abstract).
(J Tsai, Z Yin, J Kwak, D Kempe, C Kiekintveld, and M Tambe)
In Ninth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010) (Extended Abstract), May 2010.
