Solving Zero-Sum Security Games in Discretized Spatio-Temporal Domains
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.
Cite
Text
Xu et al. "Solving Zero-Sum Security Games in Discretized Spatio-Temporal Domains." AAAI Conference on Artificial Intelligence, 2014. doi:10.1609/AAAI.V28I1.8878Markdown
[Xu et al. "Solving Zero-Sum Security Games in Discretized Spatio-Temporal Domains." AAAI Conference on Artificial Intelligence, 2014.](https://mlanthology.org/aaai/2014/xu2014aaai-solving/) doi:10.1609/AAAI.V28I1.8878BibTeX
@inproceedings{xu2014aaai-solving,
title = {{Solving Zero-Sum Security Games in Discretized Spatio-Temporal Domains}},
author = {Xu, Haifeng and Fang, Fei and Jiang, Albert Xin and Conitzer, Vincent and Dughmi, Shaddin and Tambe, Milind},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2014},
pages = {1500-1506},
doi = {10.1609/AAAI.V28I1.8878},
url = {https://mlanthology.org/aaai/2014/xu2014aaai-solving/}
}