Learning in Quasi-Linear Mechanisms
Ongoing
Publications
You can also find my articles on my Google Scholar profile.
Submitted and Ongoing Work
Colonel Blotto with Battlefield Games
Under Review
Publications by Year
2025
Commitment to Sparse Strategies in Two-Player Games
Published in Proceedings of the AAAI Conference on Artificial Intelligence, 2025
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 \(k\)-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 \(k\)-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 (ie, 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.
Recommended citation: Afiouni, S., Černý, J., Ling, C. K., & Kroer, C. (2025). Commitment to Sparse Strategies in Two-Player Games. Proceedings of the AAAI Conference on Artificial Intelligence, 39(13), 13502-13509. https://doi.org/10.1609/aaai.v39i13.33474