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

May 13, 2026cs.GT

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

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.

John Lazarsfeld, Anas Barakat, Georgios Piliouras +2

SUTD · Google DeepMind · NUS CQT +2

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

May 13, 2026cs.LG

Offline Two-Player Zero-Sum Markov Games with KL Regularization

We study the problem of learning Nash equilibria in offline two-player zero-sum Markov games. While existing approaches often rely on explicit pessimism to address distribution shift, we show that KL regularization alone suffices to stabilize learning and guarantee convergence. We first introduce Regularized Offline Sequential Equilibrium (ROSE), a theoretical framework that achieves a fast

\widetilde{\mathcal{O}}(1/n)

convergence rate under \textit{unilateral concentrability}, improving over the standard

\widetilde{\mathcal{O}}(1/\sqrt{n})

rates in unregularized settings. We then propose Sequential Offline Self-play Mirror Descent (SOS-MD), a practical model-free algorithm based on least-squares value estimation and iterative self-play updates. We prove that the last iterate of SOS-MD attains the same

\widetilde{\mathcal{O}}(1/n)

statistical rate up to a vanishing optimization error of order

\widetilde{\mathcal{O}}(1/\sqrt{T})

in the number of self-play iterations

T

.

Claire Chen, Yuheng Zhang, Xinyu Liu +3

1California Institute of Technology. · University of Illinois Urbana-Champaign. · University of Virginia. +2

Nash Equilibrium Reinforcement Learning Self-Play RL KL-Regularized RL Game Theory Zero-Sum Games+3

May 11, 2026cs.MA

DelAC: A Multi-agent Reinforcement Learning of Team-Symmetric Stochastic Games

In this paper we study team-symmetric games with

m\ge 2

teams. Players within a team have symmetric identity and have a common payoff function. We show that team-symmetric games always have a team-symmetric Nash equilibrium. We develop and solve a linear complementarity problem of team-symmetric Nash equilibria. We propose an actor-critic based multi-agent reinforcement learning algorithm for team-symmetric games. Through simulations, we show that this multi-agent reinforcement learning algorithm performs much better than many existing algorithms.

Duan-Shin Lee, Yu-Hsiu Hung

Department of Computer Science, National Tsing Hua University · MediaTek Inc.

Nash Equilibrium Game Theory Actor-Critic Methods Multi-Agent Reinforcement Learning Nash Equilibrium Computation

May 11, 2026cs.LG

Equilibrium Residuals Expose Three Regimes of Matrix-Game Strategic Reasoning in Language Models

Large language models can score well on named game-theory benchmarks while failing on the same strategic computation once semantic cues are removed. We show this gap with procedurally generated zero-sum matrix games: a model that recognizes familiar games drops to 34%, 18%, and 2% success on anonymous

2{\times}2

,

3{\times}3

, and

5{\times}5

payoff matrices. The benchmark separates semantic recall, learned approximate Nash computation, and an output-interface bottleneck that limits scale. Training only on

2{\times}2

and

3{\times}3

games, supervised fine-tuning raises unseen

5{\times}5

--

7{\times}7

success from 2% to 61%, while exploitability-reward training averages 37% with high seed variance. We prove that the exploitability residual is

2

-Lipschitz in payoff perturbations, unlike discontinuous vertex-returning LP equilibrium selectors, explaining why residual training can transfer under payoff shifts even when formatting instability limits mean performance. A dominated-action padding experiment provides causal evidence: trained models solve

3{\times}3

games embedded in much larger matrices, while random-padded controls fail and dense

12{\times}12

games remain near failure. Procedural evaluation is therefore necessary for measuring strategic reasoning, and residual rewards expose a real but format-limited route to approximate equilibrium computation.

Wenhua Nie, Binhan Luo, Zijie Meng +2

National Taiwan University

Nash Equilibrium LLM Evaluation Game Theory RL for Language Model Reasoning Zero-Sum Games Nash Equilibrium Computation

May 11, 2026cs.GT

Towards Model-Free Learning in Dynamic Population Games: An Application to Karma Economies

