Nash Equilibrium Computation

Follow this topic Ask about this topic

The field studies how to find strategy profiles in which no player can improve by changing strategy alone, across settings such as matrix games, Markov games, auctions, and poker. Methods include regret minimization and counterfactual regret minimization, best-response and fictitious-play dynamics, mirror-descent methods, and optimization formulations such as linear complementarity problems and quadratic programs. Researchers also use reinforcement learning and offline data to estimate equilibria when payoffs or transitions are unknown, with exploitability, regret, and equilibrium residuals serving as common evaluation measures. A central tension is that scalable methods often provide approximate or average-iterate guarantees, while exact computation, last-iterate convergence, and principled equilibrium selection remain difficult in multiplayer and imperfect-information games.

Latest papers

70 papers12 papers in the last four weeks, up 9% on the four weeks before. 0.1% of all new papers.

Asymmetric Nash Seeking via Best Response Maps: Global Linear Convergence and Robustness to Inexact Reaction Models
Mar 17, 2026Mahdis Rabbani, Navid Mojahed, Shima NazariNash Equilibrium Computation Game Theory
Department of Mechanical and Aerospace Engineering, University of California, Davis, One Shield Ave, Davis, CA 95616.
NePPO: Near-Potential Policy Optimization for General-Sum Multi-Agent Reinforcement Learning
Mar 7, 2026Addison Kalanther, Sanika Bharvirkar, Shankar Sastry +1Multi-Agent Reinforcement Learning Game-Theoretic RL
Electrical Engineering and Computer Sciences, UC Berkeley · Electrical and Computer Engineering, Data Science & Artificial Intelligence Institute, Johns Hopkins University
Efficient Uncoupled Learning Dynamics with $\tilde{O}\!\left(T^{-1/4}\right)$ Last-Iterate Convergence in Bilinear Saddle-Point Problems over Convex Sets under Bandit Feedback
Feb 24, 2026Arnab Maiti, Claire Jie Zhang, Kevin Jamieson +3Bandit Learning Last-Iterate Convergence
University of Washington · Amazon · University of California, Irvine
Learning Distributed Equilibria in Linear-Quadratic Stochastic Differential Games: An $α$ -Potential Approach
Feb 18, 2026Philipp Plank, Yufei ZhangGame Theory Nash Equilibrium Computation
Department of Mathematics, Imperial College London, London, UK
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 Computation 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
Safe Equilibrium
Jan 12, 2022Sam GanzfriedGame Theory Nash Equilibrium
Ganzfried Research

Mar 17, 2026J/K move · Enter open · S save

Asymmetric Nash Seeking via Best Response Maps: Global Linear Convergence and Robustness to Inexact Reaction Models

Mahdis Rabbani, Navid Mojahed, Shima Nazari

Department of Mechanical and Aerospace Engineering, University of California, Davis, One Shield Ave, Davis, CA 95616.

Nash Equilibrium Computation Game Theory

Open paper AskPDF arXiv

Nash equilibria provide a principled framework for modeling interactions in multi-agent decision-making and control. However, many equilibrium-seeking methods implicitly assume that each agent has access to the other agents' objectives and constraints, an assumption that is often unrealistic in practice. This letter studies a class of asymmetric-information two-player constrained games with decoupled feasible sets, in which Player 1 knows its own objective and constraints while Player 2 is available only through a best-response map. For this class of games, we propose an asymmetric projected gradient descent-best response iteration that does not require full mutual knowledge of both players' optimization problems. Under suitable regularity conditions, we establish the existence and uniqueness of the Nash equilibrium and prove global linear convergence of the proposed iteration when the best-response map is exact. Recognizing that best-response maps are often learned or estimated, we further analyze the inexact case and show that, when the approximation error is uniformly bounded by

\varepsilon

, the iterates enter an explicit

O(\varepsilon)

neighborhood of the true Nash equilibrium. Numerical results on a benchmark game corroborate the predicted convergence behavior and error scaling.