New complexity results about Nash equilibria

DOI10.1016/J.GEB.2008.02.015zbMATH Open1142.91365OpenAlexW2013815105MaRDI QIDQ932810FDOQ932810

Authors: Vincent Conitzer, Tuomas Sandholm 

Publication date: 11 July 2008

Published in: Games and Economic Behavior (Search for Journal in Brave)

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

Recommendations

• scientific article; zbMATH DE number 2243403
• Nash and correlated equilibria: Some complexity considerations
• The complexity of computing a Nash equilibrium
• Inapproximability of NP-complete variants of Nash equilibrium
• Nash equilibria: complexity, symmetries, and approximation

Mathematics Subject Classification ID

Decision theory for games (91A35) Utility theory for games (91A30)

Cites Work

• Lossless abstraction of imperfect information games
• Equilibrium points in n -person games
• Stochastic Games
• Generic \(4\times 4\) two person games have at most 15 Nash equilibria
• Game theory
• The Complexity of Markov Decision Processes
• The complexity of computing the permanent
• Games with Incomplete Information Played by “Bayesian” Players, I–III Part I. The Basic Model
• The complexity of theorem-proving procedures
• Title not available (Why is that?)
• Title not available (Why is that?)
• Multi-agent influence diagrams for representing and solving games.
• Efficient computation of equilibria for extensive two-person games
• Title not available (Why is that?)
• Title not available (Why is that?)
• Equilibrium Points of Bimatrix Games
• Noncooperative Stochastic Games
• GO Is Polynomial-Space Hard
• Algorithms, games, and the internet
• The Complexity of Eliminating Dominated Strategies
• The Expected Number of Nash Equilibria of a Normal Form Game
• The complexity of computing a Nash equilibrium
• The complexity of two-person zero-sum games in extensive form
• On players with a bounded number of states
• The complexity of computing a best response automaton in repeated games with mixed strategies
• Non-computable strategies and discounted repeated games
• Nash and correlated equilibria: Some complexity considerations
• Efficient computation of behavior strategies
• Title not available (Why is that?)
• Hard-to-Solve Bimatrix Games
• Simple search methods for finding a Nash equilibrium
• Computing sequential equilibria for two-player games
• Computing correlated equilibria in multi-player games
• The Computational Complexity of Nash Equilibria in Concisely Represented Games
• Computing Normal Form Perfect Equilibria for Extensive Two-Person Games
• Computable strategies for repeated prisoner's dilemma
• Algorithms for closed under rational behavior (CURB) sets

Cited In (87)

