@mastersthesis {1503631,
	title = {Addressing Uncertainty in Stackelberg Games for Security: Models and Algorithms },
	year = {2013},
	type = {PhD thesis},
	abstract = {Recently, there has been significant research interest in using game-theoretic approaches to allocate limited security resources to protect physical infrastructure including ports, airports, transit systems, and other critical national infrastructure as well as natural resources such as forests,
tigers, fish, and so on. Indeed, the leader-follower Stackelberg game model is at the heart of many
deployed applications. In these applications, the game model provides a randomized strategy for
the leader (security forces), under the assumption that the adversary will conduct surveillance
before launching an attack. Inevitably, the security forces are faced with the problem of uncertainty. For example, a security officer may be forced to execute a different patrol strategy from the
planned one due to unexpected events. Also, there may be significant uncertainty regarding the
amount of surveillance conducted by an adversary. While Bayesian Stackelberg games for modeling discrete uncertainty have been successfully used in deployed applications, they are NP-hard
problems and existing methods perform poorly in scaling up the number of types: inadequate for
complex real world problems. Furthermore, Bayesian Stackelberg games have not been applied
to model execution and observation uncertainty and finally, they require the availability of full
distributional information of the uncertainty. To overcome these difficulties, my thesis presents four major contributions. First, I provide
a novel algorithm Hunter for Bayesian Stackelberg games to scale up the number of types. Exploiting the efficiency of Hunter, I show preference, execution and observation uncertainty can
be addressed in a unified framework. Second, to address execution and observation uncertainty
(where distribution may be difficult to estimate), I provide a robust optimization formulation to
compute the optimal risk-averse leader strategy in Stackelberg games. Third, addressing the uncertainty of the adversary{\textquoteright}s capability of conducting surveillance, I show that for a class of Stackelberg games motivated by real security applications, the leader is always best-responding with a
Stackelberg equilibrium strategy regardless of whether the adversary conducts surveillance or not.
As the final contribution, I provide TRUSTS, a novel game-theoretic formulation for scheduling
randomized patrols in public transit domains where timing is a crucial component. TRUSTS
addresses dynamic execution uncertainty in such spatiotemporal domains by integrating Markov
Decision Processes into the game-theoretic model. Simulation results as well as real-world trials
of TRUSTS in the Los Angeles Metro Rail system provide validations of my approach.},
	author = {Yin, Zhengyu}
}
