Settling the complexity of computing two-player Nash equilibria

DOI10.1145/1516512.1516516MaRDI QIDQ3452212zbMATH OpenOpenAlexFDO

Authors Xi Chen, Xiaotie Deng, Shang-Hua Teng

Publication date 11 November 2015

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

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

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)

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.

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

Cited in

(only showing first 100 items - show all)

• Equilibrium paths in discounted supergames
• Polynomial-time computation of exact correlated equilibrium in compact games
• The computational complexity of weak saddles
• Evolution of Mixed Strategies in Monotone Games
• Inapproximability of Nash equilibrium
• On the complexity of an expanded Tarski's fixed point problem under the componentwise ordering
• Computing solutions of the multiclass network equilibrium problem with affine cost functions
• On the complexity of deciding bimatrix games similarity
• Continuous verifiable delay functions
• The Complexity of Nash Equilibria in Limit-Average Games
• From Minicrypt to Obfustopia via private-key functional encryption
• The Linear Complementarity Problems with a Few Variables per Constraint
• Inverse game theory: learning utilities in succinct games
• A complementary pivot algorithm for market equilibrium under separable, piecewise-linear concave utilities
• Hard-to-Solve Bimatrix Games
• Computing exact and approximate Nash equilibria in 2-player games
• On pure Nash equilibria in stochastic games
• On the Complexity of Equilibrium Computation in First-Price Auctions
• The complexity of computing a Nash equilibrium
• Limited lookahead in imperfect-information games
• Colorful linear programming, Nash equilibrium, and pivots
• ETR-completeness for decision versions of multi-player (symmetric) Nash equilibria
• From minicrypt to obfustopia via private-key functional encryption
• Computing approximate Nash equilibria in polymatrix games
• Public goods games in directed networks
• Towards a unified complexity theory of total functions
• Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium
• Computing pure Nash equilibria in network revenue management games
• Metastability of logit dynamics for coordination games
• On the performance of mildly greedy players in cut games
• Two Algorithms for Computing Exact and Approximate Nash Equilibria in Bimatrix Games
• Weighted Boolean formula games
• The complexity of computational problems about Nash equilibria in symmetric win-lose games
• On the computational complexity of Nash equilibria for \((0,1)\) bimatrix games
• Discrete versions of the KKM lemma and their PPAD-completeness
• Distributed methods for computing approximate equilibria
• Lipschitz continuity and approximate equilibria
• The complexity of equilibria: Hardness results for economies via a correspondence with games
• Lipschitz continuity and approximate equilibria
• Reducibility among fractional stability problems
• Multi-agent reinforcement learning: a selective overview of theories and algorithms
• 2-player Nash and nonsymmetric bargaining games: algorithms and structural properties
• Recursive stochastic games with positive rewards
• Can almost everybody be almost happy?
• \(\mathsf{PPAD}\)-completeness of polyhedral versions of Sperner's lemma
• Query complexity of approximate equilibria in anonymous games
• Understanding PPA-completeness
• Belief-invariant and quantum equilibria in games of incomplete information
• Structure versus hardness through the obfuscation lens
• Interdependent defense games with applications to internet security at the level of autonomous systems
• Complexity of rational and irrational Nash equilibria
• Computing Nash equilibria for two-player restricted network congestion games is \(\mathcal{PLS}\)-complete
• LP-based approximations for disjoint bilinear and two-stage adjustable robust optimization
• Semidefinite programming for min-max problems and games
• On Stackelberg mixed strategies
• The complexity of computing a Nash equilibrium
• Inapproximability of NP-Complete Variants of Nash Equilibrium
• Network essence: PageRank completion and centrality-conforming Markov chains
• An algorithm for finding approximate Nash equilibria in bimatrix games
• A note on approximate Nash equilibria
• Hardness of continuous local search: query complexity and cryptographic lower bounds
• Approximating Nash equilibria in tree polymatrix games
• Pure Nash equilibria in graphical games and treewidth
• 2-D Tucker is PPA complete
• Towards a Unified Complexity Theory of Total Functions
• Computing approximate Nash equilibria in general network revenue management games
• Approximation schemes for stochastic mean payoff games with perfect information and few random positions
• TFNP: an update
• Computational aspects of uncertainty profiles and angel-daemon games
• Distributed Methods for Computing Approximate Equilibria
• On the complexity of approximating a Nash equilibrium
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• Computing equilibria: a computational complexity perspective
• The complexity of \((\mathsf{E}+\mathsf{Var})\)-equilibria, \(\mathsf{ESR}\)-equilibria, and \(\mathsf{SuperE}\)-equilibria for 2-players games with few cost values
• Hardness results for consensus-halving
• A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games
• SNARGs and PPAD hardness from the decisional Diffie-Hellman assumption
• Two's company, three's a crowd: consensus-halving for a constant number of agents
• Unique End of Potential Line
• Provably efficient reinforcement learning in decentralized general-sum Markov games
• Consensus Halving for Sets of Items
• A glimpse at Paul G. Spirakis
• Substitution with satiation: a new class of utility functions and a complementary pivot algorithm
• Tight inapproximability of Nash equilibria in public goods games
• scientific article; zbMATH DE number 7662165 (Why is no real title available?)
• Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
• Equilibrium computation in resource allocation games
• LP-based approximations for disjoint bilinear and two-stage adjustable robust optimization
• Query complexity of approximate equilibria in anonymous games
• The complexity of the parity argument with potential
• Computing lexicographically safe Nash equilibria in finite two-person games with tight game forms given by oracles
• The journey from NP to TFNP hardness
• Computational complexity of decision problems about Nash equilibria in win-lose multi-player games
• The complexity of finding fair independent sets in cycles
• Complexity of equilibria in first-price auctions under general tie-breaking rules
• How do you like your equilibrium selection problems? Hard, or very hard?
• Planning and learning in partially observable systems via filter stability
• The Hairy Ball Problem is PPAD-Complete.
• Some tractable win-lose games
• Sum-of-squares meets Nash: lower bounds for finding any equilibrium

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)