@conference {1505637,
	title = {A Double Oracle Algorithm for Zero-Sum Security Games on Graphs },
	booktitle = {International Conference on Autonomous Agents and Multiagent Systems},
	year = {2011},
	abstract = {In response to the Mumbai attacks of 2008, the Mumbai police
have started to schedule a limited number of inspection checkpoints
on the road network throughout the city. Algorithms for similar
security-related scheduling problems have been proposed in recent
literature, but security scheduling in networked domains when targets have varying importance remains an open problem at large.
In this paper, we cast the network security problem as an attackerdefender zero-sum game. The strategy spaces for both players are
exponentially large, so this requires the development of novel, scalable techniques.
We first show that existing algorithms for approximate solutions
can be arbitrarily bad in general settings. We present RUGGED
(Randomization in Urban Graphs by Generating strategies for Enemy and Defender), the first scalable optimal solution technique for
such network security games. Our technique is based on a double
oracle approach and thus does not require the enumeration of the
entire strategy space for either of the players. It scales up to realistic
problem sizes, as is shown by our evaluation of maps of southern
Mumbai obtained from GIS data.},
	author = {Jain, Manish and Dmytro Korzhyk and Ondrej Vanek and Vincent Conitzer and Michal Pechoucek and Tambe, Milind}
}
