The Complexity of Computing a Nash Equilibrium
From MaRDI portal
Publication:5189544
DOI10.1137/070699652zbMath1185.91019WikidataQ30053762 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
91A10: Noncooperative games
91A05: 2-person games
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Projections and functions of Nash equilibria, A mixed cooperative dual to the Nash equilibrium, Advances in dynamic traffic assignment: TAC. A new relationship between Wardrop's user equilibrium and Nash equilibrium, An application of optimization theory to the study of equilibria for games: a survey, The computational complexity of iterated elimination of dominated strategies, Approximate well-supported Nash equilibria below two-thirds, On the performance of mildly greedy players in cut games, Mixing time and stationary expected social welfare of logit dynamics, On the approximation performance of fictitious play in finite games, Economic models for cloud service markets: pricing and capacity planning, On mutual concavity and strategically-zero-sum bimatrix games, On perfect Nash equilibria of polymatrix games, Computing approximate Nash equilibria in polymatrix games, On Stackelberg mixed strategies, The computational complexity of weak saddles, Semidefinite programming for min-max problems and games, Distributed methods for computing approximate equilibria, Safe navigation in adversarial environments, Interdependent defense games with applications to internet security at the level of autonomous systems, Computation of equilibrium values in the Baron and Ferejohn bargaining model, Equilibria in a class of aggregative location games, A novel game theoretic approach for modeling competitive information diffusion in social networks with heterogeneous nodes, Buying optimal payoffs in bi-matrix games, Evolutionary game theory: a renaissance, Complexity of rational and irrational Nash equilibria, Probability, minimax approximation, and Nash-equilibrium. Estimating the parameter of a biased coin, Reductions in \textbf{PPP}, Equilibrium paths in discounted supergames, Towards a unified complexity theory of total functions, Inapproximability results for constrained approximate Nash equilibria, Abstracting Nash equilibria of supermodular games, Analytical complexity and errors of solving control problems for organizational and technical systems, Dynamics in network interaction games, The complexity of computing a (quasi-)perfect equilibrium for an \(n\)-player extensive form game, The complexity of \((\mathsf{E}+\mathsf{Var})\)-equilibria, \(\mathsf{ESR}\)-equilibria, and \(\mathsf{SuperE}\)-equilibria for 2-players games with few cost values, Lipschitz continuity and approximate equilibria, Zero-sum polymatrix games with link uncertainty: a Dempster-Shafer theory solution, The complexity of the parity argument with potential, Algorithm for computing approximate Nash equilibrium in continuous games with application to continuous blotto, Continuous verifiable delay functions, The complexity of finding fair independent sets in cycles, Two's company, three's a crowd: consensus-halving for a constant number of agents, Defense coordination in security games: equilibrium analysis and mechanism design, Multi-agent reinforcement learning: a selective overview of theories and algorithms, Bounded rationality in differential games: a reinforcement learning-based approach, Bounded rationality in learning, perception, decision-making, and stochastic games, Discrete versions of the KKM lemma and their PPAD-completeness, Characterising the intersection of QMA and coQMA, Fiat-Shamir for repeated squaring with applications to PPAD-hardness and VDFs, Delegation with updatable unambiguous proofs and PPAD-hardness, Equilibrium computation in resource allocation games, Communication complexity of approximate Nash equilibria, From minicrypt to obfustopia via private-key functional encryption, The communication complexity of graphical games on grid graphs, Learning convex partitions and computing game-theoretic equilibria from best response queries, Unique end of potential line, Tatonnement beyond gross substitutes? Gradient descent to the rescue, Behavioural strategies in weighted Boolean games, The Hairy Ball problem is PPAD-complete, Approximate Nash equilibria in anonymous games, Faster algorithms for extensive-form game solving via improved smoothing functions, Oriented Euler complexes and signed perfect matchings, Pure Nash equilibria in graphical games and treewidth, Polynomial-time computation of exact correlated equilibrium in compact games, Existence and computation of Berge equilibrium and of two refinements, Query complexity of approximate equilibria in anonymous games, Recursive stochastic games with positive rewards, Computational aspects of uncertainty profiles and angel-daemon games, On the communication complexity of approximate Nash equilibria, On influence, stable behavior, and the most influential individuals in networks: a game-theoretic approach, The complexity of computational problems about Nash equilibria in symmetric win-lose games, Belief-invariant and quantum equilibria in games of incomplete information, On tightness of the Tsaknakis-Spirakis algorithm for approximate Nash equilibrium, Game theory on the blockchain: a model for games with smart contracts, A note on anti-Nash equilibrium for bimatrix game, Contests with dominant strategies, Noisy three-player dilemma game: robustness of the quantum advantage, Total functions in QMA, Market power and efficiency analysis in bi-level energy transmission market, Lipschitz Continuity and Approximate Equilibria, Complexity and Optimality of the Best Response Algorithm in Random Potential Games, The Exact Computational Complexity of Evolutionarily Stable Strategies, On Pure Nash Equilibria in Stochastic Games, Computing Equilibria with Partial Commitment, Distributed Methods for Computing Approximate Equilibria, Inapproximability Results for Approximate Nash Equilibria, Computer-Aided Verification for Mechanism Design, Some Tractable Win-Lose Games, Automatizability and Simple Stochastic Games, The Complexity of Nash Equilibria in Limit-Average Games, Modeling Internet Security Investments: Tackling Topological Information Uncertainty, 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, Solving for Best Responses and Equilibria in Extensive-Form Games with Reinforcement Learning Methods, ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria, Settling Some Open Problems on 2-Player Symmetric Nash Equilibria, Approximating Nash Equilibria in Tree Polymatrix Games, A Quantum Protocol for Sampling Correlated Equilibria Unconditionally and without a Mediator, Query Complexity of Approximate Equilibria in Anonymous Games, Unnamed Item, Unnamed Item, Inapproximability of Nash Equilibrium, Constant Rank Two-Player Games are PPAD-hard, The Computational Complexity of Finding a Mixed Berge Equilibrium for a k-Person Noncooperative Game in Normal Form, Approximating Nash Equilibria and Dense Subgraphs via an Approximate Version of Carathéodory's Theorem, Persuasion and dynamic communication, Sperner’s Colorings and Optimal Partitioning of the Simplex, Network Essence: PageRank Completion and Centrality-Conforming Markov Chains, The Journey from NP to TFNP Hardness, Unnamed Item, Unnamed Item, Unnamed Item, 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, Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria, Pareto-optimal Algorithms for Scheduling Games on Parallel-batching Machines with Activation Cost, Pure Nash Equilibria and Best-Response Dynamics in Random Games, Using Neural Networks for a Universal Framework for Agent-based Models, From Duels to Battlefields: Computing Equilibria of Blotto and Other Games, A Metaheuristic Approach to Compute Pure Nash Equilibria, 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, Amortized Analysis of Asynchronous Price Dynamics, 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., TFNP: An Update, Unnamed Item, Unnamed Item, The classes PPA-\(k\): existence from arguments modulo \(k\), 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, Can PPAD hardness be based on standard cryptographic assumptions?, On the computational complexity of decision problems about multi-player Nash equilibria, The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich, Consensus Halving for Sets of Items, On the Complexity of Equilibrium Computation in First-Price Auctions, Consensus-Halving: Does It Ever Get Easier?, Sion’s Minimax Theorem in Geodesic Metric Spaces and a Riemannian Extragradient Algorithm, 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, Multiple oracle algorithm to solve continuous games, 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, A Glimpse at Paul G. Spirakis, Weighted Boolean Formula Games
