{"ID":2822693,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2601.02347","arxiv_id":"2601.02347","title":"Solving Matrix Games with Near-Optimal Matvec Complexity","abstract":"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.","short_abstract":"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 mul...","url_abs":"https://arxiv.org/abs/2601.02347","url_pdf":"https://arxiv.org/pdf/2601.02347v2","authors":"[\"Ishani Karmarkar\",\"Liam O'Carroll\",\"Aaron Sidford\"]","published":"2026-01-05T18:44:27Z","proceeding":"math.OC","tasks":"[\"math.OC\",\"cs.DS\",\"cs.GT\"]","methods":"[]","has_code":false}