@conference {1506366,
	title = {Urban Security: Game-Theoretic Resource Allocation in Networked Physical Domains },
	booktitle = {National Conference on Artificial Intelligence (AAAI)},
	year = {2010},
	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{\textquoteright}s goal is to obtain an optimal mixed strategy for allocating resources. The defender{\textquoteright}s strategy space is exponential
in the number of resources, and the attacker{\textquoteright}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.},
	author = {Tsai, Jason and Yin, Zhengyu and Kwak, Jun-young and David Kempe and Kiekintveld, Christopher and Tambe, Milind}
}
