Scaling-Up Security Games with Boundedly Rational Adversaries: A Cutting-Plane Approach / 404
Rong Yang, Albert Xin Jiang, Milind Tambe, Fernando Ordóñez

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.