Sitemap
A list of all the posts and pages found on the site. For you robots out there is an XML version available for digesting as well.
Pages
Posts
portfolio
publications
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
Colonel Blotto with Battlefield Games
Under Review
talks
Introduction to Auctions and Pacing Equilibria in Auction Markets
Published:
This tutorial covers the fundamentals of auction theory and demonstrates their use in internet advertising, culminating in an introduction to pacing equilibria in auction markets.
teaching
Analysis of Algorithms (CSOR 4231)
Masters course, Columbia University, IEOR Department, 2024
This course covers fundemental algorithm design techniques, including greedy algorithms, divide-and-conquer, dynamic programming, network flows, and NP-completeness. I helped in assisting students during office hours, and grading assignments and exams.
Optimization Models and Methods (IEOR 4004)
Masters course, Columbia University, IEOR Department, 2025
The course covers theoretical and programming aspects of optimization models and methods. I helped in assisting students during office hours, grading assignments and exams, and project supervision.