Settling the complexity of computing two-player Nash equilibria

DOI10.1145/1516512.1516516zbMATH Open1325.68095arXiv0704.1678OpenAlexW2057913812MaRDI QIDQ3452212FDOQ3452212

Authors: Xi Chen, Xiaotie Deng, Shang-Hua Teng 

Publication date: 11 November 2015

Published in: Journal of the ACM (Search for Journal in Brave)

Abstract: We settle a long-standing open question in algorithmic game theory. 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. This is the first of a series of results concerning the complexity of 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 demonstrate that, even in the simplest form of non-cooperative games, equilibrium computation and approximation are polynomial-time equivalent to fixed point computation. Our results also have two broad complexity implications in mathematical economics and operations research: Arrow-Debreu market equilibria are PPAD-hard to compute. The P-Matrix Linear Complementary Problem is computationally harder than convex programming unless every problem in PPAD is solvable in polynomial time.

Full work available at URL: https://arxiv.org/abs/0704.1678

Recommendations

• The complexity of computing a Nash equilibrium
• The complexity of computing a Nash equilibrium
• On the Complexity of Nash Equilibria and Other Fixed Points
• On the complexity of approximating a Nash equilibrium
• Inapproximability of Nash equilibrium

zbMATH Keywords

Nash equilibriumSperner's lemmaLemke-Howson algorithmsmoothed analysistwo-player gamePPAD-completenessArrow-Debreu marketBrouwer's fixed point

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Noncooperative games (91A10) 2-person games (91A05) Special types of economic equilibria (91B52)

Cited In (only showing first 100 items - show all)

• On the complexity of an expanded Tarski's fixed point problem under the componentwise ordering
• On the complexity of deciding bimatrix games similarity
• Limited lookahead in imperfect-information games
• Hardness of continuous local search: query complexity and cryptographic lower bounds
• On the Complexity of Equilibrium Computation in First-Price Auctions
• Towards a unified complexity theory of total functions
• An algorithm for finding approximate Nash equilibria in bimatrix games
• Computing solutions of the multiclass network equilibrium problem with affine cost functions
• Computing exact and approximate Nash equilibria in 2-player games
• 2-player Nash and nonsymmetric bargaining games: algorithms and structural properties
• Approximating Nash equilibria in tree polymatrix games
• Weighted Boolean formula games
• Discrete versions of the KKM lemma and their PPAD-completeness
• The complexity of computing a Nash equilibrium
• Communication complexity of approximate Nash equilibria
• Network essence: PageRank completion and centrality-conforming Markov chains
• The Complexity of Nash Equilibria in Limit-Average Games
• A complementary pivot algorithm for market equilibrium under separable, piecewise-linear concave utilities
• Query complexity of approximate equilibria in anonymous games
• Approximation schemes for stochastic mean payoff games with perfect information and few random positions
• Computing Nash equilibria for two-player restricted network congestion games is \(\mathcal{PLS}\)-complete
• Interdependent defense games with applications to internet security at the level of autonomous systems
• Computing approximate Nash equilibria in general network revenue management games
• From Minicrypt to Obfustopia via private-key functional encryption
• On the communication complexity of approximate Nash equilibria
• Inapproximability of Nash equilibrium
• From minicrypt to obfustopia via private-key functional encryption
• Belief-invariant and quantum equilibria in games of incomplete information
• Computational aspects of uncertainty profiles and angel-daemon games
• Hardness results for consensus-halving
• Recursive stochastic games with positive rewards
• Distributed Methods for Computing Approximate Equilibria
• Mixing time and stationary expected social welfare of logit dynamics
• Computing pure Nash equilibria in network revenue management games
• A note on approximate Nash equilibria
• Continuous verifiable delay functions
• Hard-to-Solve Bimatrix Games
• Computing approximate Nash equilibria in polymatrix games
• Approximate well-supported Nash equilibria below two-thirds
• ETR-completeness for decision versions of multi-player (symmetric) Nash equilibria
• Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium
• Public goods games in directed networks
• The complexity of equilibria: Hardness results for economies via a correspondence with games
• Inapproximability of NP-Complete Variants of Nash Equilibrium
• Complexity of rational and irrational Nash equilibria
• Polynomial-time computation of exact correlated equilibrium in compact games
• The complexity of computing a Nash equilibrium
• Towards a Unified Complexity Theory of Total Functions
• On the performance of mildly greedy players in cut games
• Lipschitz continuity and approximate equilibria
• Lipschitz continuity and approximate equilibria
• Structure versus hardness through the obfuscation lens
• The computational complexity of weak saddles
• The Linear Complementarity Problems with a Few Variables per Constraint
• Metastability of logit dynamics for coordination games
• Can almost everybody be almost happy?
• On the complexity of approximating a Nash equilibrium
• Multi-agent reinforcement learning: a selective overview of theories and algorithms
• On the approximation performance of fictitious play in finite games
• Pure Nash equilibria in graphical games and treewidth
• Evolution of Mixed Strategies in Monotone Games
• On pure Nash equilibria in stochastic games
• Colorful linear programming, Nash equilibrium, and pivots
• Semidefinite programming for min-max problems and games
• Parameterized two-player Nash equilibrium
• Equilibrium paths in discounted supergames
• Two Algorithms for Computing Exact and Approximate Nash Equilibria in Bimatrix Games
• On the computational complexity of Nash equilibria for \((0,1)\) bimatrix games
• Computing equilibria: a computational complexity perspective
• Inverse game theory: learning utilities in succinct games
• Distributed methods for computing approximate equilibria
• On Stackelberg mixed strategies
• Reducibility among fractional stability problems
• \(\mathsf{PPAD}\)-completeness of polyhedral versions of Sperner's lemma
• LP-based approximations for disjoint bilinear and two-stage adjustable robust optimization
• The complexity of computational problems about Nash equilibria in symmetric win-lose games
• Tight inapproximability of Nash equilibria in public goods games
• Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
• Characterising the intersection of QMA and coQMA
• Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
• The Hairy Ball Problem is PPAD-Complete.
• Sum-of-squares meets Nash: lower bounds for finding any equilibrium
• Delegation with updatable unambiguous proofs and PPAD-hardness
• Fiat-Shamir for repeated squaring with applications to PPAD-hardness and VDFs
• Title not available (Why is that?)
• The complexity of gradient descent: CLS = PPAD \(\cap\) pls
• The exact computational complexity of evolutionarily stable strategies
• Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
• The complexity of \((\mathsf{E}+\mathsf{Var})\)-equilibria, \(\mathsf{ESR}\)-equilibria, and \(\mathsf{SuperE}\)-equilibria for 2-players games with few cost values
• On the complexity of stable fractional hypergraph matching
• Total functions in QMA
• Constant rank two-player games are PPAD-hard
• Substitution with satiation: a new class of utility functions and a complementary pivot algorithm
• The computational complexity of finding a mixed Berge equilibrium for a \(k\)-person noncooperative game in normal form
• 2-D Tucker is PPA complete
• PPAD-complete pure approximate Nash equilibria in Lipschitz games
• Understanding PPA-completeness
• Fast Algorithms for Rank-1 Bimatrix Games
• The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich
• Consensus Halving for Sets of Items

This page was built for publication: Settling the complexity of computing two-player Nash equilibria

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3452212)