An augmented MDP approach for solving Stochastic Security Games

Abstract

We propose a novel theoretical approach for solving a Stochastic Security Game using augmented Markov Decison Processes and an experimental evaluation. Most of the previous works mentioned in the literature focus on Linear Programming techniques seeking Strong Stackelberg Equilibria through the defender and attacker’s strategy spaces. Although effective, these techniques are computationally expensive and tend to not scale well to very large problems. By fixing the set of the possible defense strategies, our approach is able to use the well-known augmented MDP formalism to compute an optimal policy for an attacker facing a defender patrolling. Experimental results on fully observable cases validate our approach and show good performances in comparison with optimistic and pessimistic approaches. However, these results also highlight the need of scalability improvements and of handling the partial observability cases.