Moving targets security games with externalities

Abstract This paper investigates a realistic problem in which both defense and attack strategies exhibit externalities, and each target moves over time. Specifically, a security resource can protect not only one target but also all targets within a certain range of the resource's location, which is termed protection externalities. Analogously, when the attacker attacks a specific target, similar targets will also suffer damage simultaneously. We define this property as attack externalities. As the targets move, the set of targets affected by externalities changes dynamically, which is a significant departure from previous studies. We thus develop a moving target security game model with externalities and propose an efficient algorithm to solve it. Owing to the continuity of the trajectory and time, the strategy spaces are continuous. The algorithm proposes the methods for discretizing them, respectively. Subsequently, an attack strategy‐defined LP is constructed. However, the defense strategy space after discretization faces the challenge of exponential growth. The algorithm thus incorporates a column generation approach, in which the subproblem is formulated as a mixed‐integer linear programming model, solved by a fast greedy algorithm. The algorithm also proposes a linear programming model that determines the lower bound of each attack strategy‐defined problem. Finally, we demonstrate the scalability of the algorithm and the effectiveness of its components and show that externalities indeed provide greater benefits to players.