  


Firstorder algorithm with $O(ln(1/\epsilon))$ convergence for $\epsilon$equilibrium in twoperson zerosum games
Andrew Gilpin (gilpincs.cmu.edu) Abstract: We propose an iterated version of Nesterov's firstorder smoothing method for the twoperson zerosum 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 minmax problem in $\Oh(\kappa(A) \ln(1/\epsilon))$ firstorder iterations, where $\kappa(A)$ is a certain condition measure of the matrix $A$. This improves upon the previous firstorder methods which required $\Oh(1/\epsilon)$ iterations, and it matches the iteration complexity bound of interiorpoint methods in terms of the algorithm's dependence on $\epsilon$. Unlike the interiorpoint methods that are inapplicable to large games due to their memory requirements, our algorithm retains the small memory requirements of prior firstorder 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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  