Solving zero-sum security games in discretized spatio-temporal domains


Conference Paper

Copyright © 2014, Association for the Advancement of Artificial Intelligence ( All rights reserved. Among the many deployment areas of Stackelberg Security games, a major area involves games played out in space and time, which includes applications in muitipte mobile defender resources protecting multiple mobile targets. Previous algorithms for such spatio-temporal security games fail to scale-up and little is known of the 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 difficult to find, we propose approximations or prove hardness results.

Duke Authors

Cited Authors

  • Xu, H; Fang, F; Jiang, AX; Conitzer, V; Dughmi, S; Tambe, M

Published Date

  • January 1, 2014

Published In

  • Proceedings of the National Conference on Artificial Intelligence

Volume / Issue

  • 2 /

Start / End Page

  • 1500 - 1506

International Standard Book Number 13 (ISBN-13)

  • 9781577356783

Citation Source

  • Scopus