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

DOI10.1007/s10107-010-0430-2zbMath1243.91004OpenAlexW2072651894MaRDI QIDQ431003

Andrew Gilpin, Tuomas W. Sandholm, Javier F. Peña

Publication date: 26 June 2012

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-010-0430-2

Mathematics Subject Classification ID

Minimax problems in mathematical programming (90C47) 2-person games (91A05) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33) Methods of reduced gradient type (90C52)

Related Items (15)

A fast dual proximal-gradient method for separable convex optimization with linear coupled constraints ⋮ New computational guarantees for solving convex optimization problems with first order methods, via a function growth condition measure ⋮ Subgradient methods for huge-scale optimization problems ⋮ Faster first-order primal-dual methods for linear programming using restarts and sharpness ⋮ Infeasibility Detection with Primal-Dual Hybrid Gradient for Large-Scale Linear Programming ⋮ A simple nearly optimal restart scheme for speeding up first-order methods ⋮ Forward-partial inverse-forward splitting for solving monotone inclusions ⋮ RSG: Beating Subgradient Method without Smoothness and Strong Convexity ⋮ A deterministic rescaled perceptron algorithm ⋮ Faster algorithms for extensive-form game solving via improved smoothing functions ⋮ Sharpness, Restart, and Acceleration ⋮ Faster subgradient methods for functions with Hölderian growth ⋮ Towards a deeper geometric, analytic and algorithmic understanding of margins ⋮ Algorithm for computing approximate Nash equilibrium in continuous games with application to continuous blotto ⋮ ``Efficient” Subgradient Methods for General Convex Optimization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Smooth minimization of non-smooth functions
• The complexity of two-person zero-sum games in extensive form
• Potential function methods for approximately solving linear programming problems: theory and practice.
• Efficient computation of behavior strategies
• Applying Metric Regularity to Compute a Condition Measure of a Smoothing Algorithm for Matrix Games
• Smoothing Techniques for Computing Nash Equilibria of Sequential Games
• On convergence rates of subgradient optimization methods
• An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm
• Excessive Gap Technique in Nonsmooth Convex Minimization

This page was built for publication: First-order algorithm with \({\mathcal{O}(\ln(1/\epsilon))}\) convergence for \({\epsilon}\)-equilibrium in two-person zero-sum games