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)- Structure versus hardness through the obfuscation lens
- TFNP: an update
- The computational complexity of weak saddles
- PPAD-complete approximate pure Nash equilibria in Lipschitz games
- The Linear Complementarity Problems with a Few Variables per Constraint
- Can almost everybody be almost happy?
- Complexity of equilibria in first-price auctions under general tie-breaking rules
- Planning and learning in partially observable systems via filter stability
- Metastability of logit dynamics for coordination games
- On the complexity of approximating a Nash equilibrium
- Tropical Complementarity Problems and Nash Equilibria
- Multi-agent reinforcement learning: a selective overview of theories and algorithms
- Learning convex partitions and computing game-theoretic equilibria from best response queries
- Note on constrained long choice with multiple beginning elements
- scientific article; zbMATH DE number 7662165 (Why is no real title available?)
- Cache me if you can: capacitated selfish replication games in networks
- Pure Nash equilibria in graphical games and treewidth
- Colorful linear programming, Nash equilibrium, and pivots
- A glimpse at Paul G. Spirakis
- Automated equilibrium analysis of \(2\times 2\times 2\) games
- Semidefinite programming for min-max problems and games
- (In)existence of equilibria for 2-player, 2-value games with semistrictly quasiconcave cost functions
- On pure Nash equilibria in stochastic games
- Evolution of Mixed Strategies in Monotone Games
- Optimal private payoff manipulation against commitment in extensive-form games
- Equilibrium paths in discounted supergames
- Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
- On the computational complexity of Nash equilibria for \((0,1)\) bimatrix games
- Computing equilibria: a computational complexity perspective
- Two Algorithms for Computing Exact and Approximate Nash Equilibria in Bimatrix Games
- Distributed methods for computing approximate equilibria
- The complexity of finding fair independent sets in cycles
- Correlated equilibria and fairness in concurrent stochastic games
- On Stackelberg mixed strategies
- Inverse game theory: learning utilities in succinct games
- Approximating Nash equilibria and dense subgraphs via an approximate version of Carathéodory's theorem
- Smoothed analysis of local search algorithms
- \(\mathsf{PPAD}\)-completeness of polyhedral versions of Sperner's lemma
- Tatonnement beyond gross substitutes? Gradient descent to the rescue
- The Hairy Ball problem is PPAD-complete
- Automatizability and simple stochastic games
- 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
- LP-based approximations for disjoint bilinear and two-stage adjustable robust optimization
- Two's company, three's a crowd: consensus-halving for a constant number of agents
- Computational complexity of decision problems about Nash equilibria in win-lose multi-player games
- Reducibility among fractional stability problems
- 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
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)
