Settling the complexity of computing two-player Nash equilibria
From MaRDI portal
Publication:3452212
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
Cited in
(only showing first 100 items - show all)- The complexity of computational problems about Nash equilibria in symmetric win-lose games
- On the complexity of deciding bimatrix games similarity
- On the complexity of an expanded Tarski's fixed point problem under the componentwise ordering
- Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
- Limited lookahead in imperfect-information games
- The classes PPA-\(k\): existence from arguments modulo \(k\)
- Characterising the intersection of QMA and coQMA
- Tight inapproximability of Nash equilibria in public goods games
- Towards a unified complexity theory of total functions
- Hardness of continuous local search: query complexity and cryptographic lower bounds
- Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
- Delegation with updatable unambiguous proofs and PPAD-hardness
- Fiat-Shamir for repeated squaring with applications to PPAD-hardness and VDFs
- The Hairy Ball Problem is PPAD-Complete.
- Sum-of-squares meets Nash: lower bounds for finding any equilibrium
- On the Complexity of Equilibrium Computation in First-Price Auctions
- scientific article; zbMATH DE number 6866347 (Why is no real title available?)
- An algorithm for finding approximate Nash equilibria in bimatrix games
- Computing solutions of the multiclass network equilibrium problem with affine cost functions
- The complexity of gradient descent: CLS = PPAD \(\cap\) pls
- The complexity of \((\mathsf{E}+\mathsf{Var})\)-equilibria, \(\mathsf{ESR}\)-equilibria, and \(\mathsf{SuperE}\)-equilibria for 2-players games with few cost values
- Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
- On the complexity of stable fractional hypergraph matching
- Computing exact and approximate Nash equilibria in 2-player games
- Total functions in QMA
- 2-player Nash and nonsymmetric bargaining games: algorithms and structural properties
- Constant rank two-player games are PPAD-hard
- Approximating Nash equilibria in tree polymatrix games
- Discrete versions of the KKM lemma and their PPAD-completeness
- Substitution with satiation: a new class of utility functions and a complementary pivot algorithm
- Weighted Boolean formula games
- 2-D Tucker is PPA complete
- The computational complexity of finding a mixed Berge equilibrium for a \(k\)-person noncooperative game in normal form
- The complexity of computing a Nash equilibrium
- PPAD-complete pure approximate Nash equilibria in Lipschitz games
- 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
- Understanding PPA-completeness
- Approximation schemes for stochastic mean payoff games with perfect information and few random positions
- Query complexity of approximate equilibria in anonymous games
- Interdependent defense games with applications to internet security at the level of autonomous systems
- Fast Algorithms for Rank-1 Bimatrix Games
- How do you like your equilibrium selection problems? Hard, or very hard?
- Computing approximate Nash equilibria in general network revenue management games
- The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich
- Consensus Halving for Sets of Items
- The classes PPA-\(k\): existence from arguments modulo \(k\)
- Computing Nash equilibria for two-player restricted network congestion games is \(\mathcal{PLS}\)-complete
- Some tractable win-lose games
- From Minicrypt to Obfustopia via private-key functional encryption
- Settling some open problems on 2-player symmetric Nash equilibria
- From minicrypt to obfustopia via private-key functional encryption
- Inapproximability of Nash equilibrium
- Belief-invariant and quantum equilibria in games of incomplete information
- Computational aspects of uncertainty profiles and angel-daemon games
- Equilibrium computation in resource allocation games
- A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games
- Hardness results for consensus-halving
- Provably efficient reinforcement learning in decentralized general-sum Markov games
- Consensus-Halving: Does It Ever Get Easier?
- Can PPAD hardness be based on standard cryptographic assumptions?
- Unique End of Potential Line
- Recursive stochastic games with positive rewards
- Distributed Methods for Computing Approximate Equilibria
- The complexity of the parity argument with potential
- Computing pure Nash equilibria in network revenue management games
- A note on approximate Nash equilibria
- The journey from NP to TFNP hardness
- Amortized Analysis of Asynchronous Price Dynamics
- LP-based approximations for disjoint bilinear and two-stage adjustable robust optimization
- Computing approximate Nash equilibria in polymatrix games
- Continuous verifiable delay functions
- Computing Equilibria with Partial Commitment
- Unique end of potential line
- Hard-to-Solve Bimatrix Games
- Sperner's colorings and optimal partitioning of the simplex
- Query complexity of approximate equilibria in anonymous games
- ETR-completeness for decision versions of multi-player (symmetric) Nash equilibria
- A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games
- Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium
- Parameterized complexity of sparse linear complementarity problems
- The computational complexity of weak saddles
- Simultaneous contests with equal sharing allocation of prizes: computational complexity and price of anarchy
- The complexity of equilibria: Hardness results for economies via a correspondence with games
- SNARGs and PPAD hardness from the decisional Diffie-Hellman assumption
- Inapproximability of NP-Complete Variants of Nash Equilibrium
- Public goods games in directed networks
- Complexity of rational and irrational Nash equilibria
- PPAD is as hard as LWE and iterated squaring
- Polynomial-time computation of exact correlated equilibrium in compact games
- Two-person adversarial games are zero-sum: an elaboration of a folk theorem
- The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
- Beyond the worst-case analysis of random priority: smoothed and average-case approximation ratios in mechanism design
- On the performance of mildly greedy players in cut games
- The complexity of computing a Nash equilibrium
- Towards a Unified Complexity Theory of Total Functions
- Lipschitz continuity and approximate equilibria
- Lipschitz continuity and approximate equilibria
- Computing lexicographically safe Nash equilibria in finite two-person games with tight game forms given by oracles
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)
