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)

• 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
• Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
• Amortized Analysis of Asynchronous Price Dynamics
• Tatonnement beyond gross substitutes? Gradient descent to the rescue
• The computational complexity of weak saddles
• Automatizability and simple stochastic games
• (In)existence of equilibria for 2-player, 2-value games with semistrictly quasiconcave cost functions
• Approximating Nash equilibria and dense subgraphs via an approximate version of Carathéodory's theorem
• Computing Equilibria with Partial Commitment
• The classes PPA-\(k\): existence from arguments modulo \(k\)
• PPAD-complete pure approximate Nash equilibria in Lipschitz games
• Total functions in QMA
• Tropical Complementarity Problems and Nash Equilibria
• Simultaneous contests with equal sharing allocation of prizes: computational complexity and price of anarchy
• Parameterized complexity of sparse linear complementarity problems
• The Hairy Ball problem is PPAD-complete
• A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games
• Constant rank two-player games are PPAD-hard
• Sperner's colorings and optimal partitioning of the simplex
• Correlated equilibria and fairness in concurrent stochastic games
• Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
• PPAD-complete approximate pure Nash equilibria in Lipschitz games
• Unique end of potential line
• The classes PPA-\(k\): existence from arguments modulo \(k\)
• Automated equilibrium analysis of \(2\times 2\times 2\) games
• Learning convex partitions and computing game-theoretic equilibria from best response queries
• Two-person adversarial games are zero-sum: an elaboration of a folk theorem
• Consensus-Halving: Does It Ever Get Easier?
• Delegation with updatable unambiguous proofs and PPAD-hardness
• Fiat-Shamir for repeated squaring with applications to PPAD-hardness and VDFs
• Cache me if you can: capacitated selfish replication games in networks
• Smoothed analysis of local search algorithms
• Settling some open problems on 2-player symmetric Nash equilibria
• The complexity of gradient descent: CLS = PPAD \(\cap\) pls
• Beyond the worst-case analysis of random priority: smoothed and average-case approximation ratios in mechanism design
• Characterising the intersection of QMA and coQMA
• The computational complexity of finding a mixed Berge equilibrium for a \(k\)-person noncooperative game in normal form
• scientific article; zbMATH DE number 6866347 (Why is no real title available?)
• Can PPAD hardness be based on standard cryptographic assumptions?
• Fast Algorithms for Rank-1 Bimatrix Games
• PPAD is as hard as LWE and iterated squaring
• A fast algorithm to solve large-scale matrix games based on dimensionality reduction and its application in multiple unmanned combat air vehicles attack-defense decision-making
• On the complexity of stable fractional hypergraph matching
• Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
• Note on constrained long choice with multiple beginning elements
• Optimal private payoff manipulation against commitment in extensive-form games
• The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich
• 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

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)