{"id":"arxiv/2601.02347","url":"https://arxiv.org/abs/2601.02347","tags":["math.OC","cs.DS","cs.GT"],"score":0,"title":"Solving Matrix Games with Near-Optimal Matvec Complexity","domain":"math.OC","source":"arxiv","authors":["Ishani Karmarkar","Liam O'Carroll","Aaron Sidford"],"reviews":0,"subject":"math.OC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-01-05","reactions":{}}