Nash Equilibrium Computation

Follow this topic Ask about this topic

Momentum

12 papers in the last four weeks, against 2 the four weeks before. 0.1% of all new papers.

Jul 13Week of Sep 28

Latest papers 46

All topics

When and Why is Optimistic Multiplicative Weights Slow? The Geometry of Energy Dissipation
May 13, 2026John Lazarsfeld, Anas Barakat, Georgios Piliouras +2Nash Equilibrium Last-Iterate Convergence
SUTD · Google DeepMind · NUS CQT +2
Offline Two-Player Zero-Sum Markov Games with KL Regularization
May 13, 2026Claire Chen, Yuheng Zhang, Xinyu Liu +3Nash Equilibrium Reinforcement Learning
1California Institute of Technology. · University of Illinois Urbana-Champaign. · University of Virginia. +2
DelAC: A Multi-agent Reinforcement Learning of Team-Symmetric Stochastic Games
May 11, 2026Duan-Shin Lee, Yu-Hsiu HungNash Equilibrium Game Theory
Department of Computer Science, National Tsing Hua University · MediaTek Inc.
Equilibrium Residuals Expose Three Regimes of Matrix-Game Strategic Reasoning in Language Models
May 11, 2026Wenhua Nie, Binhan Luo, Zijie Meng +2Nash Equilibrium LLM Evaluation
National Taiwan University
Towards Model-Free Learning in Dynamic Population Games: An Application to Karma Economies
May 11, 2026Matteo Cederle, Saverio Bolognani, Gian Antonio SustoNash Equilibrium Game Theory
Department of Information Engineering University of Padova · Automatic Control Laboratory ETH Zurich
Pessimism-Free Offline Learning in General-Sum Games via KL Regularization
Apr 30, 2026Claire Chen, Yuheng ZhangNash Equilibrium Reinforcement Learning
The Division of Physics, Mathematics and Astronomy California Institute of Technology · Department of Computer Science University of Illinois Urbana-Champaign
What Suppresses Nash Equilibrium Play in Large Language Models? Mechanistic Evidence and Causal Control
Apr 29, 2026Paraskevas V. Lekeas, Giorgos StamatopoulosNash Equilibrium Game Theory
DreamWorks Animation, Glendale, USA · Department of Economics, University of Crete2026 Rethymno, Crete, Greece
Asymmetric-Information Resource Allocation Games: An LP Approach to Purposeful Deception
Apr 27, 2026Longxu Pan, Yue Guan, Daigo Shishika +1Imperfect-Information Games Game Theory
School of Aerospace Engineering, Georgia Institute of Technology, Atlanta, GA, USA · College of Engineering and Computing, George Mason University, Fairfax, VA, USA
The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
Apr 17, 2026Côme Fiegel, Pierre Ménard, Tadashi Kozuno +2Nash Equilibrium Last-Iterate Convergence
ENSAE Paris - CREST, Palaiseau, France · Inria - FairPlay · ENS Lyon, Lyon, France +3
Local exponential stability of mean-field Langevin descent-ascent and associated particle system
Feb 2, 2026Geuntaek Seo, Minseop Shin, Pierre Monmarché +1Nash Equilibrium Lyapunov Stability
Quadratic Programming Approach for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games
Sep 30, 2025Sam GanzfriedNash Equilibrium Imperfect-Information Games
Ganzfried Research
Distributionally Robust Markov Games with Average Reward
Aug 5, 2025Zachary Roch, Yue WangNash Equilibrium Multi-Agent System Optimization
Department of Electrical and Computer Engineering, University of Central Florida, Orlando, Florida, USA. · Department of Computer Science, University of Central Florida, Orlando, Florida, USA.
Nonlinear Equilibrium Transitions in a Potential Game Model for Federated Learning
Nov 18, 2024Kang Liu, Ziqi Wang, Enrique ZuazuaNash Equilibrium Game Theory
Institut de Mathématiques de Bourgogne, Université Bourgogne Europe, CNRS, Dijon, 21000, France · Chair for Dynamics, Control, Machine Learning and Numerics – Alexander von Humboldt Professorship, Department of Mathematics, Friedrich-Alexander-Universität Erlangen-Nürnberg, Cauerstrasse 11, Erlangen, 91058, Germany · Chair of Computational Mathematics, Fundación Deusto, Avenida de las Universidades, 24, Bilbao, 48007, Basque Country, Spain +1
Decentralized Best-Response-Based Learning in Two-Player Zero-Sum Stochastic Games: A Finite-Sample Analysis
Sep 2, 2024Zaiwei Chen, Kaiqing Zhang, Eric Mazumdar +2Nash Equilibrium Game Theory
IE, Purdue University. · ECE, University of Maryland, College Park. · CMS, Caltech. +1
Independent Learning of Nash Equilibria in Partially Observable Markov Potential Games with Decoupled Dynamics
Date pendingPhilip Jordan, Maryam KamgarpourNash Equilibrium Reinforcement Learning
SYCAMORE, EPFL
Stability and Convergence of Optimistic Exponential Weights with Asymmetric Step Sizes in Bimatrix Games
Date pendingHédi Hadiji, Sarah SachsNash Equilibrium Last-Iterate Convergence
Laboratoire des Signaux et Systèmes, CentraleSupélec, Paris, France · School of Mathematics, University of Bristol, Bristol, United Kingdom

May 13, 2026, cs.GTJ/K move · Enter open · S save

When and Why is Optimistic Multiplicative Weights Slow? The Geometry of Energy Dissipation

John Lazarsfeld, Anas Barakat, Georgios Piliouras, Antonios Varvitsiotis+1

SUTD · Google DeepMind · NUS CQT+2

Nash Equilibrium Last-Iterate Convergence Optimization Convergence Analysis Game Theory Zero-Sum Games Convergence Analysis+1

Open paper AskPDF arXiv

This paper studies the convergence of the Optimistic Multiplicative Weights Update algorithm (OMWU) in two player zero-sum games. Recent works have identified instances on which the last-iterate of OMWU can converge arbitrarily slowly, but understanding when and why this slow convergence occurs has remained open. In this work, we develop a new analysis framework that gives sharp, quantitative explanations for this behavior. Our analysis is based on viewing the algorithm's dual iterates as an optimistic skew-gradient descent with respect to an energy function. We prove over the dual iterates that energy is dissipative, and by establishing tight bounds on the magnitude of dissipation, our analysis quantifies the geometric bottlenecks that arise when the corresponding primal iterates are close to the simplex boundary. This further translates into a new linear last-iterate convergence rate in KL divergence on games with a unique and interior Nash equilibrium. Compared to prior work, this new rate contains a much sharper dependence on game-specific constants, and we prove this dependence is optimal. Moreover, these geometric insights further translate into new separations on uniform convergence rates for OMWU. On the one hand, we prove constant lower bounds on the uniform best-iterate convergence rate in KL divergence and total variation distance from Nash. On the other hand, we establish for the

2\times 2

setting a new

{\widetilde O}(T^{-1/2})

best-iterate rate in duality gap, improving substantially over prior work. Together, this shows in general that uniform convergence rate guarantees do not transfer across different measures of distance to Nash.

Momentum

Related topics

Latest papers 46