Nash and correlated equilibria: Some complexity considerations
From MaRDI portal
Publication:1191824
DOI10.1016/0899-8256(89)90006-7zbMath0755.90093OpenAlexW2292587149MaRDI QIDQ1191824
Publication date: 27 September 1992
Published in: Games and Economic Behavior (Search for Journal in Brave)
Full work available at URL: http://www.kellogg.northwestern.edu/research/math/papers/777.pdf
Noncooperative games (91A10) Abstract computational complexity for mathematical programming problems (90C60)
Related Items (88)
How Do You Like Your Equilibrium Selection Problems? Hard, or Very Hard? ⋮ 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 ⋮ The structure and complexity of Nash equilibria for a selfish routing game ⋮ Settling Some Open Problems on 2-Player Symmetric Nash Equilibria ⋮ Simulating cardinal preferences in Boolean games: a proof technique ⋮ Graded modalities in strategy logic ⋮ Homotopy methods to compute equilibria in game theory ⋮ Computing equilibria: a computational complexity perspective ⋮ Enumeration of Nash equilibria for two-player games ⋮ Automatic verification of concurrent stochastic systems ⋮ Selection of a correlated equilibrium in Markov stopping games ⋮ AWESOME: a general multiagent learning algorithm that converges in self-play and learns a best response against stationary opponents ⋮ The complexity of decision problems about equilibria in two-player Boolean games ⋮ The complexity of computational problems about Nash equilibria in symmetric win-lose games ⋮ Bottom-up design of strategic options as finite automata ⋮ The Exact Computational Complexity of Evolutionarily Stable Strategies ⋮ Parameterized complexity of sparse linear complementarity problems ⋮ Complexity of rational and irrational Nash equilibria ⋮ A sequential Stackelberg game for dynamic inspection problems ⋮ Persuasion and dynamic communication ⋮ A note on anti-Nash equilibrium for bimatrix game ⋮ A global optimization algorithm for solving a four-person game ⋮ Revealed Preference Tests of Collectively Rational Consumption Behavior: Formulations and Algorithms ⋮ Computing Equilibria with Partial Commitment ⋮ Inapproximability Results for Approximate Nash Equilibria ⋮ The computational complexity of rationalizing boundedly rational choice behavior ⋮ Correlated equilibria in continuous games: characterization and computation ⋮ On mutual concavity and strategically-zero-sum bimatrix games ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Parameterized two-player Nash equilibrium ⋮ Correlated Equilibria in Wireless Power Control Games ⋮ Speculative and hedging interaction model in oil and U.S. dollar markets -- phase transition ⋮ Equilibria, fixed points, and complexity classes ⋮ Nash equilibria: complexity, symmetries, and approximation ⋮ The computational complexity of evolutionarily stable strategies ⋮ New complexity results about Nash equilibria ⋮ Simple search methods for finding a Nash equilibrium ⋮ A FPTAS for computing a symmetric leontief competitive economy equilibrium ⋮ 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 ⋮ Correlated Equilibria and Communication in Games ⋮ Pairwise-Interaction Games ⋮ The graph of Prisoners' Dilemma supergame payoffs as a function of the discount factor ⋮ The complexity of two-person zero-sum games in extensive form ⋮ On Stackelberg mixed strategies ⋮ On the complexity of deciding bimatrix games similarity ⋮ The complexity of computing a (quasi-)perfect equilibrium for an \(n\)-player extensive form game ⋮ The complexity of equilibria: Hardness results for economies via a correspondence with games ⋮ The complexity of \((\mathsf{E}+\mathsf{Var})\)-equilibria, \(\mathsf{ESR}\)-equilibria, and \(\mathsf{SuperE}\)-equilibria for 2-players games with few cost values ⋮ The real computational complexity of minmax value and equilibrium refinements in multi-player games ⋮ Generalized correlated equilibrium for two-person games in extensive form with perfect information ⋮ Asymptotic expected number of Nash equilibria of two-player normal form games ⋮ Well supported approximate equilibria in bimatrix games ⋮ Simple complexity from imitation games ⋮ Computer science and decision theory ⋮ Unnamed Item ⋮ 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 ⋮ The myth of the folk theorem ⋮ Approximating the existential theory of the reals ⋮ Approximate Equilibria for Strategic Two Person Games ⋮ 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 ⋮ Commitment games ⋮ Reasoning about temporal properties of rational play ⋮ Perspectives on multiagent learning ⋮ An interior-point path-following algorithm for computing a Leontief economy equilibrium ⋮ Perfect communication equilibria in repeated games with imperfect monitoring ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg ⋮ Fast Algorithms for Rank-1 Bimatrix 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 in additive hedonic games ⋮ Bounded rationality in learning, perception, decision-making, and stochastic games ⋮ Correlated Equilibria and Mean Field Games: A Simple Model ⋮ On total functions, existence theorems and computational complexity ⋮ Computational complexity of multi-player evolutionarily stable strategies ⋮ Game Theory Explorer: software for the applied game theorist
Cites Work
This page was built for publication: Nash and correlated equilibria: Some complexity considerations
