@conference {1506767,
	title = {Computing Optimal Randomized Resource Allocations for Massive Security Games },
	booktitle = {The Eighth International Conference on Autonomous Agents and Multiagent Systems},
	year = {2009},
	abstract = {Predictable allocations of security resources such as police officers, canine units, or checkpoints are vulnerable to exploitation
by attackers. Recent work has applied game-theoretic methods
to find optimal randomized security policies, including a fielded
application at the Los Angeles International Airport (LAX). This
approach has promising applications in many similar domains, including police patrolling for subway and bus systems, randomized
baggage screening, and scheduling for the Federal Air Marshal Service (FAMS) on commercial flights. However, the existing methods scale poorly when the security policy requires coordination of
many resources, which is central to many of these potential applications.
We develop new models and algorithms that scale to much more
complex instances of security games. The key idea is to use a compact model of security games, which allows exponential improvements in both memory and runtime relative to the best known algorithms for solving general Stackelberg games. We develop even
faster algorithms for security games under payoff restrictions that
are natural in many security domains. Finally, introduce additional
realistic scheduling constraints while retaining comparable performance improvements. The empirical evaluation comprises both
random data and realistic instances of the FAMS and LAX problems. Our new methods scale to problems several orders of magnitude larger than the fastest known algorithm.},
	author = {Kiekintveld, Christopher and Jain, Manish and Tsai, Jason and Pita, James and Ord{\'o}{\~n}ez, Fernando and Tambe, Milind}
}
