First-order algorithm with $O(ln(1/\epsilon))$ convergence for $\epsilon$-equilibrium in two-person zero-sum games

Andrew Gilpin (gilpincs.cmu.edu)
Javier Pena (jfpandrew.cmu.edu)
Tuomas Sandholm (sandholmcs.cmu.edu)

Abstract: 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}.$$ This formulation applies to matrix games as well as sequential games. Our new algorithmic scheme computes an $\epsilon$-equilibrium to this min-max problem in $\Oh(\kappa(A) \ln(1/\epsilon))$ first-order iterations, where $\kappa(A)$ is a certain condition measure of the matrix $A$. This improves upon the previous first-order methods which required $\Oh(1/\epsilon)$ iterations, and it matches the iteration complexity bound of interior-point methods in terms of the algorithm's dependence on $\epsilon$. Unlike the 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. Our scheme supplements Nesterov's algorithm with an outer loop that lowers the target $\epsilon$ between iterations (this target affects the amount of smoothing in the inner loop). We find it surprising that such a simple modification yields an exponential speed improvement. Finally, computational experiments both in matrix games and sequential games show that a significant speed improvement is obtained in practice as well, and the relative speed improvement increases with the desired accuracy (as suggested by the complexity bounds).

Keywords: games, equilibrium, smoothing

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Other Topics (Game Theory )

Citation: 23rd National Conference on Artificial Intelligence (AAAI'08)

Download: [PDF]

Entry Submitted: 04/16/2008
Entry Accepted: 05/02/2008
Entry Last Modified: 05/03/2008

Modify/Update this entry