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 ef?ciently 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 C O C O M O. Therefore, we next present a novel cutting-plane algorithm called B LADE to scale-up SSGs with complex adversary models,with three key novelties: (i) an ef?cient scalable separation oracle to generate deep cuts; (ii) a heuristic that uses gradient to further improve the cuts; (iii) techniques for quality-ef?ciency tradeoff.