Abstract

Stackelberg security games are used as decision-support tools in security settings. The algorithms addressing these games generate optimal randomized schedules for distributing security resources. Unfortunately, finding optimal strategies for Bayesian Stackelberg games and Stackelberg security games is generally NP-Hard. Developing efficient methodologies to tackle large instances is essential to face this. We propose a branch-and-price scheme with novel and tighter constraints to find a Strong Stackelberg Equilibrium for Stackelberg games. We also provide a general algorithm generating upper and lower bounds for Stackelberg Security Games. We compare different methods and parameters for branch-and-price in these games, and we test and compare our proposed method to prior decomposition methods based on different integer programming formulations of Stackelberg games.