Scaling-up Security Games with Boundedly Rational Adversaries: A Cutting-plane Approach

Yang, Rong; Jiang, Albert Xin; Tambe, Milind; Ordóñez, Fernando

Scaling-up Security Games with Boundedly Rational Adversaries: A Cutting-plane Approach

Rong Yang, Albert Xin Jiang, Milind Tambe, Fernando Ordóñez

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 404-409.

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.

Rong Yang, Albert Xin Jiang, Milind Tambe, and Fernando Ordóñez. 2013. Scaling-up Security Games with Boundedly Rational Adversaries: A Cutting-plane Approach. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13. IJCAI, 404–409. https://ijcai.org/proceedings/2013/67

@inproceedings{ijcai2013p67,
  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 = {Proceedings of the Twenty-Third International Joint Conference on
               Artificial Intelligence, {IJCAI-13}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Francesca Rossi},
  pages     = {404--409},
  year      = {2013},
  month     = {8},
  url       = {https://ijcai.org/proceedings/2013/67},
}

TY  - CPAPER
TI  - Scaling-up Security Games with Boundedly Rational Adversaries: A Cutting-plane Approach
AU  - Yang, Rong
AU  - Jiang, Albert Xin
AU  - Tambe, Milind
AU  - Ordóñez, Fernando
T2  - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2013
SP  - 404
EP  - 409
UR  - https://ijcai.org/proceedings/2013/67
ER  -