Nash Equilibrium Computation

Overview

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

CardsList

76 papers4 papers in the last four weeks, down 71% on the four weeks before. 0.0% of all new papers.

  1. Virtual Double Oracle: Faster Convergence by Leveraging Strategies That Were Watching All Along

    Nov 17, 2026Ruilan Wang, Francisco Aristi Reina, Katerina PapadakiNash Equilibrium ComputationZero-Sum Games

  2. On the Convergence of Alternating Regret Matching Algorithms

    Nov 2, 2026Anh Duc Nguyen, Ioannis Anagnostides, Brian Hu Zhang +1Regret MinimizationNash Equilibrium Computation

  3. When Are We Near Nash? Certifying Solutions in General-Sum Games

    Oct 21, 2026Boning Li, Longbo HuangNash Equilibrium ComputationImperfect-Information Games

  4. IR-PRM+ with Previous-Utility Prediction: Constant Regret and Best-Iterate Convergence

    Oct 13, 2026Michael Sullins, Ian A. KashCounterfactual Regret MinimizationRegret Minimization

  5. Linear Last-Iterate Convergence Rates for Optimistic Learning in Harmonic Games

    Oct 13, 2026John Lazarsfeld, Anas Barakat, Jacob Abernethy +4Last-Iterate ConvergenceGame Theory

  6. Equilibrium Learning in Unbounded Stochastic Games with Gaussian Transitions

    Oct 12, 2026Jonathan Anthony Mavroforas, Fred RoostaNash Equilibrium ComputationReinforcement Learning

  7. DiffNash: Finding Nash Equilibrium in High-Dimensional Continuous Action Spaces with Diffusion Policies

    Oct 11, 2026Haichuan Wang, Anagha Satish, Jiale Zheng +4Nash Equilibrium ComputationGame-Playing Agents

  8. Fully Online Decentralized Learning in Stochastic Games with Unknown Independent Chains

    Oct 1, 2026S. Rasoul EtesamiGame TheoryOnline Mirror Descent

  9. Robust Nash Alignment under Preference Uncertainty

    Sep 30, 2026Shihab Ahmed, Debamita Ghosh, David Tang +3LLM AlignmentPreference Alignment

  10. Average-and Last-Iterate Lower Bounds for Optimistic Matrix Mirror-Prox in Quantum Zero-Sum Games

    Sep 30, 2026Yiheng Su, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Pucheng XiongLast-Iterate ConvergenceOracle Complexity

  11. Decentralized Decision-Making among Heterogeneous Autonomous Vehicles: An αα-Potential Game Framework

    Sep 30, 2026Anran Hu, Zhexin Wang, Yufei Zhang +1Game TheoryAutonomous Driving

  12. Inertia-Corrected Newton Method For Generalized Nash Equilibria in Dynamic Games with Optimality Verification

    Sep 25, 2026Zhiyuan Zhang, Panagiotis TsiotrasNash Equilibrium ComputationGame Theory

  13. Game-Theoretic Control with Constrained Potential Surgery

    Sep 25, 2026Zhiyuan Zhang, Panagiotis TsiotrasNash Equilibrium ComputationGame Theory

  14. Context-dependent agent evaluation with orthogonal equilibrium learning

    Sep 25, 2026Haorui Ma, Zehua Zang, Jiangmeng Li +3Agent EvaluationAI Agent Evaluation

  15. Dynamical low-rank equilibrium computation for stochastic games between advanced persistent threats and moving target defense

    Sep 20, 2026Tian Zijian, Zhang He, Chen Xinjie +2Nash Equilibrium ComputationZero-Sum Games

  16. Guiding Agents of Quantum Games to Equilibrium using Matrix Exponential Fixed-Point Iteration

    Sep 18, 2026Alireza Habibi, Luis F. Abanto Leon, Setareh MaghsudiNash Equilibrium Computation

  17. Efficient Nash Equilibrium Computation for Cybersecurity Games

    Sep 16, 2026Michael Lanier, David Farmer, Yevgeniy VorobeychikGame TheoryGeneral-Sum Games

  18. High-Probability Nash Regret for Decentralized Learning in Markov αα-Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games

    Sep 14, 2026S. Rasoul EtesamiPolicy GradientAsynchronous RL

  19. Inference-Time Nash Alignment

    Sep 8, 2026Hadi Hosseini, Debmalya Mandal, Duohan ZhangInference-Time OptimizationPreference Alignment

  20. Robust PAC Learning of Concurrent Stochastic Games

    Sep 3, 2026Angel Y. He, David ParkerGame TheoryRobust RL

  21. Fully Distributed GNE Algorithms for Multi-Robot Placement without Consensus on Multipliers

    Aug 29, 2026Shao-An Yin, Mingyi Hong, Nicola EliaNash Equilibrium ComputationDistributed Optimization

  22. Optimal Alternating Regret for Online Learning and Games

    Aug 25, 2026Yixin Tao, Weiqiang ZhengOnline LPOnline Convex Optimization