Solving Stackelberg Security Games For Multiple Defenders and Multiple Attackers

Abstract

In the last years, there has been a substantial effort in the application of Stackelberg game-theoretic approaches in the security arena, in which security agencies implement patrols and checkpoints to protect targets from criminal attacks. The classical game-theoretic approach employed successful to solve security games is that of a Stackelberg game between a defender (leader) and an attacker (follower). In this work we present a novel approach for computing optimal randomized security policies in non-cooperative Stackelberg security games for multiple defenders and attackers. The solution is based on the extraproximal method and its extension to Markov chains. We compute the unique Stackelberg/Nash equilibrium of the security game employing the Lagrange principle and introducing the Tikhonov regularizator method. We consider a game-theory realization based on a discrete-time random walk of the problem supported by the Kullback-Leibler divergence. Finally, we illustrate the usefulness of the proposed method with an application example in the security arena.