Catcher-Evader Games
This work addresses the challenge of handling uncertainty in security domains for researchers and practitioners, though it is incremental as it builds on existing game-theoretic solutions.
The paper tackles the problem of modeling uncertainty in security games by introducing a general catcher-evader framework that captures Bayesian security games, showing that computing Stackelberg strategies is NP-hard but providing an algorithm for Nash equilibrium that performs well in experiments.
Algorithms for computing game-theoretic solutions have recently been applied to a number of security domains. However, many of the techniques developed for compact representations of security games do not extend to {\em Bayesian} security games, which allow us to model uncertainty about the attacker's type. In this paper, we introduce a general framework of {\em catcher-evader} games that can capture Bayesian security games as well as other game families of interest. We show that computing Stackelberg strategies is NP-hard, but give an algorithm for computing a Nash equilibrium that performs well in experiments. We also prove that the Nash equilibria of these games satisfy the {\em interchangeability} property, so that equilibrium selection is not an issue.