Equilibria, fixed points, and complexity classes
type: Item
instance of: scholarly article
title: Equilibria, fixed points, and complexity classes
zbMATH Open document ID: 1302.68143
author: Mihalis Yannakakis
published in: Computer Science Review
publication date: 2014-10-07T00:00:00Z
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2008/1311/
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 91A05
Mathematics Subject Classification ID: 91A06
Mathematics Subject Classification ID: 91A10
Mathematics Subject Classification ID: 68-02
zbMATH DE Number: 6352108
zbMATH Keywords: Nash equilibria
zbMATH Keywords: complexity classes
MaRDI profile type: Publication
OpenAlex ID: W2031237501
cites work: Neural networks and physical systems with emergent collective computational abilities.
cites work: How easy is local search?
cites work: Q4339078
cites work: Simple Local Search Problems that are Hard to Solve
cites work: Non-cooperative games
cites work: Q3524716
cites work: A class of games possessing pure-strategy Nash equilibria
cites work: The complexity of pure Nash equilibria
cites work: Q3549719
cites work: The complexity of stochastic games
cites work: Q4287357
cites work: Q3975934
cites work: Positional strategies for mean payoff games
cites work: The complexity of mean payoff games on graphs
cites work: Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
cites work: Q4070959
cites work: Existence of an Equilibrium for a Competitive Economy
cites work: Nash and Walras equilibrium via Brouwer
cites work: Excess demand functions
cites work: Stochastic Games
cites work: Q4382287
cites work: Q4437142
cites work: Q5727090
cites work: Branching Processes
cites work: Branching processes in biology
cites work: Q4939994
cites work: Introduction to Matrix Analytic Methods in Stochastic Modeling
cites work: Random walks with ``back buttons''
cites work: Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations
cites work: Efficient Qualitative Analysis of Classes of Recursive Markov Decision Processes and Simple Stochastic Games
cites work: Recursive Concurrent Stochastic Games
cites work: Automata, Languages and Programming
cites work: On the Complexity of Nash Equilibria and Other Fixed Points
cites work: The Approximation of Fixed Points of a Continuous Mapping
cites work: Exponential lower bounds for finding Brouwer fixed points
cites work: Optimal solution of nonlinear equations
cites work: Computational complexity of fixed points and intersection points
cites work: Non-computability of competitive equilibrium
cites work: Theory of games and economic behavior.
cites work: Nash and correlated equilibria: Some complexity considerations
cites work: Equilibrium Points of Bimatrix Games
cites work: Hard-to-Solve Bimatrix Games
cites work: On the complexity of the parity argument and other inefficient proofs of existence
cites work: The complexity of computing a Nash equilibrium
cites work: Q2934593
cites work: Approximate Equilibria for Strategic Two Person Games
cites work: The complexity of equilibria: Hardness results for economies via a correspondence with games
cites work: Q4155835
cites work: A problem that is easier to solve on the unit-cost algebraic RAM
cites work: Q4385524
cites work: On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
cites work: Handbook of game theory with economic applications. Vol. 3
cites work: On algorithms for discrete and approximate brouwer fixed points
cites work: The NP-completeness column
cites work: Q5802534
cites work: Efficient Algorithms for Constant Well Supported Approximate Equilibria in Bimatrix Games
cites work: Algorithmic Game Theory
cites work: The Euclidean traveling salesman problem is NP-complete
Wikidata QID: Q29040396
DOI: 10.1016/J.COSREV.2009.03.004