Smoothing techniques for computing Nash equilibria of sequential games

DOI10.1287/MOOR.1100.0452MaRDI QIDQ3169104zbMATH OpenOpenAlexFDO

Authors Samid Hoda, Andrew Gilpin, Tuomas Sandholm, Javier Peña

Publication date 27 April 2011

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/moor.1100.0452

zbMATH Keywords

Nash equilibriumsequential gamessmoothing techniques

Mathematics Subject Classification ID

Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33) 2-person games (91A05) Multistage and repeated games (91A20)

Recommendations

• First-order algorithm with \({\mathcal{O}(\ln(1/\epsilon))}\) convergence for \({\epsilon}\)-equilibrium in two-person zero-sum games
• Simple search methods for finding a Nash equilibrium
• Equilibrium computation for two-player games in strategic and extensive form
• Computing Nash equilibria by iterated polymatrix approximation
• Faster algorithms for extensive-form game solving via improved smoothing functions

Cited in

(15)

• Approximating maxmin strategies in imperfect recall games using A-loss recall property
• Limited lookahead in imperfect-information games
• Accelerated gradient sliding for structured convex optimization
• Faster algorithms for extensive-form game solving via improved smoothing functions
• Automated construction of bounded-loss imperfect-recall abstractions in extensive-form games
• Near-optimal no-regret algorithms for zero-sum games
• Smoothness for Simultaneous Composition of Mechanisms with Admission
• First-order algorithm with \({\mathcal{O}(\ln(1/\epsilon))}\) convergence for \({\epsilon}\)-equilibrium in two-person zero-sum games
• Game theory approach to H/sub ∞/-optimal discrete-time fixed-point and fixed-lag smoothing
• Portfolio selection with multiple spectral risk constraints
• Accelerated smoothing hard thresholding algorithms for \(\ell_0\) regularized nonsmooth convex regression problem
• Smoothing accelerated proximal gradient method with fast convergence rate for nonsmooth convex optimization beyond differentiability
• Fast convergence of optimistic gradient ascent in network zero-sum extensive form games
• HSVI can solve zero-sum partially observable stochastic games
• A distributed iterative Tikhonov method for networked monotone stochastic and hierarchical aggregative games

Describes a project that uses

Uses Software

• GameShrink

This page was built for publication: Smoothing techniques for computing Nash equilibria of sequential games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3169104)