Scalability via Sparsity in Stackelberg Security Games: An Augmented Decision Space Approach

This paper proposes the Augmented Decision Space Optimization (ADSO) framework for sparsity-driven optimization of mixed strategies in Stackelberg Security Games (SSGs). Unlike conventional evolutionary search processes that gradually converge toward sparse solutions, ADSO integrates binary variables to explicitly encode the inclusion or exclusion of pure strategies, while real-valued variables fine-tune their selection probabilities. This dual representation directly enforces sparsity and facilitates computational efficiency in large-scale problem instances. Extensive empirical studies on three benchmark games demonstrate that ADSO consistently produces compact strategies with minimal computational cost, achieving performance comparable to exact methods where they are feasible, and delivering state-of-the-art results in settings beyond the reach of such methods. Apart from SSGs, the framework exhibits strong potential for broader application to other game-theoretic and combinatorial optimization problems characterized by sparse solutions.