New complexity results about Nash equilibria

DOI10.1016/j.geb.2008.02.015zbMath1142.91365OpenAlexW2013815105MaRDI QIDQ932810

Vincent Conitzer, Tuomas W. 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

Mathematics Subject Classification ID

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

Related Items

Belief and truth in hypothesised behaviours, On the Complexity of Equilibrium Computation in First-Price Auctions, Some results of Maria Serna on strategic games: complexity of equilibria and models, When the Players Are Not Expectation Maximizers, How Do You Like Your Equilibrium Selection Problems? Hard, or Very Hard?, The complexity of equilibria for risk-modeling valuations, An abstraction-refinement methodology for reasoning about network games, Computation of sparse and dense equilibrium strategies of evolutionary games, On the complexity of constrained Nash equilibria in graphical games, ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria, Settling Some Open Problems on 2-Player Symmetric Nash Equilibria, On the convergence of multicast games in directed networks, Simulating cardinal preferences in Boolean games: a proof technique, Graded modalities in strategy logic, Computing equilibria: a computational complexity perspective, AWESOME: a general multiagent learning algorithm that converges in self-play and learns a best response against stationary opponents, Weighted Boolean Formula Games, The Computational Complexity of Finding a Mixed Berge Equilibrium for a k-Person Noncooperative Game in Normal Form, Computing the strong Nash equilibrium for Markov chains games, The complexity of computational problems about Nash equilibria in symmetric win-lose games, The Exact Computational Complexity of Evolutionarily Stable Strategies, Complexity of rational and irrational Nash equilibria, A sequential Stackelberg game for dynamic inspection problems, Persuasion and dynamic communication, On Pure Nash Equilibria in Stochastic Games, Directed graphical structure, Nash equilibrium, and potential games, Constructive proof of the existence of Nash equilibrium in a finite strategic game with sequentially locally nonconstant payoff functions, Revealed Preference Tests of Collectively Rational Consumption Behavior: Formulations and Algorithms, Action-graph games, Infection and immunization: a new class of evolutionary game dynamics, Computing Equilibria with Partial Commitment, Inapproximability Results for Approximate Nash Equilibria, The computational complexity of rationalizing boundedly rational choice behavior, Designing fast converging cost sharing methods for multicast transmissions, Nash equilibria: complexity, symmetries, and approximation, The computational complexity of evolutionarily stable strategies, Simple search methods for finding a Nash equilibrium, A Note on Game Theory and Verification, Good neighbors are hard to find: Computational complexity of network formation, The complexity of uniform Nash equilibria and related regular subgraph problems, Single Parameter FPT-Algorithms for Non-trivial Games, Pairwise-Interaction Games, Computing approximate Nash equilibria in polymatrix games, On Stackelberg mixed strategies, On the complexity of deciding bimatrix games similarity, Nash equilibria in discrete routing games with convex latency functions, The complexity of \((\mathsf{E}+\mathsf{Var})\)-equilibria, \(\mathsf{ESR}\)-equilibria, and \(\mathsf{SuperE}\)-equilibria for 2-players games with few cost values, Conditional value-at-risk: structure and complexity of equilibria, The real computational complexity of minmax value and equilibrium refinements in multi-player games, Well supported approximate equilibria in bimatrix games, Simple complexity from imitation games, Strong Nash equilibria and mixed strategies, Malicious Bayesian Congestion Games, A Logic for Reasoning about Rational Agents, Inapproximability results for constrained approximate Nash equilibria, Interdependent defense games with applications to internet security at the level of autonomous systems, Imitation games and computation, Computing the strong \(L_p\)-Nash equilibrium for Markov chains games: convergence and uniqueness, Approximating the existential theory of the reals, Approximating the existential theory of the reals, Strategic Characterization of the Index of an Equilibrium, 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, Inapproximability of NP-Complete Variants of Nash Equilibrium, Game theory on attack graph for cyber deception, The Complexity of Nash Equilibria in Limit-Average Games, Bilevel programming methods for computing single-leader-multi-follower equilibria in normal-form and polymatrix games, Reasoning about temporal properties of rational play, Perspectives on multiagent learning, Optimal Off-line Experimentation for Games, Semidefinite Programming and Nash Equilibria in Bimatrix Games, On the computational complexity of Nash equilibria for \((0,1)\) bimatrix games, On the complexity of market equilibria with maximum social welfare, Computational complexity of multi-player evolutionarily stable strategies, Game Theory Explorer: software for the applied game theorist

Uses Software

GameShrink

Cites Work