Faster algorithms for extensive-form game solving via improved smoothing functions

DOI10.1007/S10107-018-1336-7zbMATH Open1433.91014OpenAlexW2895703110MaRDI QIDQ2288198FDOQ2288198

Christian Kroer, Tuomas Sandholm, Kevin Waugh, Fatma Kılınç-Karzan

Publication date: 17 January 2020

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

Full work available at URL: https://doi.org/10.1007/s10107-018-1336-7

zbMATH Keywords

Nash equilibriumzero-sum gamefirst-order methodextensive-form gamebilinear saddle-point problem

Mathematics Subject Classification ID

Convex programming (90C25) 2-person games (91A05) Games in extensive form (91A18) Algorithmic game theory and complexity (91A68)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Lossless abstraction of imperfect information games
• Smooth minimization of non-smooth functions
• Primal-dual subgradient methods for convex problems
• Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
• Excessive Gap Technique in Nonsmooth Convex Minimization
• The Complexity of Computing a Nash Equilibrium
• Solving variational inequalities with Stochastic Mirror-Prox algorithm
• Efficient computation of equilibria for extensive two-person games
• An Exact Double-Oracle Algorithm for Zero-Sum Extensive-Form Games with Imperfect Information
• First-order algorithm with \({\mathcal{O}(\ln(1/\epsilon))}\) convergence for \({\epsilon}\)-equilibrium in two-person zero-sum games
• Efficient computation of behavior strategies
• Smoothing Techniques for Computing Nash Equilibria of Sequential Games
• DeepStack: Expert-level artificial intelligence in heads-up no-limit poker
• Faster algorithms for extensive-form game solving via improved smoothing functions
• Near-optimal no-regret algorithms for zero-sum games

Cited In (2)

• HSVI can solve zero-sum partially observable stochastic games
• Faster algorithms for extensive-form game solving via improved smoothing functions

Uses Software

• GameShrink
• DeepStack

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Efficient computation of equilibria for extensive two-person games 👍 👎
• Smoothing Techniques for Computing Nash Equilibria of Sequential Games 👍 👎
• Faster algorithms for mean-payoff games 👍 👎
• Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes 👍 👎
• Faster algorithm for mean-payoff games 👍 👎
• Faster Algorithms for Finitary Games 👍 👎
• Exact algorithms for solving stochastic games 👍 👎

This page was built for publication: Faster algorithms for extensive-form game solving via improved smoothing functions

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