Stackelberg security games: Computing the shortest-path equilibrium

In this paper we consider a game theory approach for representing a real-world attacker-defender Stackelberg security game. In this novel approach the behavior of an ergodic system (repeated stochastic Markov chain game) is represented by a Lyapunov-like function non-decreasing in time. Then, the representation of the Stackelberg security game is transformed in a potential game in terms of Lyapunov. We present a method for constructing a Lyapunov-like function: the function replaces the recursive mechanism with the elements of the ergodic system seeking to drive the underlying finite-state Stackelberg game to an equilibrium point along a least expected cost path. The proposed method analyzes both pure and mixed stationary strategies to find the strong Stackelberg equilibrium. Mixed strategies are found when the resources available for both the defender and the attacker are limited. Lyapunov games model how players are likely to behave in one-shot games and allow finishing during the game whether the applied best-reply strategy (pure or mixed) provides the convergence to a shortest-path equilibrium point (or not). We prove that Lyapunov games truly fit into the framework for deterministic and stochastic shortest-path security games. The convergence rate of the proposed method to a Stackelberg/Nash equilibrium is analyzed. Validity of the proposed method is successfully demonstrated both theoretically and by a simulated experiment.