Dynamic Population Games (DPGs) provide a tractable framework for modeling strategic interactions in large populations of self-interested agents, and have been successfully applied to the design of Karma economies, a class of fair non-monetary resource allocation mechanisms. Despite their appealing theoretical properties, existing computational tools for DPGs assume full knowledge of the game model and operate in a centralized fashion, limiting their applicability in realistic settings where agents have access only to their own private experience. This paper takes a step towards addressing this gap by studying model-free equilibrium learning in Karma DPGs. First, we analyze the setting in which a novel agent joins a Karma DPG already at its Stationary Nash Equilibrium (SNE) and learns a policy via Deep Q-Networks (DQN) without knowledge of the game model. Leveraging recent convergence results for DQN, we establish a suboptimality bound consisting of a DQN approximation error of order

O(1/\sqrt{N_s})

and a mean field perturbation error of order

O(1/N)

, where

N_s

is the replay buffer size and

N

is the population size. Second, we consider the challenging problem of learning the SNE from scratch. We show empirically that combining deep RL with fictitious play and smoothed policy iteration allows agents to converge, in a model-free fashion, to a configuration close to the centrally computed SNE. Together, these contributions support the vision of Karma economies as practical tools for fair resource allocation.

Matteo Cederle, Saverio Bolognani, Gian Antonio Susto

Department of Information Engineering University of Padova · Automatic Control Laboratory ETH Zurich

Nash Equilibrium Game Theory Model-Free RL Nash Equilibrium Computation

Apr 30, 2026cs.LG

Pessimism-Free Offline Learning in General-Sum Games via KL Regularization

Offline multi-agent reinforcement learning in general-sum settings is challenged by the distribution shift between logged datasets and target equilibrium policies. While standard methods rely on manual pessimistic penalties, we demonstrate that KL regularization suffices to stabilize learning and achieve equilibrium recovery. We propose General-sum Anchored Nash Equilibrium (GANE), which recovers regularized Nash equilibria at an accelerated statistical rate of

\widetilde{O}(1/n)

. For computational tractability, we develop General-sum Anchored Mirror Descent (GAMD), an iterative algorithm converging to a Coarse Correlated Equilibrium at the standard rate of

\widetilde{O}(1/\sqrt{n}+1/T)

. These results establish KL regularization as a standalone mechanism for pessimism-free offline learning that achieves equivalent or accelerated rates in multi-player general-sum games.

Claire Chen, Yuheng Zhang

The Division of Physics, Mathematics and Astronomy California Institute of Technology · Department of Computer Science University of Illinois Urbana-Champaign

Nash Equilibrium Reinforcement Learning KL-Regularized RL Game Theory Offline RL Multi-Agent Reinforcement Learning+2

Apr 29, 2026cs.GT

What Suppresses Nash Equilibrium Play in Large Language Models? Mechanistic Evidence and Causal Control

LLM agents are known to deviate from Nash equilibria in strategic interactions, but nobody has looked inside the model to understand why, or asked whether the deviation can be reversed. We do both. Working with four open-source models (Llama-3 and Qwen2.5, 8B to 72B parameters) playing four canonical two-player games, we establish the behavioral picture through self-play and cross-play experiments, then open up the 32-layer Llama-3-8B model and examine what actually happens during a strategic decision. The mechanistic findings are clear. Opponent history is encoded with near-perfect fidelity at the first layer (96% probe accuracy) and consumed progressively, while Nash action encoding is weak throughout, never exceeding 56%. There is no dedicated Nash module. Instead, the model privately favors the Nash action through most of its forward pass, but a prosocial override rooted in pretraining on human text concentrated in the final layers reverses this, reaching 84% probability of cooperation at layer 30. Injecting a learned Nash direction into the residual stream shifts behavior bidirectionally and causally, confirmed through concept clamping. The behavioral experiments surface six scale- and architecture-dependent findings, the most notable being that chain-of-thought reasoning worsens Nash play in small models but achieves near-perfect Nash play above 70B parameters. The cross-play experiments reveal three phenomena invisible in self-play: a small model can unravel any partner's cooperation by defecting early; two large models reinforce each other's cooperative instincts indefinitely; and who moves first determines which Nash equilibrium the system reaches. LLMs do not lack Nash-playing competence. They compute it, then suppress it.

