The complexity of computing a Nash equilibrium
From MaRDI portal
Publication:2931371
DOI10.1145/1132516.1132527zbMath1301.68142MaRDI QIDQ2931371
Christos H. Papadimitriou, Paul W. Goldberg, Constantinos Daskalakis
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
91A10: Noncooperative games
91A05: 2-person games
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
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, Computing Nash equilibria for scheduling on restricted parallel links, Propositional proofs and reductions between NP search problems, Action-graph games, Equilibria of graphical games with symmetries, 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, Equilibria problems on games: complexity versus succinctness, Load balancing without regret in the bulletin board model, A FPTAS for computing a symmetric leontief competitive economy equilibrium, An interior-point path-following algorithm for computing a Leontief economy equilibrium, Ranking games, On the complexity of constrained Nash equilibria in graphical games, Computing equilibria: a computational complexity perspective, New complexity results about Nash equilibria, The complexity of uniform Nash equilibria and related regular subgraph problems, Walrasian equilibrium: Hardness, approximations and tractable instances, On the complexity of deciding bimatrix games similarity, The complexity of equilibria: Hardness results for economies via a correspondence with games, Well supported approximate equilibria in bimatrix games, The computation of approximate competitive equilibrium is PPAD-hard, Imitation games and computation, The myth of the folk theorem, Separable and low-rank continuous games, Symmetries and the complexity of pure Nash equilibrium, 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, On the complexity of 2D discrete fixed point problem, New algorithms for approximate Nash equilibria in bimatrix games, Nash equilibria in all-optical networks, Computer science and decision theory, Introduction to the special issue on learning and computational game theory, ReGale: some memorable results, Deterministic calibration and Nash equilibrium, The Computational Complexity of Trembling Hand Perfection and Other Equilibrium Refinements, Noncooperative cost spanning tree games with budget restrictions, Decision Problems for Nash Equilibria in Stochastic Games
