Abstract

A first-order algorithm with $O(\log(1/\epsilon))$ convergence for computing $\epsilon$-equilibrium of two-person zero-sum games

Javier Pena
Carnegie-Mellon University

We propose an iterated version of Nesterov's first-order smoothing
method for the two-person zero-sum game equilibrium problem
\[
\min_{x\in Q_1} \max_{y\in Q_2} \ip{x}{Ay} = \max_{y\in Q_2} \min_{x\in Q_1} \ip{x}{Ay}.
\]
Our algorithm computes an $\epsilon$-equilibrium to this min-max problem in $O(\kappa(A) \ln(1/\epsilon))$ first-order iterations, where $\kappa(A)$ is a certain condition measure of the matrix $A$. This improves upon previous first-order methods which required $\O(1/\epsilon)$ iterations, and matches the iteration complexity bound of interior-point methods in terms of the algorithm's dependence on $\epsilon$. Unlike interior-point methods that are inapplicable to large games due to their memory requirements, our algorithm retains the small memory requirements of prior first-order methods. The condition measure $\kappa(A)$ can be interpreted as the modulus of metric regularity of a canonical set-valued mapping associated to $A$. This allows to apply techniques from variational analysis to obtain additional insight into the condition measure $\kappa(A)$.



This is based on joint with work A. Gilpin, T. Sandholm, B. Mordukhovich, and V. Roshchina.