@conference {1501287,
	title = {Conquering Adversary Behavioral Uncertainty in Security Games: An Efficient Modeling Robust based Algorithm },
	booktitle = {30th AAAI Conference on Artificial Intelligence (AAAI) (Student Abstract)},
	year = {2016},
	abstract = {Real-world deployed applications of Stackelberg Security
Games (Shieh et al. 2012; Basilico, Gatti, and Amigoni
2009; Letchford and Vorobeychik 2011) have led to significant research emphasis on modeling the attacker{\textquoteright}s bounded
rationality (Yang et al. 2011; Nguyen et al. 2013). One key
assumption in behavioral modeling is the availability of a
significant amount of data to obtain an accurate prediction.
However, in real-world security domains such as the wildlife
protection, this assumption may be inapplicable due to the
limited access to real-world data (Lemieux 2014), leading
to uncertainty in the attacker{\textquoteright}s behaviors {\textemdash} a key research
challenge of security problems.
Recent research has focused on addressing uncertainty in
behavioral modeling, following two different approaches: 1)
one approach assumes a known distribution of multiple attacker types, each follows a certain behavioral model, and
attempts to solve the resulting Bayesian games (Yang et
al. 2014); and 2) another considers the existence of multiple attacker types of which behavioral models are perfectly
known, but without a known distribution over the types. It
then only considers the worst attacker type for the defender
(Brown, Haskell, and Tambe 2014). These two approaches
have several limitations. First, both still require a sufficient
amount of data to precisely estimate either the distribution
over attacker types (the former approach) or the model parameters for each individual type (the latter approach). Second, solving the resulting Bayesian games in the former case
is computationally expensive. Third, the latter approach
tends to be overly conservative as it only focuses on the
worst-case attacker type.
This paper remedies these shortcomings of state-of-theart approaches when addressing behavioral uncertainty in
SSG by providing three key contributions. First, we present
a new game model with uncertainty in which we consider a
single behavioral model to capture decision making of the
whole attacker population (instead of multiple behavioral
models); uncertainty intervals are integrated with the chosen
model to capture behavioral uncertainty. The idea of uncertainty interval is commonly used in literature (Aghassi and
Bertsimas 2006) and has been shown to effectively represent uncertainty in SSG (Kiekintveld, Islam, and Kreinovich
2013). Second, based on this game model, we propose a new
efficient robust algorithm that computes the defender{\textquoteright}s optimal strategy which is robust to the uncertainty.
Overall, the resulting robust optimization problem for
computing the defender{\textquoteright}s optimal strategy against the worst
case of behavioral uncertainty is a non-linear non-convex
fractional maximin problem. Our algorithm efficiently
solves this problem based on the following key insights: 1)
it converts the problem into a single maximization problem
via a non-linear conversion for fractional terms and the dual
of the inner minimization in maximin; 2) a binary search is
then applied to remove the fractional terms; and 3) the algorithm explores extreme points of the feasible solution region
and uses a piece-wise linear approximation to convert the
problem into a Mixed Integer Linear Program (MILP). Our
new algorithm provides an O(+
1
K
)-optimal solution where
 is the convergence threshold for the binary search and K
is the number of segments in the piecewise approximation.}
}
