Efficient Approximation for Security Games with Interval Uncertainty

C Kiekintveld and V Kreinovich

In Proceedings of the AAAI Spring Symposium on Game Theory for Security, Sustainability, and Health (GTSSH 2012).

This is the author's version of the work.

Download

Abstract

There are an increasing number of applications of security games. One of the key challenges for this field going forward is to address the problem of model uncertainty and the robustness of the game-theoretic solutions. Most existing methods for dealing with payoff uncertainty are Bayesian methods which are NP-hard and have difficulty scaling to very large problems. In this work we consider an alternative approach based on interval uncertainty. For a variant of security games with interval uncertainty we introduce a polynomial-time approximation algorithm that can compute very accurate solutions within a given error bound.