Paraskevas V. Lekeas, Giorgos Stamatopoulos

DreamWorks Animation, Glendale, USA · Department of Economics, University of Crete2026 Rethymno, Crete, Greece

Nash Equilibrium Game Theory LLM Interpretability Causal Interventions in Language Models Multi-Agent LLMs Nash Equilibrium Computation

Apr 27, 2026cs.GT

Asymmetric-Information Resource Allocation Games: An LP Approach to Purposeful Deception

In this work, we introduce the Deceptive Resource Allocation Game (DRAG), which studies purposeful deception within a Bayesian game framework. In DRAG, a Defender allocates resources across the true asset and several decoys to influence an Attacker's beliefs and actions, with the goal of diverting the Attacker away from the true asset. We seek to characterize purposeful deception, whereby the Defender deceives only when doing so improves its performance. To this end, we solve for the Perfect Bayesian Nash Equilibrium (PBNE) of the corresponding game. We show that, despite the coupled belief-policy interdependence, the problem admits an efficient, non-iterative linear programming formulation. Numerical results demonstrate that the resulting policies naturally balance effective allocation and belief manipulation, giving rise to purposeful and emergent deceptive behaviors.

Longxu Pan, Yue Guan, Daigo Shishika +1

School of Aerospace Engineering, Georgia Institute of Technology, Atlanta, GA, USA · College of Engineering and Computing, George Mason University, Fairfax, VA, USA

Imperfect-Information Games Game Theory Linear Programming Nash Equilibrium Computation

Apr 17, 2026cs.LG

The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback

We study the problem of learning in zero-sum matrix games with repeated play and bandit feedback. Specifically, we focus on developing uncoupled algorithms that guarantee, without communication between players, the convergence of the last-iterate to a Nash equilibrium. Although the non-bandit case has been studied extensively, this setting has only been explored recently, with a bound of

\mathcal{O}(T^{-1/8})

on the exploitability gap. We show that, for uncoupled algorithms, guaranteeing convergence of the policy profiles to a Nash equilibrium is detrimental to the performance, with the best attainable rate being

Ω(T^{-1/4})

in contrast to the usual

Ω(T^{-1/2})

rate for convergence of the average iterates. We then propose two algorithms that achieve this optimal rate up to constant and logarithmic factors. The first algorithm leverages a straightforward trade-off between exploration and exploitation, while the second employs a regularization technique based on a two-step mirror descent approach.

Côme Fiegel, Pierre Ménard, Tadashi Kozuno +2

ENSAE Paris - CREST, Palaiseau, France · Inria - FairPlay · ENS Lyon, Lyon, France +3

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

Feb 2, 2026cs.LG

Local exponential stability of mean-field Langevin descent-ascent and associated particle system

We study the mean-field Langevin descent-ascent (MFL-DA), a coupled optimization dynamics on the space of probability measures for entropically regularized two-player zero-sum games, together with its associated interacting particle system. For general nonconvex-nonconcave payoffs, Wang and Chizat (COLT 2024) asked whether the original single-timescale MFL-DA converges to the mixed Nash equilibrium and, if so, at what rate. We prove a local affirmative answer in Wasserstein space: if the initial datum is sufficiently close to the mixed Nash equilibrium, then the mean-field dynamics converges to it exponentially fast at a quantitative rate. We further show that the finite-

N

particle system inherits this stability up to times exponential in

N

, with an

N

-independent exponential rate modulo a finite-particle error floor. Combined with the recent counterexample of Mourrat and Pillaud-Vivien for MFL-DA, which shows that global convergence cannot hold in general, our theorem completes the positive local counterpart of the Wang-Chizat question: the mixed Nash equilibrium has a robust basin of attraction, stable under both the mean-field flow and its finite-particle approximation.

Geuntaek Seo, Minseop Shin, Pierre Monmarché +1

Nash Equilibrium Lyapunov Stability Game Theory Wasserstein Gradient Flows Zero-Sum Games Mean-Field Theory+1

Sep 30, 2025cs.GT

