The Complexity of Computing a Nash Equilibrium
From MaRDI portal
Publication:5189544
DOI10.1137/070699652zbMath1185.91019DBLPjournals/siamcomp/DaskalakisGP09OpenAlexW2002373723WikidataQ30053762 ScholiaQ30053762MaRDI QIDQ5189544
Paul W. Goldberg, Constantinos Daskalakis, Christos H. Papadimitriou
Publication date: 17 March 2010
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.152.7003
Noncooperative games (91A10) 2-person games (91A05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (only showing first 100 items - show all)
Inapproximability of Nash Equilibrium ⋮ On the Complexity of Equilibrium Computation in First-Price Auctions ⋮ TFNP: An Update ⋮ Consensus-Halving: Does It Ever Get Easier? ⋮ The Journey from NP to TFNP Hardness ⋮ Constant Rank Two-Player Games are PPAD-hard ⋮ A Glimpse at Paul G. Spirakis ⋮ Weighted Boolean Formula Games ⋮ The Computational Complexity of Finding a Mixed Berge Equilibrium for a k-Person Noncooperative Game in Normal Form ⋮ Using Neural Networks for a Universal Framework for Agent-based Models ⋮ Approximating Nash Equilibria and Dense Subgraphs via an Approximate Version of Carathéodory's Theorem ⋮ Persuasion and dynamic communication ⋮ Sion’s Minimax Theorem in Geodesic Metric Spaces and a Riemannian Extragradient Algorithm ⋮ SNARGs and PPAD hardness from the decisional Diffie-Hellman assumption ⋮ Evolution of Mixed Strategies in Monotone Games ⋮ Public goods games in directed networks ⋮ Reasoning about causality in games ⋮ Automated equilibrium analysis of \(2\times 2\times 2\) games ⋮ From Duels to Battlefields: Computing Equilibria of Blotto and Other Games ⋮ Multiple oracle algorithm to solve continuous games ⋮ Learning Stationary Nash Equilibrium Policies in \(n\)-Player Stochastic Games with Independent Chains ⋮ A Metaheuristic Approach to Compute Pure Nash Equilibria ⋮ Provably efficient reinforcement learning in decentralized general-sum Markov games ⋮ Simultaneous contests with equal sharing allocation of prizes: computational complexity and price of anarchy ⋮ PPAD-complete pure approximate Nash equilibria in Lipschitz games ⋮ PPAD is as hard as LWE and iterated squaring ⋮ On parameterized complexity of binary networked public goods game ⋮ Unnamed Item ⋮ On Imperfect Recall in Multi-Agent Influence Diagrams ⋮ Sperner’s Colorings and Optimal Partitioning of the Simplex ⋮ Network Essence: PageRank Completion and Centrality-Conforming Markov Chains ⋮ Unnamed Item ⋮ Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds ⋮ On Sparse Discretization for Graphical Games ⋮ Towards a Unified Complexity Theory of Total Functions ⋮ The classes PPA-\(k\): existence from arguments modulo \(k\) ⋮ Amortized Analysis of Asynchronous Price Dynamics ⋮ The real computational complexity of minmax value and equilibrium refinements in multi-player games ⋮ The classes PPA-\(k\): existence from arguments modulo \(k\) ⋮ From Minicrypt to Obfustopia via Private-Key Functional Encryption ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Can PPAD hardness be based on standard cryptographic assumptions? ⋮ On the computational complexity of decision problems about multi-player Nash equilibria ⋮ Substitution with Satiation: A New Class of Utility Functions and a Complementary Pivot Algorithm ⋮ Unnamed Item ⋮ On the complexity of stable fractional hypergraph matching ⋮ Unique End of Potential Line ⋮ The Hairy Ball Problem is PPAD-Complete. ⋮ Optimal Off-line Experimentation for Games ⋮ Fast Algorithms for Rank-1 Bimatrix Games ⋮ Semidefinite Programming and Nash Equilibria in Bimatrix Games ⋮ Nash Equilibria in Certain Two-Choice Multi-Player Games Played on the Ladder Graph ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich ⋮ Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria ⋮ Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria ⋮ Consensus Halving for Sets of Items ⋮ Pareto-optimal Algorithms for Scheduling Games on Parallel-batching Machines with Activation Cost ⋮ Pure Nash Equilibria and Best-Response Dynamics in Random Games ⋮ Projections and functions of Nash equilibria ⋮ A mixed cooperative dual to the Nash equilibrium ⋮ A novel game theoretic approach for modeling competitive information diffusion in social networks with heterogeneous nodes ⋮ How Do You Like Your Equilibrium Selection Problems? Hard, or Very Hard? ⋮ On Nash-Equilibria of Approximation-Stable Games ⋮ A Direct Reduction from k-Player to 2-Player Approximate Nash Equilibrium ⋮ Buying optimal payoffs in bi-matrix games ⋮ ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria ⋮ Advances in dynamic traffic assignment: TAC. A new relationship between Wardrop's user equilibrium and Nash equilibrium ⋮ Settling Some Open Problems on 2-Player Symmetric Nash Equilibria ⋮ Approximating Nash Equilibria in Tree Polymatrix Games ⋮ An application of optimization theory to the study of equilibria for games: a survey ⋮ A Quantum Protocol for Sampling Correlated Equilibria Unconditionally and without a Mediator ⋮ The computational complexity of iterated elimination of dominated strategies ⋮ Equilibrium computation in resource allocation games ⋮ Query Complexity of Approximate Equilibria in Anonymous Games ⋮ Approximate well-supported Nash equilibria below two-thirds ⋮ Communication complexity of approximate Nash equilibria ⋮ Evolutionary game theory: a renaissance ⋮ On the performance of mildly greedy players in cut games ⋮ Existence and computation of Berge equilibrium and of two refinements ⋮ Query complexity of approximate equilibria in anonymous games ⋮ The complexity of computational problems about Nash equilibria in symmetric win-lose games ⋮ Mixing time and stationary expected social welfare of logit dynamics ⋮ The Exact Computational Complexity of Evolutionarily Stable Strategies ⋮ From minicrypt to obfustopia via private-key functional encryption ⋮ Belief-invariant and quantum equilibria in games of incomplete information ⋮ On the approximation performance of fictitious play in finite games ⋮ Complexity of rational and irrational Nash equilibria ⋮ On tightness of the Tsaknakis-Spirakis algorithm for approximate Nash equilibrium ⋮ Game theory on the blockchain: a model for games with smart contracts ⋮ Economic models for cloud service markets: pricing and capacity planning ⋮ A note on anti-Nash equilibrium for bimatrix game ⋮ On Pure Nash Equilibria in Stochastic Games ⋮ Contests with dominant strategies ⋮ The communication complexity of graphical games on grid graphs ⋮ Learning convex partitions and computing game-theoretic equilibria from best response queries ⋮ Computation of equilibrium values in the Baron and Ferejohn bargaining model
This page was built for publication: The Complexity of Computing a Nash Equilibrium
