@conference {1506498,
	title = {Game-Theoretic Allocation of Security Forces in a City },
	booktitle = {AAMAS 2010 workshop on Optimization in Multiagent Systems},
	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}
}