Quadratic Programming Approach for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games

There has been significant recent progress in algorithms for approximation of Nash equilibrium in large two-player zero-sum imperfect-information games and exact computation of Nash equilibrium in multiplayer strategic-form games. While counterfactual regret minimization and fictitious play are scalable to large games and have convergence guarantees in two-player zero-sum games, they do not guarantee convergence to Nash equilibrium in multiplayer games. We present an approach for exact computation of Nash equilibrium in multiplayer imperfect-information games that solves a quadratically-constrained program based on a nonlinear complementarity problem formulation from the sequence-form game representation. This approach capitalizes on recent advances for solving nonconvex quadratic programs. Our algorithm is able to quickly solve three-player Kuhn poker after removal of dominated actions. Of the available algorithms in the Gambit software suite, only the logit quantal response approach is successfully able to solve the game; however, the approach takes longer than our algorithm and also involves a degree of approximation. Our formulation also leads to a new approach for computing Nash equilibrium in multiplayer strategic-form games which we demonstrate to outperform a previous quadratically-constrained program formulation.

Sam Ganzfried

Ganzfried Research

Nash Equilibrium Imperfect-Information Games Game Theory Quadratic Programming Nash Equilibrium Computation

Aug 5, 2025cs.MA

Distributionally Robust Markov Games with Average Reward

We propose and study distributionally robust Markov games (DR-MGs) with the average-reward criterion as a crucial framework for multi-agent decision-making under model mismatches and over extended horizons. Under a standard irreducible assumption, we first derive a correspondence between the optimal policies and the solutions of the robust Bellman equation, based on which we further show the existence of a stationary Nash Equilibrium (NE) of the game. We further study DR-MGs under a more general weakly communicating setting. We construct a set-valued map based on the constant-gain optimal robust Bellman operator and show that its value is a subset of the best-response policies. We further prove that this map admits a fixed point, which implies the existence of NE. We then design two algorithms, Robust Nash-Iteration and robust TD Descent, with provably convergent guarantees. Finally, we show that the NE under average-reward can be approximated by the ones for the discounted DR-MGs as the discount factor approaches one. Our studies provide a comprehensive theoretical and algorithmic foundation for decision-making in complex, uncertain, and long-running multi-player environments.

Zachary Roch, Yue Wang

Department of Electrical and Computer Engineering, University of Central Florida, Orlando, Florida, USA. · Department of Computer Science, University of Central Florida, Orlando, Florida, USA.

Nash Equilibrium Multi-Agent System Optimization Reinforcement Learning Average-Reward RL Game Theory Distributionally Robust Optimization+4

Nov 18, 2024cs.LG

Nonlinear Equilibrium Transitions in a Potential Game Model for Federated Learning

In federated learning (FL), a central server typically allocates training efforts to clients. However, from a market-oriented perspective, clients may independently choose their training efforts based on rational self-interest. To study this setting, we propose a potential game framework in which each client's payoff is determined by its individual effort and the rewards provided by the server. The rewards are influenced by the collective efforts of all clients and can be modulated by a reward factor. We first establish the existence of Nash equilibria (NEs) and then investigate their uniqueness in a stationary setting. We show that the NEs depend nonlinearly on the reward factor and exhibit a nonsmooth transition at a critical value, where the stationary potential loses strict curvature, leading to nonunique NEs and a jump between low-effort and high-effort branches. Furthermore, we prove the convergence of the best-response algorithm for computing NEs in our FL game. Finally, we apply the clients' rational efforts derived from the NEs to FL training with various datasets and models, thereby validating the effectiveness of the identified critical reward factor. The source code is available at https://github.com/DCN-FAU-AvH/FL-Potential-Game

Kang Liu, Ziqi Wang, Enrique Zuazua

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

Nash Equilibrium Game Theory Potential Games Federated Learning Nash Equilibrium Computation

Sep 2, 2024cs.LG

Decentralized Best-Response-Based Learning in Two-Player Zero-Sum Stochastic Games: A Finite-Sample Analysis