• Malicious Bayesian Congestion Games
• The computational complexity of trembling hand perfection and other equilibrium refinements
• Bilevel programming methods for computing single-leader-multi-follower equilibria in normal-form and polymatrix games
• The complexity of \((\mathsf{E}+\mathsf{Var})\)-equilibria, \(\mathsf{ESR}\)-equilibria, and \(\mathsf{SuperE}\)-equilibria for 2-players games with few cost values
• Substitution with satiation: a new class of utility functions and a complementary pivot algorithm
• The computational complexity of finding a mixed Berge equilibrium for a \(k\)-person noncooperative game in normal form
• Semidefinite Programming and Nash Equilibria in Bimatrix Games
• A Note on Game Theory and Verification
• Optimal Off-line Experimentation for Games
• How do you like your equilibrium selection problems? Hard, or very hard?
• Settling some open problems on 2-player symmetric Nash equilibria
• Computing Equilibria with Partial Commitment
• ETR-completeness for decision versions of multi-player (symmetric) Nash equilibria
• On the convergence of multicast games in directed networks
• Approximating the existential theory of the reals
• Game theory on attack graph for cyber deception
• A sequential Stackelberg game for dynamic inspection problems
• Single parameter FPT-algorithms for non-trivial games
• Directed graphical structure, Nash equilibrium, and potential games
• The real computational complexity of minmax value and equilibrium refinements in multi-player games
• Computational complexity of decision problems about Nash equilibria in win-lose multi-player games
• Approximating the existential theory of the reals
• Strong Nash equilibria and mixed strategies
• On the complexity of deciding bimatrix games similarity
• Some results of Maria Serna on strategic games: complexity of equilibria and models
• A Logic for Reasoning about Rational Agents
• On the Complexity of Equilibrium Computation in First-Price Auctions
• Constructive proof of the existence of Nash equilibrium in a finite strategic game with sequentially locally nonconstant payoff functions
• Title not available (Why is that?)
• Strategic Characterization of the Index of an Equilibrium
• On the complexity of constrained Nash equilibria in graphical games
• Belief and truth in hypothesised behaviours
• AWESOME: a general multiagent learning algorithm that converges in self-play and learns a best response against stationary opponents
• Nash equilibria in discrete routing games with convex latency functions
• Nash equilibria: complexity, symmetries, and approximation
• The complexity of equilibria for risk-modeling valuations
• Weighted Boolean formula games
• Action-graph games
• Fundamentals of Computation Theory
• Inapproximability results for approximate Nash equilibria
• The Complexity of Nash Equilibria in Limit-Average Games
• An abstraction-refinement methodology for reasoning about network games
• The complexity of uniform Nash equilibria and related regular subgraph problems
• Good neighbors are hard to find: Computational complexity of network formation
• Interdependent defense games with applications to internet security at the level of autonomous systems
• Reducibility among equilibrium problems
• Persuasion and dynamic communication
• Complexity of rational and irrational Nash equilibria
• Game Theory Explorer: software for the applied game theorist
• Nash and correlated equilibria: Some complexity considerations
• Infection and immunization: a new class of evolutionary game dynamics
• Computing approximate Nash equilibria in polymatrix games
• Inapproximability results for constrained approximate Nash equilibria
• When the players are not expectation maximizers
• Imitation games and computation
• Perspectives on multiagent learning
• Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium
• Simple search methods for finding a Nash equilibrium
• On the computational complexity of decision problems about multi-player Nash equilibria
• Inapproximability of NP-Complete Variants of Nash Equilibrium
• On the complexity of market equilibria with maximum social welfare
• Alternating minima and maxima, Nash equilibria and bounded arithmetic
• The computational complexity of evolutionarily stable strategies
• Complexity of rational and irrational Nash equilibria
• Simulating cardinal preferences in Boolean games: a proof technique
• Well supported approximate equilibria in bimatrix games
• Reasoning about temporal properties of rational play
• Complexity of Verifying Game Equilibria
• Designing fast converging cost sharing methods for multicast transmissions
• $\mathcal{NP}$ -Hardness of Pure Nash Equilibrium in Scheduling and Connection Games
• The computational complexity of rationalizing boundedly rational choice behavior
• Revealed Preference Tests of Collectively Rational Consumption Behavior: Formulations and Algorithms
• Computing the strong Nash equilibrium for Markov chains games
• Pairwise-interaction games
• Computation of sparse and dense equilibrium strategies of evolutionary games
• The complexity of decision problems about Nash equilibria in win-lose games
• Simple complexity from imitation games
• On the Hardness and Existence of Quasi-Strict Equilibria
• Computing the strong \(L_p\)-Nash equilibrium for Markov chains games: convergence and uniqueness
• On pure Nash equilibria in stochastic games
• On the computational complexity of Nash equilibria for \((0,1)\) bimatrix games
• Computing equilibria: a computational complexity perspective
• Graded modalities in strategy logic
• On Stackelberg mixed strategies
• Conditional value-at-risk: structure and complexity of equilibria
• Computational complexity of multi-player evolutionarily stable strategies
• The complexity of computational problems about Nash equilibria in symmetric win-lose games

Uses Software

• GameShrink

This page was built for publication: New complexity results about Nash equilibria

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