@conference {1503275,
	title = {Addressing Scalability and Robustness in Security Games with Multiple Boundedly Rational Adversaries },
	booktitle = {Conference on Decision and Game Theory for Security (GameSec)},
	year = {2014},
	abstract = {Boundedly rational human adversaries pose a serious challenge to security because they deviate from the classical assumption of
perfect rationality. An emerging trend in security game research addresses this challenge by using behavioral models such as quantal response (QR) and subjective utility quantal response (SUQR). These
models improve the quality of the defender{\textquoteright}s strategy by more accurately
modeling the decisions made by real human adversaries. Work on incorporating human behavioral models into security games has typically followed two threads. The first thread, scalability, seeks to develop efficient
algorithms to design patrols for large-scale domains that protect against
a single adversary. However, this thread cannot handle the common situation of multiple adversary types with heterogeneous behavioral models.
Having multiple adversary types introduces considerable uncertainty into
the defender{\textquoteright}s planning problem. The second thread, robustness, uses either Bayesian or maximin approaches to handle this uncertainty caused
by multiple adversary types. However, the robust approach has so far
not been able to scale up to complex, large-scale security games. Thus,
each of these two threads alone fails to work in key real world security
games. Our present work addresses this shortcoming and merges these
two research threads to yield a scalable and robust algorithm, MIDAS
(MaxImin Defense Against SUQR), for generating game-theoretic patrols
to defend against multiple boundedly rational human adversaries. Given
the size of the defender{\textquoteright}s optimization problem, the key component of
MIDAS is incremental cut and strategy generation using a master/slave
optimization approach. Innovations in MIDAS include (i) a maximin
mixed-integer linear programming formulation in the master and (ii) a
compact transition graph formulation in the slave. Additionally, we provide a theoretical analysis of our new model and report its performance
in simulations. In collaboration with the United States Coast Guard
(USCG), we consider the problem of defending fishery stocks from illegal fishing in the Gulf of Mexico and use MIDAS to handle heterogeneity
in adversary types (i.e., illegal fishermen) in order to construct robust
patrol strategies for USCG assets.},
	author = {Brown, Matthew and William B. Haskell and Tambe, Milind}
}
