The complexity of computing a Nash equilibrium
From MaRDI portal
Publication:2931371
DOI10.1145/1132516.1132527zbMath1301.68142OpenAlexW2140790422MaRDI QIDQ2931371
Paul W. Goldberg, Constantinos Daskalakis, Christos H. 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
Noncooperative games (91A10) 2-person games (91A05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (76)
Some results of Maria Serna on strategic games: complexity of equilibria and models ⋮ The Computational Complexity of Trembling Hand Perfection and Other Equilibrium Refinements ⋮ Ranking games ⋮ On the complexity of constrained Nash equilibria in graphical games ⋮ Computing equilibria: a computational complexity perspective ⋮ Introduction to the special issue on learning and computational game theory ⋮ Inverse Game Theory: Learning Utilities in Succinct Games ⋮ ReGale: some memorable results ⋮ Reasoning about equilibria in game-like concurrent systems ⋮ Computing pure Nash equilibria in network revenue management games ⋮ Random bimatrix games are asymptotically easy to solve (a simple proof) ⋮ \(\mathsf{PPAD}\)-completeness of polyhedral versions of Sperner's lemma ⋮ A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games ⋮ A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games ⋮ Action-graph games ⋮ Equilibria of graphical games with symmetries ⋮ Multilinear Games ⋮ Completeness for the complexity class \(\forall \exists \mathbb{R}\) and area-universality ⋮ Local and global price of anarchy of graphical games ⋮ Convergence to approximate Nash equilibria in congestion games ⋮ Correlated equilibria in continuous games: characterization and computation ⋮ On the performance of approximate equilibria in congestion games ⋮ Higher order game dynamics ⋮ Propositional proofs and reductions between NP search problems ⋮ Recent development in computational complexity characterization of Nash equilibrium ⋮ Equilibria, fixed points, and complexity classes ⋮ Nash equilibria: complexity, symmetries, and approximation ⋮ 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 ⋮ Robust and scalable middleware for selfish-computer systems ⋮ Equilibria problems on games: complexity versus succinctness ⋮ New complexity results about Nash equilibria ⋮ Load balancing without regret in the bulletin board model ⋮ A FPTAS for computing a symmetric leontief competitive economy equilibrium ⋮ The complexity of uniform Nash equilibria and related regular subgraph problems ⋮ Computing equilibria in discounted dynamic games ⋮ Deterministic calibration and Nash equilibrium ⋮ Structure Versus Hardness Through the Obfuscation Lens ⋮ Walrasian equilibrium: Hardness, approximations and tractable instances ⋮ Approximate equilibria in strongly symmetric games ⋮ On the complexity of deciding bimatrix games similarity ⋮ The complexity of equilibria: Hardness results for economies via a correspondence with games ⋮ Introduction to computer science and economic theory ⋮ Approximate Nash equilibria in anonymous games ⋮ 2-D Tucker is PPA complete ⋮ Well supported approximate equilibria in bimatrix games ⋮ The computation of approximate competitive equilibrium is PPAD-hard ⋮ Unnamed Item ⋮ Computer science and decision theory ⋮ The truth behind the myth of the folk theorem ⋮ Imitation games and computation ⋮ The myth of the folk theorem ⋮ Noncooperative cost spanning tree games with budget restrictions ⋮ Separable and low-rank continuous games ⋮ Computing Nash equilibria for scheduling on restricted parallel links ⋮ Optimal deterministic auctions with correlated priors ⋮ Symmetries and the complexity of pure Nash equilibrium ⋮ The Complexity of Nash Equilibria in Infinite Multiplayer Games ⋮ The Complexity of Zero Knowledge ⋮ Approximate Equilibria for Strategic Two Person Games ⋮ The Local and Global Price of Anarchy of Graphical Games ⋮ Approximate Nash Equilibria for Multi-player Games ⋮ Zero-Sum Polymatrix Games: A Generalization of Minmax ⋮ Cache me if you can: capacitated selfish replication games in networks ⋮ A note on approximate Nash equilibria ⋮ Polynomial algorithms for approximating Nash equilibria of bimatrix games ⋮ A simplicial approach for discrete fixed point theorems ⋮ Existence of equilibria in a decentralized two-level supply chain ⋮ Decision Problems for Nash Equilibria in Stochastic Games ⋮ An interior-point path-following algorithm for computing a Leontief economy equilibrium ⋮ On the complexity of 2D discrete fixed point problem ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg ⋮ New algorithms for approximate Nash equilibria in bimatrix games ⋮ Convergence method, properties and computational complexity for Lyapunov games ⋮ Nash equilibria in all-optical networks ⋮ Price-based protocols for fair resource allocation ⋮ Unnamed Item
This page was built for publication: The complexity of computing a Nash equilibrium
