Settling the complexity of computing two-player Nash equilibria

2009/05/01 by Xi Chen, Xiaotie Deng, Shang-Hua Teng +1 · 579 citations
Decision Sciences · Economics, Econometrics and Finance · Mathematics · #Class (philosophy) #Combinatorics #Complexity class #Computer science #Discrete mathematics #Economic theories and models #Game Theory and Applications #Game Theory and Voting Systems #Game theory #Mathematical economics #Mathematics #Nash equilibrium #Polynomial #Time complexity

paper · doi:10.1145/1516512.1516516

published in Journal of the ACM 56(3), 1-57 (Association for Computing Machinery)

openalex publication_date 2009/05/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

We prove that Bimatrix, the problem of finding a Nash equilibrium in a two-player game, is complete for the complexity class PPAD (Polynomial Parity Argument, Directed version) introduced by Papadimitriou in 1991. Our result, building upon the work of Daskalakis et al. [2006a] on the complexity of four-player Nash equilibria, settles a long standing open problem in algorithmic game theory. It also serves as a starting point for a series of results concerning the complexity of two-player Nash equilibria. In particular, we prove the following theorems: —Bimatrix does not have a fully polynomial-time approximation scheme unless every problem in PPAD is solvable in polynomial time. —The smoothed complexity of the classic Lemke-Howson algorithm and, in fact, of any algorithm for Bimatrix is not polynomial unless every problem in PPAD is solvable in randomized polynomial time. Our results also have a complexity implication in mathematical economics: —Arrow-Debreu market equilibria are PPAD -hard to compute.

Citations

• Non-Cooperative Games

Cited by

