Computing equilibria: a computational complexity perspective

DOI10.1007/s00199-009-0448-yzbMath1192.91035OpenAlexW2070377170MaRDI QIDQ847807

Tim Roughgarden

Publication date: 19 February 2010

Published in: Economic Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00199-009-0448-y

zbMATH Keywords

computational complexitygame theoryNP-completenessNP-hardnessequilibrium computation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Other game-theoretic models (91A40)

Related Items

A Direct Reduction from k-Player to 2-Player Approximate Nash Equilibrium ⋮ Steepest ascent can be exponential in bounded treewidth problems ⋮ Complexity of stability in trading networks ⋮ Computation of equilibrium values in the Baron and Ferejohn bargaining model ⋮ The Weighted Set Covering Game: A Vaccine Pricing Model for Pediatric Immunization ⋮ Unnamed Item ⋮ Pareto optimality in coalition formation ⋮ Computation of the random arrival rule for bankruptcy problems ⋮ Semidefinite programming for min-max problems and games ⋮ A new algorithm to solve the generalized Nash equilibrium problem ⋮ Properties and applications of dual reduction ⋮ The truth behind the myth of the folk theorem ⋮ Applications of Algebra for Some Game Theoretic Problems ⋮ Coordination problems on networks revisited: statics and dynamics

Uses Software

• Concorde
• GAMUT

Cites Work

• Computational Complexity
• Computing correlated equilibria in multi-player games
• College Admissions and the Stability of Marriage
• Potential games with continuous player sets
• 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
• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new polynomial-time algorithm for linear programming
• On total functions, existence theorems and computational complexity
• Games of fixed rank: a hierarchy of bimatrix games
• Computing a quasi-perfect equilibrium of a two-player game
• Exponential lower bounds for finding Brouwer fixed points
• The computational complexity of evolutionarily stable strategies
• New complexity results about Nash equilibria
• Simple search methods for finding a Nash equilibrium
• New algorithms for approximate Nash equilibria in bimatrix games
• The complexity of computing best-response automata in repeated games
• How easy is local search?
• On players with a bounded number of states
• Nash and correlated equilibria: Some complexity considerations
• The complexity of two-person zero-sum games in extensive form
• Subjectivity and correlation in randomized strategies
• The relative complexity of NP search problems
• On the complexity of the parity argument and other inefficient proofs of existence
• On the role of computation in economic theory
• Calibrated learning and correlated equilibrium
• Representations and solutions for game-theoretic problems
• Computational economics and economic theory: Substitutes or complements?
• On the NP-completeness of finding an optimal strategy in games with common payoffs
• Potential games
• General equilibrium models and homotopy methods
• Simple complexity from imitation games
• A class of games possessing pure-strategy Nash equilibria
• Non-cooperative games
• Finitely Repeated Games with Finite Automata
• On complexity as bounded rationality (extended abstract)
• Reducibility among equilibrium problems
• The complexity of computing a Nash equilibrium
• The Computational Complexity of Nash Equilibria in Concisely Represented Games
• How Hard Is It to Approximate the Best Nash Equilibrium?
• On the Complexity of Nash Equilibria and Other Fixed Points
• The Complexity of Eliminating Dominated Strategies
• On the Complexity of Pure-Strategy Nash Equilibria in Congestion and Local-Effect Games
• Extensive-Form Correlated Equilibrium: Definition and Computational Complexity
• Simple Local Search Problems that are Hard to Solve
• Linear Automaton Transformations
• On the impact of combinatorial structure on congestion games
• Settling the complexity of computing two-player Nash equilibria
• Average-Case Complexity
• An Optimization Approach for Approximate Nash Equilibria
• The complexity of pure Nash equilibria
• Finding Equilibria in Games of No Chance
• Multiagent Systems
• The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games
• On the Complexity of Numerical Analysis
• Orientation in Complementary Pivot Algorithms
• Totally Balanced Games and Games of Flow
• A method for obtaining digital signatures and public-key cryptosystems
• On the Complexity of Cooperative Solution Concepts
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• A Simple Adaptive Procedure Leading to Correlated Equilibrium
• The NP-completeness column
• Equilibrium Points of Bimatrix Games
• On the Computational Complexity of Algorithms
• Paths, Trees, and Flowers
• Adaptive Heuristics
• Nash equilibria in random games
• Algorithms – ESA 2005
• Hard-to-Solve Bimatrix Games
• The Approximation of Fixed Points of a Continuous Mapping
• On the Sperner lemma
• The complexity of theorem-proving procedures
• On Computable Numbers, with an Application to the Entscheidungsproblem
• Equilibrium points in n -person games