@mastersthesis {1504002,
	title = {Thwarting Adversaries with Unpredictability: Massive-scale Game-Theoretic Algorithms for Real-world Security Deployments },
	year = {2013},
	type = {PhD thesis},
	abstract = {Protecting critical infrastructure and targets such as airports, transportation networks, power
generation facilities as well as critical natural resources and endangered species is an important
task for police and security agencies worldwide. Securing such potential targets using limited
resources against intelligent adversaries in the presence of the uncertainty and complexities of
the real-world is a major challenge. My research uses a game-theoretic framework to model the
strategic interaction between a defender (or security forces) and an attacker (or terrorist adversary)
in security domains.
Game theory provides a sound mathematical approach for deploying limited security resources
to maximize their effectiveness. While game theory has always been popular in the arena of
security, unfortunately, the state of the art algorithms either fail to scale or to provide a correct
solution for large problems with arbitrary scheduling constraints. For example, US carriers fly over
27,000 domestic and 2,000 international flights daily, presenting a massive scheduling challenge
for Federal Air Marshal Service (FAMS).
My thesis contributes to a very new area that solves game-theoretic problems using insights
from large-scale optimization literature towards addressing the computational challenge posed by
real-world domains. I have developed new models and algorithms that compute optimal strategies
for scheduling defender resources is large real-world domains. My thesis makes the following contributions. First, it presents new algorithms that can solve for trillions of actions for both
the defender and the attacker. Second, it presents a hierarchical framework that provides orders
of magnitude scale-up in attacker types for Bayesian Stackelberg games. Third, it provides an
analysis and detection of a phase-transition that identifies properties that makes security games
hard to solve.
These new models have not only advanced the state of the art in computational game-theory,
but have actually been successfully deployed in the real-world. My work represents a successful
transition from game-theoretic advancements to real-world applications that are already in use, and
it has opened exciting new avenues to greatly expand the reach of game theory. For instance, my
algorithms are used in the IRIS system: IRIS has been in use by the Federal Air Marshals Service
(FAMS) to schedule air marshals on board international commercial flights since October 2009.},
	author = {Jain, Manish}
}
