Solving Matrix Games with Near-Optimal Matvec Complexity
For researchers in game theory and optimization, this work provides nearly optimal algorithms for solving fundamental classes of matrix games, significantly reducing computational complexity.
The paper presents algorithms for computing ε-approximate Nash equilibria in two-player bilinear games with bounded payoff matrices, achieving matrix-vector multiply complexities of Õ(ε^{-2/3}) for ℓ1-ℓ1 and ℓ2-ℓ1 games, improving on prior Õ(ε^{-8/9}) and Õ(ε^{-7/9}) complexities, and matching lower bounds up to polylog factors.
We study the problem of computing an $ε$-approximate Nash equilibrium of a two-player, bilinear game with a bounded payoff matrix $A \in \mathbb{R}^{m \times n}$, when the players' strategies are constrained to lie in simple sets. We provide algorithms which solve this problem in $\tilde{O}(ε^{-2/3})$ matrix-vector multiplies (matvecs) in two well-studied cases: $\ell_1$-$\ell_1$ (or zero-sum) games, where the players' strategies are both in the probability simplex, and $\ell_2$-$\ell_1$ games (encompassing hard-margin SVMs), where the players' strategies are in the unit Euclidean ball and probability simplex respectively. These results improve upon the previous state-of-the-art complexities of $\tilde{O}(ε^{-8/9})$ for $\ell_1$-$\ell_1$ and $\tilde{O}(ε^{-7/9})$ for $\ell_2$-$\ell_1$ due to [KOS '25]. In both settings our results are nearly-optimal as they match lower bounds of [KS '25] up to polylogarithmic factors.