Simulation-based methods in multi-step Stackelberg Security Games in the context of homeland security

The project was financed by the National Science Centre grant number DEC-2017/25/B/ST6/02061.

Popular Science Summary

The globalization of threats in the area of public security (international terrorism, arms or drug trafficking) has become one of the key problems of the 21st century. As a result, there has been a dynamic development of modern, research-supported methods for combating them. One of the developing areas of research in this field is Security Games, which involve modeling tactical situations related to countering threats as games and searching for optimal strategies within these models. They model asymmetric interactions between a defender and an attacker under conditions of incomplete information.

The primary scientific goal of the project is to develop qualitatively new methodologies for solving multi-step Security Games (constituting a variant of the so-called Stackelberg Games) based on Monte-Carlo simulations and evolutionary methods.

Developed Algorithmic Methods

Due to the computational complexity (NP-hardness) of determining the Stackelberg Equilibrium in multi-step games, research efforts have moved away from classical exact methods based on linear programming (MILP) in favor of scalable metaheuristics. Within the framework of the project, a number of unique approaches were proposed and examined:

  • Algorithms based on Monte Carlo Tree Search (MCTS): Methods (Mixed-UCT, O2UCT) were proposed that utilize Monte Carlo game tree search to estimate optimal mixed strategies. Thanks to iterative sampling of the attacker's strategy space and the application of a "double-oracle" type approach, these solutions allow for the effective determination of strategies in general-sum games.

  • Evolutionary and Memetic Approach: Generic evolutionary algorithms (EASG) were designed to evolve populations of defender strategies. These methods were extended to support signaling games (EASGS), taking into account the use of drones and sensors as well as detection uncertainty. Memetic algorithms were also introduced, enriching evolution with local strategy optimization to improve solution quality.

  • Strategy Coevolution: Coevolutionary systems (CoEvoSG) were created, in which two competing populations evolve simultaneously: defender strategies and attacker strategies. The application of a "Hall of Fame" mechanism based on the Nash Equilibrium allowed for the stabilization of the learning process and faster convergence, eliminating the need for a costly search of the opponent's entire response space.

  • Neuroevolution: Methods utilizing neural networks to evaluate strategy quality (NESG, DNESG) were developed. These networks, trained on historical data, act as surrogate models, enabling instant comparison of strategies in evolutionary tournaments without the need to conduct full game simulations. This approach allows for the approximation of the attacker's decision model without a priori knowledge of their preferences.

  • Modeling Bounded Rationality: Scenarios were analyzed in which the opponent does not behave in a perfectly rational manner. Psychological models, such as Anchoring Theory and Prospect Theory, were integrated into optimization algorithms. Experiments conducted with human participants confirmed that strategies generated taking into account these cognitive biases (e.g., using the ATSGL variant for MILP methods or appropriate variants of heuristic methods) allow the defender to achieve higher scores when facing real opponents.

  • Augmented Decision Space Optimization (ADSO): An optimization method in an augmented decision space was proposed, utilizing binary variables to control solution sparsity. This approach enables the generation of more compact defense strategies, which significantly improves computational scalability in very large game instances.

Results and Applications

The conducted experiments showed that the proposed metaheuristic methods offer close-to-linear time scalability and almost constant memory usage, which constitutes a significant advantage over the exponential complexity of classical solvers. As a result, these algorithms make it possible to solve games of sizes and time horizons that were previously unattainable for exact methods.

The methods were verified on various scenarios, including:

  • Protection of physical infrastructure (Warehouse Games, Search Games).
  • Cybersecurity (FlipIt, Deep Packet Inspection games).
  • Protection of natural resources (Green Security Games) using patrols and warning systems.
  • Protection of moving targets (e.g., passenger ferries).