Solving Zero-Sum Games with Fewer Matrix-Vector Products

Ishani Karmarkar, Liam O'Carroll, Aaron Sidford

In this paper we consider the problem of computing an $\epsilon$-approximate Nash Equilibrium of a zero-sum game in a payoff matrix $A\in {\mathbb{R}}^{m\times n}$ with $O(1)$-bounded ent…