Computing Optimal Mixed Strategies for Security Games with Dynamic Payoffs

Yin, Yue; Xu, Haifeng; Gan, Jiarui; An, Bo; Jiang, Albert Xin

Computing Optimal Mixed Strategies for Security Games with Dynamic Payoffs

Yue Yin, Haifeng Xu, Jiarui Gan, Bo An, Albert Xin Jiang

Download BibTeX Cite

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 681-687.

Abstract

Security agencies in the real world often need to protect targets with time-dependent values, e.g., tourist sites where the number of travelers changes over time. Since the values of different targets often change asynchronously, the defender can relocate security resources among targets dynamically to make the best use of limited resources. We propose a game-theoretic scheme to develop dynamic, randomized security strategies in consideration of adversary's surveillance capability. This differs from previous studies on security games by considering varying target values and continuous strategy spaces of the security agency and the adversary. The main challenge lies in the computational intensiveness due to the continuous, hence infinite strategy spaces. We propose an optimal algorithm and an arbitrarily near-optimal algorithm to compute security strategies under different conditions. Experimental results show that both algorithms significantly outperform existing approaches.

Yue Yin, Haifeng Xu, Jiarui Gan, Bo An, and Albert Xin Jiang. 2015. Computing Optimal Mixed Strategies for Security Games with Dynamic Payoffs. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15. IJCAI, 681–687. https://ijcai.org/proceedings/2015/102

@inproceedings{ijcai2015p102,
  title     = {Computing Optimal Mixed Strategies for Security Games with Dynamic Payoffs},
  author    = {Yin, Yue and Xu, Haifeng and Gan, Jiarui and An, Bo and Jiang, Albert Xin},
  booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-15}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Qiang Yang and Michael Wooldridge},
  pages     = {681--687},
  year      = {2015},
  month     = {7},
  note      = {Main Track},
  url       = {https://ijcai.org/proceedings/2015/102},
}

TY  - CPAPER
TI  - Computing Optimal Mixed Strategies for Security Games with Dynamic Payoffs
AU  - Yin, Yue
AU  - Xu, Haifeng
AU  - Gan, Jiarui
AU  - An, Bo
AU  - Jiang, Albert Xin
T2  - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2015
SP  - 681
EP  - 687
UR  - https://ijcai.org/proceedings/2015/102
ER  -