The complexity of computing a Nash equilibrium

DOI10.1145/1132516.1132527zbMATH Open1301.68142OpenAlexW2140790422MaRDI QIDQ2931371FDOQ2931371

Authors: Constantinos Daskalakis, Paul W. Goldberg, Christos Papadimitriou 

Publication date: 25 November 2014

Published in: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.158.845

Recommendations

• The complexity of computing a Nash equilibrium
• The complexity of finding Nash equilibria
• On the complexity of approximating a Nash equilibrium
• scientific article; zbMATH DE number 6783488
• Computability of Nash equilibrium
• scientific article; zbMATH DE number 1842054
• On the computability of Nash equilibria
• The complexity of pure Nash equilibria
• The Computational Complexity of Nash Equilibria in Concisely Represented Games
• Settling the complexity of computing two-player Nash equilibria

zbMATH Keywords

game theorycomplexityNash equilibriumPPAD-completeness

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Noncooperative games (91A10) 2-person games (91A05)

Cited In (only showing first 100 items - show all)

• Some results of Maria Serna on strategic games: complexity of equilibria and models
• Equilibria, fixed points, and complexity classes
• On the complexity of constrained Nash equilibria in graphical games
• A direct reduction from \(k\)-player to 2-player approximate Nash equilibrium
• The Computational Complexity of Nash Equilibria in Concisely Represented Games
• Nash equilibria: complexity, symmetries, and approximation
• A simplicial approach for discrete fixed point theorems
• Approximate equilibria in strongly symmetric games
• Introduction to computer science and economic theory
• Action-graph games
• Existence of equilibria in a decentralized two-level supply chain
• Inverse Game Theory: Learning Utilities in Succinct Games
• Finding Gale strings
• New complexity results about Nash equilibria
• The complexity of uniform Nash equilibria and related regular subgraph problems
• Symmetries and the complexity of pure Nash equilibrium
• Propositional proofs and reductions between NP search problems
• Convergence to approximate Nash equilibria in congestion games
• Reducibility among equilibrium problems
• Load balancing without regret in the bulletin board model
• Deterministic calibration and Nash equilibrium
• Nash and correlated equilibria: Some complexity considerations
• Computing equilibria in discounted dynamic games
• Title not available (Why is that?)
• Walrasian equilibrium: Hardness, approximations and tractable instances
• On the performance of approximate equilibria in congestion games
• Computing correlated equilibria in multi-player games
• A note on approximate Nash equilibria
• Polynomial algorithms for approximating Nash equilibria of bimatrix games
• Computing Nash equilibria for scheduling on restricted parallel links
• Equilibria, fixed points, and complexity classes
• Recent development in computational complexity characterization of Nash equilibrium
• Approximate Equilibria for Strategic Two Person Games
• Noncooperative cost spanning tree games with budget restrictions
• Robust and scalable middleware for selfish-computer systems
• Imitation games and computation
• Higher order game dynamics
• The complexity of equilibria: Hardness results for economies via a correspondence with games
• Computational complexity in additive hedonic games
• Local and global price of anarchy of graphical games
• Alternating minima and maxima, Nash equilibria and bounded arithmetic
• The computational complexity of evolutionarily stable strategies
• Equilibria of graphical games with symmetries
• Reasoning about equilibria in game-like concurrent systems
• Well supported approximate equilibria in bimatrix games
• New algorithms for approximate Nash equilibria in bimatrix games
• The complexity of computing a Nash equilibrium
• The myth of the folk theorem
• How discontinuous is computing Nash equilibria? (Extended abstract)
• Separable and low-rank continuous games
• The computational complexity of weak saddles
• How incomputable is finding Nash equilibria?
• On the Complexity of Nash Equilibria and Other Fixed Points
• On the complexity of approximating a Nash equilibrium
• Ranking games
• Computing Cournot-Nash Equilibria
• Equilibria problems on games: complexity versus succinctness
• Approximate Nash Equilibria for Multi-player Games
• Zero-sum polymatrix games: a generalization of minmax
• Computer science and decision theory
• Correlated equilibria in continuous games: characterization and computation
• Approximate Nash equilibria in anonymous games
• An interior-point path-following algorithm for computing a Leontief economy equilibrium
• On the computational complexity of Nash equilibria for \((0,1)\) bimatrix games
• Computing equilibria: a computational complexity perspective
• A FPTAS for computing a symmetric leontief competitive economy equilibrium
• \(\mathsf{PPAD}\)-completeness of polyhedral versions of Sperner's lemma
• Convergence method, properties and computational complexity for Lyapunov games
• On the complexity of deciding bimatrix games similarity
• Price-based protocols for fair resource allocation
• The computational complexity of trembling hand perfection and other equilibrium refinements
• Title not available (Why is that?)
• Computability of Nash equilibrium
• Delegation with updatable unambiguous proofs and PPAD-hardness
• The Complexity of Nash Equilibria in Infinite Multiplayer Games
• The exact computational complexity of evolutionarily stable strategies
• ReGale: some memorable results
• The computation of approximate competitive equilibrium is PPAD-hard
• Decision Problems for Nash Equilibria in Stochastic Games
• 2-D Tucker is PPA complete
• Title not available (Why is that?)
• Multilinear Games
• Complexity of pure-strategy Nash equilibria in non-cooperative games
• How do you like your equilibrium selection problems? Hard, or very hard?
• Structure Versus Hardness Through the Obfuscation Lens
• The Complexity of Zero Knowledge
• A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games
• The Local and Global Price of Anarchy of Graphical Games
• Computing pure Nash equilibria in network revenue management games
• A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games
• Completeness for the complexity class \(\forall \exists \mathbb{R}\) and area-universality
• Title not available (Why is that?)
• The computational complexity of weak saddles
• Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium
• The truth behind the myth of the folk theorem
• A mixed 0-1 linear programming approach to the computation of all pure-strategy Nash equilibria of a finite \(n\)-person game in normal form
• Introduction to the special issue on learning and computational game theory
• PPAD is as hard as LWE and iterated squaring
• On the complexity of 2D discrete fixed point problem
• Random bimatrix games are asymptotically easy to solve (a simple proof)

This page was built for publication: The complexity of computing a Nash equilibrium

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2931371)