Near-optimal no-regret algorithms for zero-sum games

DOI10.1016/j.geb.2014.01.003zbMath1318.91008OpenAlexW2049337234MaRDI QIDQ2516247

Alan Deckelbaum, Constantinos Daskalakis, Anthony Kim

Publication date: 12 August 2015

Published in: Games and Economic Behavior (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.geb.2014.01.003

zbMATH Keywords

learningzero-sum gamesrepeated gamesno-regret dynamics

Mathematics Subject Classification ID

2-person games (91A05) Rationality and learning in game theory (91A26) Multistage and repeated games (91A20)

Related Items

Faster algorithms for extensive-form game solving via improved smoothing functions, Introduction to the special issue -- Algorithmic game theory -- STOC/FOCS/SODA 2011

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Smooth minimization of non-smooth functions
• Completely uncoupled dynamics and Nash equilibria
• A new polynomial-time algorithm for linear programming
• The weighted majority algorithm
• On the rate of convergence of continuous-time fictitious play
• Adaptive game playing using multiplicative weights
• The equivalence of linear programs and zero-sum games
• Non-cooperative games
• An iterative method of solving a game
• On the Rate of Convergence of Fictitious Play
• Smoothing Techniques for Computing Nash Equilibria of Sequential Games
• Asymptotic calibration
• A Simple Adaptive Procedure Leading to Correlated Equilibrium
• Excessive Gap Technique in Nonsmooth Convex Minimization
• Prediction, Learning, and Games