Abstract

Protecting critical infrastructure from intentional damage requires foreseeing the strategies of the possible attackers. The problem faced by the Defender of such infrastructure can be formulated as a Stackelberg security game (SSG). A defender must decide what specific targets to protect with limited resources, maximizing their expected utility (e.g., minimizing damage value) and considering that a second player (or players), called attacker, responds in the best possible way. Since both Stackelberg games and Stackelberg security games are NP-Hard, the main challenge in finding optimal strategies in real applications consists in developing efficient methodologies for large instances. We focus on particular polyhedral structures of the Defender’s strategy set and the possible algorithmic implications of these structures. The structures we include here are those that can be modeled as perfect formulations, such as m nodes, m nodes with fairness considerations, b-matchings, combined resources with matching strategies, and trees. Once these structures are characterized, we propose efficient solution methods for SSG. We use several different formulations in the space of marginal probabilities, and we develop branch-and-cut schemes to deal with large instances. We test the proposed methods and compare them with each other and with other methods in the literature, whenever it is possible.