Computing equilibria: a computational complexity perspective
type: Item
instance of: scholarly article
title: Computing equilibria: a computational complexity perspective
zbMATH Open document ID: 1192.91035
author: Tim Roughgarden
published in: Economic Theory
publication date: 2010-02-19T00:00:00Z
review text: With the development of information technology and computer science, we have a great possibility to solve certain hard optimization problems. Because of this there has been a tremendous growth in the field of approximation algorithms, heuristics and metaheuristics. Before using them, it is important to study computational complexity of a considered problem. This survey explains how complexity theory defines ``hard problems'' and illustrates this definition applying these concepts to several equilibrium problems from game theory. At the end, the discussion regarding implications for the choice how to solve the problem is presented.
reviewed by: Kristina Šorić
Mathematics Subject Classification ID: 91A40
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 90C60
zbMATH DE Number: 5673330
zbMATH Keywords: computational complexity
zbMATH Keywords: NP-hardness
zbMATH Keywords: NP-completeness
zbMATH Keywords: game theory
zbMATH Keywords: equilibrium computation
describes a project that uses: Concorde
describes a project that uses: GAMUT
MaRDI profile type: Publication
full work available at URL: s00199-009-0448-y
OpenAlex ID: W2070377170
cites work: Q3395977
cites work: On the impact of combinatorial structure on congestion games
cites work: On the Complexity of Numerical Analysis
cites work: Q3425132
cites work: Subjectivity and correlation in randomized strategies
cites work: Nash equilibria in random games
cites work: The relative complexity of NP search problems
cites work: COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
cites work: Q3524720
cites work: Average-Case Complexity
cites work: On the role of computation in economic theory
cites work: Q3549720
cites work: New algorithms for approximate Nash equilibria in bimatrix games
cites work: Q3373046
cites work: Q5801629
cites work: Settling the complexity of computing two-player Nash equilibria
cites work: Q2934594
cites work: On the NP-completeness of finding an optimal strategy in games with common payoffs
cites work: On the Sperner lemma
cites work: New complexity results about Nash equilibria
cites work: The complexity of theorem-proving procedures
cites work: Q3844775
cites work: The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games
cites work: The complexity of computing a Nash equilibrium
cites work: Algorithms – ESA 2005
cites work: On the Complexity of Cooperative Solution Concepts
cites work: On the Complexity of Pure-Strategy Nash Equilibria in Congestion and Local-Effect Games
cites work: General equilibrium models and homotopy methods
cites work: Paths, Trees, and Flowers
cites work: The computational complexity of evolutionarily stable strategies
cites work: On the Complexity of Nash Equilibria and Other Fixed Points
cites work: The complexity of pure Nash equilibria
cites work: Q4289278
cites work: Calibrated learning and correlated equilibrium
cites work: Q5801630
cites work: College Admissions and the Stability of Marriage
cites work: Q4198056
cites work: The complexity of computing best-response automata in repeated games
cites work: The Complexity of Eliminating Dominated Strategies
cites work: Nash and correlated equilibria: Some complexity considerations
cites work: Reducibility among equilibrium problems
cites work: Computational Complexity
cites work: Finding Equilibria in Games of No Chance
cites work: Adaptive Heuristics
cites work: Q3549631
cites work: A Simple Adaptive Procedure Leading to Correlated Equilibrium
cites work: Q5636862
cites work: On the Computational Complexity of Algorithms
cites work: How Hard Is It to Approximate the Best Nash Equilibrium?
cites work: Exponential lower bounds for finding Brouwer fixed points
cites work: Q4506483
cites work: The NP-completeness column
cites work: How easy is local search?
cites work: Computational economics and economic theory: Substitutes or complements?
cites work: Q3351186
cites work: Q4875220
cites work: Totally Balanced Games and Games of Flow

Computing equilibria: a computational complexity perspective (cites work)
cites work: Games of fixed rank: a hierarchy of bimatrix games

Computing equilibria: a computational complexity perspective (cites work)
cites work: A new polynomial-time algorithm for linear programming

Computing equilibria: a computational complexity perspective (cites work)
cites work: Q3050157

Computing equilibria: a computational complexity perspective (cites work)
cites work: Q4051879

Computing equilibria: a computational complexity perspective (cites work)
cites work: The complexity of two-person zero-sum games in extensive form