We present a finite-sample analysis of decentralized learning in two-player zero-sum matrix games and stochastic games, with a focus on best-response-based learning algorithms. In matrix games, the learning algorithm is payoff-based and symmetric: each player updates its policy using only its own payoff observations, incrementally moving toward an estimated smoothed best response to the opponent's latest policy. For stochastic games, we build on this matrix-game primitive to develop a learning algorithm called value iteration with smoothed best response (VI-SBR), which combines smoothed-best-response learning in induced matrix games with a decentralized, model-free approximation of minimax value iteration. We establish finite-sample guarantees in both settings. For matrix games, our results imply a sample complexity of

\mathcal{O}(ε^{-1})

for finding an

ε

-Nash distribution and, with explicit exploration,

\tilde{\mathcal{O}}(ε^{-8})

for finding an

ε

-Nash equilibrium. For stochastic games, we prove that the exploration-enhanced VI-SBR algorithm achieves a sample complexity of

\tilde{\mathcal{O}}(ε^{-8})

for finding an

ε

-Nash equilibrium. Technically, our analysis develops a coupled Lyapunov-drift framework. This framework simultaneously handles stochastic iterative algorithms with multiple interacting stochastic iterates, the non-zero-sum auxiliary games generated by independently updated value functions, and the time-inhomogeneous Markovian noise induced by time-varying policies. The resulting tools may be useful more broadly for analyzing learning algorithms with coupled stochastic iterates and nonstationary sampling processes.

Zaiwei Chen, Kaiqing Zhang, Eric Mazumdar +2

IE, Purdue University. · ECE, University of Maryland, College Park. · CMS, Caltech. +1

Nash Equilibrium Game Theory Zero-Sum Games Decentralized MARL Nash Equilibrium Computation

Date pendingcs.GT

Independent Learning of Nash Equilibria in Partially Observable Markov Potential Games with Decoupled Dynamics

We study Nash equilibrium learning in partially observable Markov games (POMGs), a multi-agent reinforcement learning framework in which agents cannot fully observe the underlying state. Prior work in this setting relies on centralization or information sharing, and suffers from sample and computational complexity that scales exponentially in the number of players. We focus on a subclass of POMGs with independent state transitions, where agents remain coupled through their rewards, and assume that the underlying fully observed Markov game is a Markov potential game. For this class, we present an independent learning algorithm in which players, observing only their own actions and observations and without communication, jointly converge to an approximate Nash equilibrium. Due to partial observability, optimal policies may in general depend on the full action-observation history. Under a filter stability assumption, we show that policies based on finite history windows provide sufficient approximation guarantees. This enables us to approximate the POMG by a surrogate Markov game that is near-potential, leading to quasi-polynomial sample and computational complexity for independent Nash equilibrium learning in the underlying POMG.

Philip Jordan, Maryam Kamgarpour

SYCAMORE, EPFL

Nash Equilibrium Reinforcement Learning Imperfect-Information Games Partially Observable RL Game Theory Decentralized MARL+1

Date pendingcs.MA

Stability and Convergence of Optimistic Exponential Weights with Asymmetric Step Sizes in Bimatrix Games

We study bimatrix two-player games and investigate the last-iterate convergence and stability of equilibria for the iterates generated by the optimistic exponential weights method. In contrast to prior work, we allow the step sizes

\eta_x

and

\eta_y

to differ. Our first main result establishes, under the assumption that the set of fixed points is finite, a sufficient condition for global last-iterate convergence in the special case of zero-sum games, which constrains only the product

\eta_x\eta_y

of the step sizes. This condition is practically relevant and partially explains empirically observed behavior. Our second main result provides an almost-tight threshold for asymptotic stability and instability, again in terms of products of the step sizes, for general bimatrix games. This result is primarily of theoretical interest. We derive several known results and practically relevant step size bounds for special cases and illustrate our results by experiments.

Hédi Hadiji, Sarah Sachs

Laboratoire des Signaux et Systèmes, CentraleSupélec, Paris, France · School of Mathematics, University of Bristol, Bristol, United Kingdom

Nash Equilibrium Last-Iterate Convergence Game Theory Zero-Sum Games Convergence Analysis Nash Equilibrium Computation