Andrew Gilpin, Javier Pena, Tuomas Sandholm
We propose an iterated version of Nesterov's first-order smoothing method for the two-person zero-sum game equilibrium problem. This formulation applies to matrix games as well as sequential games. Our new algorithmic scheme computes an ε-equilibrium to this min-max problem in O(K(A) ln (1/ε)) first-order iterations, where K(A) is a certain condition measure of the matrix A.This improves upon the previous first-order methods which required O(1/ε) iterations, and it matches the iteration complexity bound of interior-point methods in terms of the algorithm's dependence on ε.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 a variant of Nesterov's algorithm with an outer loop that lowers the target ε 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).
Subjects: 7.1 Multi-Agent Systems; 8. Enabling Technologies
Submitted: Apr 15, 2008