The Oracle Complexity of Simplex-based Matrix Games

Guy Kornowski, Ohad Shamir

We study the problem of solving matrix games of the form ${\min }_{\mathbf{p}\in \Delta }{\max }_{\mathbf{w}\in \mathcal{W}}{\mathbf{p}}^{\top }A\mathbf{w}$, where $A$ is a matrix and $\Delta$ is the pr…