Scaling-up Security Games with Boundedly Rational Adversaries: A Cutting-Plane Approach
Abstract
To improve the current real-world deployments of Stackelberg security games (SSGs), it is critical now to efficiently incorporate models of adversary bounded rationality in large-scale SSGs. Unfortunately, previously proposed branch-and-price approaches fail to scale-up given the non-convexity of such models, as we show with a realization called COCOMO. Therefore, we next present a novel cutting-plane algorithm called BLADE to scale-up SSGs with complex adversary models, with three key novelties: (i) an efficient scalable separation oracle to generate deep cuts; (ii) a heuristic that uses gradient to further improve the cuts; (iii) techniques for quality-efficiency tradeoff.
Cite
Text
Yang et al. "Scaling-up Security Games with Boundedly Rational Adversaries: A Cutting-Plane Approach." International Joint Conference on Artificial Intelligence, 2013.Markdown
[Yang et al. "Scaling-up Security Games with Boundedly Rational Adversaries: A Cutting-Plane Approach." International Joint Conference on Artificial Intelligence, 2013.](https://mlanthology.org/ijcai/2013/yang2013ijcai-scaling/)BibTeX
@inproceedings{yang2013ijcai-scaling,
title = {{Scaling-up Security Games with Boundedly Rational Adversaries: A Cutting-Plane Approach}},
author = {Yang, Rong and Jiang, Albert Xin and Tambe, Milind and Ordóñez, Fernando},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2013},
pages = {404-410},
url = {https://mlanthology.org/ijcai/2013/yang2013ijcai-scaling/}
}