Augmented Decision Spaces for Stackelberg Security Games: Sparse evolution begets scalability
Abstract
This paper introduces the Augmented Decision Space Optimization (ADSO) method for sparsity-driven optimization of mixed-strategies in Stackelberg Security Games (SSGs). The proposed method enhances traditional strategy optimization by combining binary variables to represent the presence of pure strategies with real-valued variables to refine their selection probabilities. Specifically, instead of waiting for an evolutionary process to gradually discover sparse solutions, the binary variables in ADS allow the real-valued variables to be switched on or off, thereby directly enforcing sparsity. This dual codification scheme achieves targets such as sparsification and computational efficiency in large-scale games. We demonstrate that ADS outperforms existing heuristic methods, offering superior solution quality, scalability, and stability. Empirical results across three different benchmark games show that ADS generates compact strategies with minimal computational overhead, achieving performance close to the exact methods. Furthermore, state-of-the-art results are obtained for problems where exact methods fail to scale effectively. Our framework promises broad applicability beyond SSGs, encompassing a wide range of game-theoretic and combinatorial optimization problems.
Authors: Adam Żychowski, Abhishek Gupta, Yew-Soon Ong, Jacek Mańdziuk
Published in: Genetic and Evolutionary Computation Conference (GECCO) (2025)