AAAI Publications, Twenty-Eighth AAAI Conference on Artificial Intelligence

Font Size: 
Solving Zero-Sum Security Games in Discretized Spatio-Temporal Domains
Haifeng Xu, Fei Fang, Albert Xin Jiang, Vincent Conitzer, Shaddin Dughmi, Milind Tambe

Last modified: 2014-06-21

Abstract


Among the many deployment areas of Stackelberg Security games, a major area involves games played out in space and time, which includes applications in multiple mobile defender resources protecting multiple mobile targets. Previous algorithms for such spatio-temporal security games fail to scale-up and little is known ofthe computational complexity properties of these problems.This paper provides a novel oracle-based algorithmic framework for a systematic study of different problem variants of computing optimal (minimax) strategies in spatio-temporal security games. Our framework enables efficient computation of a minimax strategy when the problem admits a polynomial-time oracle. Furthermore,for the cases in which efficient oracles are difficultto find, we propose approximations or prove hardness results.

Keywords


Security Games; Zero-Sum Games; Minimax Equilibrium; Oracle; Equilibria Computation

Full Text: PDF