An iterative method for solving stackelberg security games: A Markov games approach

Stackelberg security games are represented by a Stackelberg model for multiple defenders and attackers. The dynamics of the game involves defenders trying to allocate their limited resources to defend important targets, and attackers observing the behavior of the defenders, look for the most advantageous target to harm. The computation of the equilibrium point is a fundamental issue for Stackelberg security games. This paper presents an iterative method for computing the equilibrium point in Stackelberg security Markov games. We first cast the problem as a Stackelberg game for multiple players in Markov chain games conceptualizing security games as polylinear games. Defenders and attackers are independently playing non-cooperatively in a Nash game restricted by a Stackelberg game. Then, we develop a new method for solving security games, that provides randomized patrolling strategies for optimizing resource allocation. For developing the method, we transform the problem into a system of independent equations where each is an optimization problem. The method involves two half steps: the first employs a proximal approach and the second a projection gradient method. We present a numerical example for showing the effectiveness of the method.