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

Arrow-Debreu marketBrouwer's fixed pointLemke-Howson algorithmNash equilibriumPPAD-completenesssmoothed analysisSperner's lemmatwo-player game

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 2-person games (91A05) Noncooperative games (91A10) 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)

• A note on approximate Nash equilibria
• On the computational complexity of Nash equilibria for \((0,1)\) bimatrix games
• On the complexity of an expanded Tarski's fixed point problem under the componentwise ordering
• Computing pure Nash equilibria in network revenue management games
• Complexity of rational and irrational Nash equilibria
• Colorful linear programming, Nash equilibrium, and pivots
• Computing solutions of the multiclass network equilibrium problem with affine cost functions
• Equilibrium paths in discounted supergames
• Towards a unified complexity theory of total functions
• Approximation schemes for stochastic mean payoff games with perfect information and few random positions
• Limited lookahead in imperfect-information games
• The complexity of \((\mathsf{E}+\mathsf{Var})\)-equilibria, \(\mathsf{ESR}\)-equilibria, and \(\mathsf{SuperE}\)-equilibria for 2-players games with few cost values
• Lipschitz continuity and approximate equilibria
• 2-D Tucker is PPA complete
• The complexity of the parity argument with potential
• Continuous verifiable delay functions
• (In)existence of equilibria for 2-player, 2-value games with semistrictly quasiconcave cost functions
• The complexity of finding fair independent sets in cycles
• Two's company, three's a crowd: consensus-halving for a constant number of agents
• Multi-agent reinforcement learning: a selective overview of theories and algorithms
• Discrete versions of the KKM lemma and their PPAD-completeness
• Characterising the intersection of QMA and coQMA
• Fiat-Shamir for repeated squaring with applications to PPAD-hardness and VDFs
• Delegation with updatable unambiguous proofs and PPAD-hardness
• Equilibrium computation in resource allocation games
• An algorithm for finding approximate Nash equilibria in bimatrix games
• LP-based approximations for disjoint bilinear and two-stage adjustable robust optimization
• From minicrypt to obfustopia via private-key functional encryption
• Learning convex partitions and computing game-theoretic equilibria from best response queries
• Unique end of potential line
• Tatonnement beyond gross substitutes? Gradient descent to the rescue
• Understanding PPA-completeness
• Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
• The Hairy Ball problem is PPAD-complete
• Cache me if you can: capacitated selfish replication games in networks
• Pure Nash equilibria in graphical games and treewidth
• Polynomial-time computation of exact correlated equilibrium in compact games
• Query complexity of approximate equilibria in anonymous games
• Parameterized complexity of sparse linear complementarity problems
• Recursive stochastic games with positive rewards
• Computational aspects of uncertainty profiles and angel-daemon games
• The complexity of computational problems about Nash equilibria in symmetric win-lose games
• Belief-invariant and quantum equilibria in games of incomplete information
• Beyond the worst-case analysis of random priority: smoothed and average-case approximation ratios in mechanism design
• Total functions in QMA
• Can almost everybody be almost happy?
• Lipschitz continuity and approximate equilibria
• Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium
• The complexity of computing a Nash equilibrium
• On the complexity of approximating a Nash equilibrium
• On pure Nash equilibria in stochastic games
• Computing Equilibria with Partial Commitment
• Distributed Methods for Computing Approximate Equilibria
• Computing approximate Nash equilibria in general network revenue management games
• Some tractable win-lose games
• Automatizability and simple stochastic games
• Inapproximability of NP-Complete Variants of Nash Equilibrium
• The Complexity of Nash Equilibria in Limit-Average Games
• How do you like your equilibrium selection problems? Hard, or very hard?
• 2-player Nash and nonsymmetric bargaining games: algorithms and structural properties
• ETR-completeness for decision versions of multi-player (symmetric) Nash equilibria
• Settling some open problems on 2-player symmetric Nash equilibria
• Approximating Nash equilibria in tree polymatrix games
• Smoothed analysis of local search algorithms
• A complementary pivot algorithm for market equilibrium under separable, piecewise-linear concave utilities
• Query complexity of approximate equilibria in anonymous games
• Inverse game theory: learning utilities in succinct games
• A glimpse at Paul G. Spirakis
• Weighted Boolean formula games
• On the performance of mildly greedy players in cut games
• The Linear Complementarity Problems with a Few Variables per Constraint
• Computing exact and approximate Nash equilibria in 2-player games
• The computational complexity of weak saddles
• \(\mathsf{PPAD}\)-completeness of polyhedral versions of Sperner's lemma
• Constant rank two-player games are PPAD-hard
• The computational complexity of finding a mixed Berge equilibrium for a k-person noncooperative game in normal form
• Inapproximability of Nash equilibrium
• Approximating Nash equilibria and dense subgraphs via an approximate version of Carathéodory's theorem
• Sperner's colorings and optimal partitioning of the simplex
• Network essence: PageRank completion and centrality-conforming Markov chains
• scientific article; zbMATH DE number 6866347 (Why is no real title available?)
• The journey from NP to TFNP hardness
• Towards a Unified Complexity Theory of Total Functions
• Fast Algorithms for Rank-1 Bimatrix Games
• Hardness results for consensus-halving
• Amortized Analysis of Asynchronous Price Dynamics
• Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
• On the complexity of stable fractional hypergraph matching
• Unique End of Potential Line
• The Hairy Ball Problem is PPAD-Complete.
• Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
• Computing approximate Nash equilibria in polymatrix games
• Hardness of continuous local search: query complexity and cryptographic lower bounds
• Structure versus hardness through the obfuscation lens
• On Stackelberg mixed strategies
• The complexity of computing a Nash equilibrium
• Substitution with satiation: a new class of utility functions and a complementary pivot algorithm
• Sum-of-squares meets Nash: lower bounds for finding any equilibrium
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• TFNP: an update

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)