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} \langle x, Ay \rangle = \max_{y \in Q_2} \min_{x \in Q_1} \langle x, Ay \rangle.
\]
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 us to apply techniques from variational analysis to obtain additional insight into the condition measure \( \kappa(A) \).
This is based on joint work with A. Gilpin, T. Sandholm, B. Mordukhovich, and V. Roshchina.
\[
\min_{x \in Q_1} \max_{y \in Q_2} \langle x, Ay \rangle = \max_{y \in Q_2} \min_{x \in Q_1} \langle x, Ay \rangle.
\]
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 us to apply techniques from variational analysis to obtain additional insight into the condition measure \( \kappa(A) \).
This is based on joint work with A. Gilpin, T. Sandholm, B. Mordukhovich, and V. Roshchina.
No video available