Commitment to Sparse Strategies in Two-Player Games
Salam Afiouni,
Jakub Cerny,
Chun Kai Ling,
Christian Kroer
December 2024
Abstract
While Nash equilibria are guaranteed to exist, they may exhibit dense support, making them difficult to understand and execute in some applications. In this paper, we study -sparse commitments in games where one player is restricted to mixed strategies with support size at most k. Finding k-sparse commitments is known to be computationally hard. We start by showing several structural properties of -sparse solutions, including that the optimal support may vary dramatically as k increases. These results suggest that naive greedy or double-oracle-based approaches are unlikely to yield practical algorithms. We then develop a simple approach based on mixed integer linear programs (MILPs) for zero-sum games, general-sum Stackelberg games, and various forms of structured sparsity. We also propose practical algorithms for cases where one or both players have large (i.e., practically innumerable) action sets, utilizing a combination of MILPs and incremental strategy generation. We evaluate our methods on synthetic and real-world scenarios based on security applications. In both settings, we observe that even for small support sizes, we can obtain more than 90% of the true Nash value while maintaining a reasonable runtime, demonstrating the significance of our formulation and algorithms.
Publication
Commitment to Sparse Strategies in Two-Player Games