TY - JOUR
T1 - A Stackelberg security game with random strategies based on the extraproximal theoretic approach
AU - Trejo, Kristal K.
AU - Clempner, Julio B.
AU - Poznyak, Alexander S.
N1 - Publisher Copyright:
© 2014 Elsevier Ltd.
PY - 2015/1/1
Y1 - 2015/1/1
N2 - In this paper we present a novel approach for representing a real-world attacker-defender Stackelberg security game-theoretic model based on the extraproximal method. We focus on a class of ergodic controlled finite Markov chain games. The extraproximal problem formulation is considered as a nonlinear programming problem with respect to stationary distributions. The Lagrange principle and Tikhonov's regularization method are employed to ensure the convergence of the cost functions. We transform the problem into a system of equations in a proximal format, and a two-step (prediction and basic) iterated procedure is applied to solve the formulated problem. In particular, the extraproximal method is employed for computing mixed strategies, providing a strong optimization formulation to compute the Stackelberg/Nash equilibrium. Mixed strategies are especially found when the resources available for both the defender and the attacker are limited. In this sense, each equation in this system is an optimization problem for which the minimum is found using a quadratic programming approach. The model supports a defender and N attackers. In order to address the dynamic execution uncertainty in security patrolling, we provide a game-theoretic based method for scheduling randomized patrols. Simulation results provide a validations of our approach.
AB - In this paper we present a novel approach for representing a real-world attacker-defender Stackelberg security game-theoretic model based on the extraproximal method. We focus on a class of ergodic controlled finite Markov chain games. The extraproximal problem formulation is considered as a nonlinear programming problem with respect to stationary distributions. The Lagrange principle and Tikhonov's regularization method are employed to ensure the convergence of the cost functions. We transform the problem into a system of equations in a proximal format, and a two-step (prediction and basic) iterated procedure is applied to solve the formulated problem. In particular, the extraproximal method is employed for computing mixed strategies, providing a strong optimization formulation to compute the Stackelberg/Nash equilibrium. Mixed strategies are especially found when the resources available for both the defender and the attacker are limited. In this sense, each equation in this system is an optimization problem for which the minimum is found using a quadratic programming approach. The model supports a defender and N attackers. In order to address the dynamic execution uncertainty in security patrolling, we provide a game-theoretic based method for scheduling randomized patrols. Simulation results provide a validations of our approach.
KW - Extraproximal method
KW - Finite Markov chains
KW - Security games
KW - Strong Stackelberg equilibrium
UR - http://www.scopus.com/inward/record.url?scp=84910663262&partnerID=8YFLogxK
U2 - 10.1016/j.engappai.2014.09.002
DO - 10.1016/j.engappai.2014.09.002
M3 - Artículo
SN - 0952-1976
VL - 37
SP - 145
EP - 153
JO - Engineering Applications of Artificial Intelligence
JF - Engineering Applications of Artificial Intelligence
ER -