• Pure-Circuit: Tight Inapproximability for PPAD
• Unique end of potential line
• When Is Delegated Play Truthful? Within-Range Regret and the Trilemma of Aligned Delegation
• A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games
• Constant Rank Two-Player Games are PPAD-hard
• Learning in Nonzero-Sum Stochastic Games with Potentials
• FPTAS for Mixed-Strategy Nash Equilibria in Tree Graphical Games and Their Generalizations
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• Correlated Equilibria for Approximate Variational Inference in MRFs
• Efficient Equilibrium Computation in Symmetric First-Price Auctions
• Solving Combinatorial Games using Products, Projections and Lexicographically Optimal Bases
• Settling Some Open Problems on 2-Player Symmetric Nash Equilibria
• (weak) Calibration is Computationally Hard
• The Complexity of Min-Max Optimization with Product Constraints
• A Converse to Banach's Fixed Point Theorem and its CLS Completeness
• On Altruism and Spite in Bimatrix Games
• Interdependent Defense Games: Modeling Interdependent Security under Deliberate Attacks
• Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games
• Decentralized Reinforcement Learning: Global Decision-Making via Local Economic Transactions
• Throttling Equilibria in Auction Markets
• The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions
• On the Complexity of Nash Equilibria in Anonymous Games
• A Manifold of Polynomial Time Solvable Bimatrix Games
• Equilibria in Quantitative Concurrent Games
• Quantum Strategic Game Theory
• Convergence of Regret Matching in Potential Games and Constrained Optimization
• Near-Optimal Quantum Algorithms for Computing (Coarse) Correlated Equilibria of General-Sum Games
• Finding a Nash equilibrium of a random win-lose game in expected polynomial time
• On the Complexity of Stationary Nash Equilibria in Discounted Perfect Information Stochastic Games
• The Hidden Game Problem
• The Complexity of Sparse Win-Lose Bimatrix Games
• Approximate Well-supported Nash Equilibria below Two-thirds
• The Weihrauch degree of finding Nash equilibria in multiplayer games
• Communication complexity of Nash equilibrium in potential games
• Discovering Expert-Level Nash Equilibrium Algorithms with Large Language Models
• Communication Complexity of Correlated Equilibrium in Two-Player Games
• Distributionally Robust Markov Games with Average Reward
• Computing Constrained Approximate Equilibria in Polymatrix Games
• Hierarchies within TFNP: building blocks and collapses
• Near-Optimal No-Regret Learning in General Games
• The Complexity of Non-Monotone Markets
• An Empirical Study of Finding Approximate Equilibria in Bimatrix Games
• Distributed Nash Equilibrium Seeking in Non-Monotone Games over the Simplex
• Computational Complexity of Approximate Nash Equilibrium in Large Games
• Combining local search techniques and path following for bimatrix games
• High-Order Deep Meta-Learning with Category-Theoretic Interpretation
• Inapproximability of NP-Complete Variants of Nash Equilibrium
• Computing solutions of the multiclass network equilibrium problem with affine cost functions
• Tractable Graph Structures in EFX Orientation
• Query Complexity of Correlated Equilibrium
• Value-Set Iteration: Computing Optimal Correlated Equilibria in Infinite-Horizon Multi-Player Stochastic Games
• A Hybrid Adaptive Nash Equilibrium Solver for Distributed Multi-Agent Systems with Game-Theoretic Jump Triggering
• On the Communication Complexity of Approximate Nash Equilibria
• Linear Production Games with Non-transferable Utilities
• The Computational Complexity of Financial Networks with Credit Default Swaps
• Computing Equilibria with Partial Commitment
• The Query Complexity of Local Search and Brouwer in Rounds
• The Complexity of Correlated Equilibria in Generalized Games
• Constant Rank Bimatrix Games are PPAD-hard
• Smoothed and Average-case Approximation Ratios of Mechanisms: Beyond the Worst-case Analysis
• MODE: Mutual Optimality in Direct Effects of Reciprocal Recommendations in Matching Markets
• The Complexity of the Path-following Solutions of Two-dimensional Sperner/Brouwer Functions
• The Mysteries of Security Games: Equilibrium Computation Becomes Combinatorial Algorithm Design
• Support Contraction for Well-Supported Nash Equilibria
• A Geometric Approach to Combinatorial Fixed-Point Theorems
• Computational Complexity of the α-Ham-Sandwich Problem
• Convergence of Time-Averaged Mean Field Gradient Descent Dynamics for Continuous Multi-Player Zero-Sum Games
• Monotonic and Non-Monotonic Solution Concepts for Generalized Circuits
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium
• Why Prices Need Algorithms
• Consensus-Halving: Does It Ever Get Easier?
• The complexity of splitting necklaces and bisecting ham sandwiches
• Consensus halving is PPA-complete
• Two's Company, Three's a Crowd: Consensus-Halving for a Constant Number of Agents
• Sperner’s Colorings and Optimal Partitioning of the Simplex
• On the Verification and Computation of Strong Nash Equilibrium
• Hardness of Approximation Between P and NP
• Analyzing Games with Ambiguous Player Types using the \rm MINthenMAX Decision Model
• How Hard Is It to Approximate the Best Nash Equilibrium?
• 2-Player Nash and Nonsymmetric Bargaining Games: Algorithms and Structural Properties
• Ranking games that have competitiveness-based strategies
• On the dimensions of correlated equilibrium polytopes of generic games
• Sublogarithmic Swap Regret in Multiplayer General-Sum Games via Hybrid Regularization
• The Classes PPA-k: Existence from Arguments Modulo k
• Query Complexity of Approximate Equilibria in Anonymous Games
• Distributed Methods for Computing Approximate Equilibria
• From Nash Equilibria to Chain Recurrent Sets: An Algorithmic Solution Concept for Game Theory. [europepmc]
• On the complexity of computing Markov perfect equilibrium in general-sum stochastic games. [europepmc]
• Cognitive models facilitate real-time inference of latent motives. [europepmc]

Related

• Settling the Complexity of Computing Two-Player Nash Equilibria
• Computing Nash Equilibria: Approximation and Smoothed Complexity
• A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games
• A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games
• Settling Some Open Problems on 2-Player Symmetric Nash Equilibria