Computing equilibria: a computational complexity perspective (cites work)
cites work: Representations and solutions for game-theoretic problems

Computing equilibria: a computational complexity perspective (cites work)
cites work: Equilibrium Points of Bimatrix Games

Computing equilibria: a computational complexity perspective (cites work)
cites work: Q4071737

Computing equilibria: a computational complexity perspective (cites work)
cites work: Q4369429

Computing equilibria: a computational complexity perspective (cites work)
cites work: Simple complexity from imitation games

Computing equilibria: a computational complexity perspective (cites work)
cites work: On total functions, existence theorems and computational complexity

Computing equilibria: a computational complexity perspective (cites work)
cites work: Computing a quasi-perfect equilibrium of a two-player game

Computing equilibria: a computational complexity perspective (cites work)
cites work: Potential games

Computing equilibria: a computational complexity perspective (cites work)
cites work: Equilibrium points in n -person games

Computing equilibria: a computational complexity perspective (cites work)
cites work: Non-cooperative games

Computing equilibria: a computational complexity perspective (cites work)
cites work: Linear Automaton Transformations

Computing equilibria: a computational complexity perspective (cites work)
cites work: Finitely repeated games with finite automata

Computing equilibria: a computational complexity perspective (cites work)
cites work: On players with a bounded number of states

Computing equilibria: a computational complexity perspective (cites work)
cites work: On the complexity of the parity argument and other inefficient proofs of existence

Computing equilibria: a computational complexity perspective (cites work)
cites work: Q3221403

Computing equilibria: a computational complexity perspective (cites work)
cites work: Computing correlated equilibria in multi-player games

Computing equilibria: a computational complexity perspective (cites work)
cites work: On complexity as bounded rationality (extended abstract)

Computing equilibria: a computational complexity perspective (cites work)
cites work: Simple search methods for finding a Nash equilibrium

Computing equilibria: a computational complexity perspective (cites work)
cites work: Q3245637

Computing equilibria: a computational complexity perspective (cites work)
cites work: Q5541339

Computing equilibria: a computational complexity perspective (cites work)
cites work: A method for obtaining digital signatures and public-key cryptosystems

Computing equilibria: a computational complexity perspective (cites work)
cites work: A class of games possessing pure-strategy Nash equilibria

Computing equilibria: a computational complexity perspective (cites work)
cites work: Q5501360

Computing equilibria: a computational complexity perspective (cites work)
cites work: Potential games with continuous player sets

Computing equilibria: a computational complexity perspective (cites work)
cites work: Hard-to-Solve Bimatrix Games

Computing equilibria: a computational complexity perspective (cites work)
cites work: The Approximation of Fixed Points of a Continuous Mapping

Computing equilibria: a computational complexity perspective (cites work)
cites work: Q4070959

Computing equilibria: a computational complexity perspective (cites work)
cites work: Simple Local Search Problems that are Hard to Solve

Computing equilibria: a computational complexity perspective (cites work)
cites work: The Computational Complexity of Nash Equilibria in Concisely Represented Games

Computing equilibria: a computational complexity perspective (cites work)
cites work: Multiagent Systems

Computing equilibria: a computational complexity perspective (cites work)
cites work: Q3392273

Computing equilibria: a computational complexity perspective (cites work)
cites work: Q3549719

Computing equilibria: a computational complexity perspective (cites work)
cites work: Q3524728

Computing equilibria: a computational complexity perspective (cites work)
cites work: Orientation in Complementary Pivot Algorithms

Computing equilibria: a computational complexity perspective (cites work)
cites work: An Optimization Approach for Approximate Nash Equilibria

Computing equilibria: a computational complexity perspective (cites work)
cites work: On Computable Numbers, with an Application to the Entscheidungsproblem

Computing equilibria: a computational complexity perspective (cites work)
cites work: Q4385524

Computing equilibria: a computational complexity perspective (cites work)
cites work: Q3524714

Computing equilibria: a computational complexity perspective (cites work)
cites work: Q5474958

Computing equilibria: a computational complexity perspective (cites work)
cites work: Extensive-Form Correlated Equilibrium: Definition and Computational Complexity

Computing equilibria: a computational complexity perspective (cites work)
cites work: Q4365127

Computing equilibria: a computational complexity perspective (cites work)
cites work: Q4910705

Computing equilibria: a computational complexity perspective (DOI)
DOI: 10.1007/S00199-009-0448-Y