Abstract

Protecting critical infrastructure from intentional damage requires considering the behavior of attackers. This problem can be formulated as a Stackelberg security game. Here, a "defender" must protect specific targets with limited resources, maximizing its expected utility and considering that a second player, called "attacker", responds optimally. One of the challenges in solving Stackelberg games in real applications is the size of the problem. In general, finding optimal strategies for Stackelberg games is NP-Hard. Our primary goal is to establish the connections between the algorithmic implications of the polyhedral structure of the defender’s strategy set and the development and implementation of efficient solution methods and algorithms on a large scale. The first point relates to analyzing the difficulty of solving a Stackelberg security game and the defender’s strategy space structure. To this end, we study security games with defender strategies that can be modeled as perfect formulations, such as b-matchings and schedules of size 2. The second point implies evaluating efficient solution methods. In this context, we use formulations that either describe the set of pure strategies explicitly or describe the space through marginal probabilities. We develop branch&price and branch&cut schemes to deal with large instances, and we study several algorithmic enhancements as stabilization methods and heuristics to get good initial feasible solutions.