Equilibria, fixed points, and complexity classes
From MaRDI portal
Publication:458480
DOI10.1016/j.cosrev.2009.03.004zbMath1302.68143OpenAlexW2031237501WikidataQ29040396 ScholiaQ29040396MaRDI QIDQ458480
Publication date: 7 October 2014
Published in: Computer Science Review (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2008/1311/
Analysis of algorithms and problem complexity (68Q25) Noncooperative games (91A10) 2-person games (91A05) (n)-person games, (n>2) (91A06) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
On the Complexity of Equilibrium Computation in First-Price Auctions, Positive solutions of a nonlinear algebraic system with sign-changing coefficient matrix, On the complexity of core, kernel, and bargaining set, Intermediate value theorem for simplices for simplicial approximation of fixed points and zeros, Existence of positive solutions for a class of nonlinear algebraic systems, On the Complexity of Local Search in Unconstrained Quadratic Binary Optimization, The intermediate value theorem and decision-making in psychology and economics: an expositional consolidation
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
- Exponential lower bounds for finding Brouwer fixed points
- The complexity of equilibria: Hardness results for economies via a correspondence with games
- Optimal solution of nonlinear equations
- How easy is local search?
- Positional strategies for mean payoff games
- On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
- The complexity of stochastic games
- Nash and correlated equilibria: Some complexity considerations
- A problem that is easier to solve on the unit-cost algebraic RAM
- The Euclidean traveling salesman problem is NP-complete
- Non-computability of competitive equilibrium
- On the complexity of the parity argument and other inefficient proofs of existence
- The complexity of mean payoff games on graphs
- Handbook of game theory with economic applications. Vol. 3
- Nash and Walras equilibrium via Brouwer
- Excess demand functions
- Random walks with ``back buttons
- Computational complexity of fixed points and intersection points
- A class of games possessing pure-strategy Nash equilibria
- Non-cooperative games
- The complexity of computing a Nash equilibrium
- On the Complexity of Nash Equilibria and Other Fixed Points
- Simple Local Search Problems that are Hard to Solve
- Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations
- The complexity of pure Nash equilibria
- On algorithms for discrete and approximate brouwer fixed points
- Introduction to Matrix Analytic Methods in Stochastic Modeling
- The NP-completeness column
- Branching Processes
- Equilibrium Points of Bimatrix Games
- Neural networks and physical systems with emergent collective computational abilities.
- Efficient Algorithms for Constant Well Supported Approximate Equilibria in Bimatrix Games
- Algorithmic Game Theory
- Efficient Qualitative Analysis of Classes of Recursive Markov Decision Processes and Simple Stochastic Games
- Approximate Equilibria for Strategic Two Person Games
- Hard-to-Solve Bimatrix Games
- The Approximation of Fixed Points of a Continuous Mapping
- Automata, Languages and Programming
- Stochastic Games
- Existence of an Equilibrium for a Competitive Economy
- Recursive Concurrent Stochastic Games
- Branching processes in biology
