Computing equilibria: a computational complexity perspective

DOI10.1007/S00199-009-0448-YMaRDI QIDQ847807zbMATH OpenOpenAlexFDO

Authors 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 complexityequilibrium computationgame theoryNP-completenessNP-hardness

Mathematics Subject Classification ID

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

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.

Recommendations

• Recent development in computational complexity characterization of Nash equilibrium
• Complexity of pure-strategy Nash equilibria in non-cooperative games
• Nash and correlated equilibria: Some complexity considerations
• How do you like your equilibrium selection problems? Hard, or very hard?
• The complexity of computing a Nash equilibrium

Cites work

• A class of games possessing pure-strategy Nash equilibria
• A method for obtaining digital signatures and public-key cryptosystems
• A new polynomial-time algorithm for linear programming
• A Simple Adaptive Procedure Leading to Correlated Equilibrium
• Adaptive Heuristics
• Advanced mathematical economics.
• Algorithms – ESA 2005
• An optimization approach for approximate Nash equilibria
• Average-Case Complexity
• Calibrated learning and correlated equilibrium
• College Admissions and the Stability of Marriage
• Combinatorial algorithms for market equilibria
• Combinatorial auctions
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• Computational Complexity
• Computational economics and economic theory: Substitutes or complements?
• Computing a quasi-perfect equilibrium of a two-player game
• Computing correlated equilibria in multi-player games
• Computing over the reals: foundations for scientific computing.
• Convergence to approximate Nash equilibria in congestion games
• Equilibria, fixed points, and complexity classes
• Equilibrium points in n -person games
• Equilibrium Points of Bimatrix Games
• Exponential lower bounds for finding Brouwer fixed points
• Extensive-form correlated equilibrium: definition and computational complexity
• Finding Equilibria in Games of No Chance
• Finitely repeated games with finite automata
• General equilibrium models and homotopy methods
• Hard-to-Solve Bimatrix Games
• How easy is local search?
• How Hard Is It to Approximate the Best Nash Equilibrium?
• scientific article; zbMATH DE number 3644821 (Why is no real title available?)
• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 3128730 (Why is no real title available?)
• scientific article; zbMATH DE number 4202070 (Why is no real title available?)
• scientific article; zbMATH DE number 5595151 (Why is no real title available?)
• scientific article; zbMATH DE number 5604094 (Why is no real title available?)
• scientific article; zbMATH DE number 5485469 (Why is no real title available?)
• scientific article; zbMATH DE number 5485547 (Why is no real title available?)
• scientific article; zbMATH DE number 5485548 (Why is no real title available?)
• scientific article; zbMATH DE number 3177183 (Why is no real title available?)
• scientific article; zbMATH DE number 3466805 (Why is no real title available?)
• scientific article; zbMATH DE number 3487169 (Why is no real title available?)
• scientific article; zbMATH DE number 3489106 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 559220 (Why is no real title available?)
• scientific article; zbMATH DE number 1082100 (Why is no real title available?)
• scientific article; zbMATH DE number 1099369 (Why is no real title available?)
• scientific article; zbMATH DE number 1142308 (Why is no real title available?)
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• scientific article; zbMATH DE number 871945 (Why is no real title available?)
• scientific article; zbMATH DE number 6469241 (Why is no real title available?)
• scientific article; zbMATH DE number 3254905 (Why is no real title available?)
• scientific article; zbMATH DE number 3363526 (Why is no real title available?)
• scientific article; zbMATH DE number 3062452 (Why is no real title available?)
• scientific article; zbMATH DE number 3062453 (Why is no real title available?)
• Linear Automaton Transformations
• Multiagent Systems
• Nash and correlated equilibria: Some complexity considerations
• Nash equilibria in random games
• Network formation games and the potential function method
• New algorithms for approximate Nash equilibria in bimatrix games
• New complexity results about Nash equilibria
• Non-cooperative games
• On complexity as bounded rationality (extended abstract)
• On Computable Numbers, with an Application to the Entscheidungsproblem
• On players with a bounded number of states
• On the Complexity of Cooperative Solution Concepts
• On the Complexity of Nash Equilibria and Other Fixed Points
• On the Complexity of Numerical Analysis
• On the complexity of pure-strategy Nash equilibria in congestion and local-effect games
• On the complexity of the parity argument and other inefficient proofs of existence
• On the Computational Complexity of Algorithms
• On the impact of combinatorial structure on congestion games
• On the NP-completeness of finding an optimal strategy in games with common payoffs
• On the role of computation in economic theory
• On the Sperner lemma
• On total functions, existence theorems and computational complexity
• Orientation in Complementary Pivot Algorithms
• Paths, Trees, and Flowers
• Potential games
• Potential games with continuous player sets
• Reducibility among equilibrium problems
• Representations and solutions for game-theoretic problems
• Settling the complexity of computing two-player Nash equilibria
• Simple complexity from imitation games
• Simple Local Search Problems that are Hard to Solve
• Simple search methods for finding a Nash equilibrium
• Subjectivity and correlation in randomized strategies
• The Approximation of Fixed Points of a Continuous Mapping
• The complexity of computing a Nash equilibrium
• The complexity of computing best-response automata in repeated games
• The Complexity of Eliminating Dominated Strategies
• The complexity of pure Nash equilibria
• The complexity of theorem-proving procedures
• The complexity of two-person zero-sum games in extensive form
• The computational complexity of evolutionarily stable strategies
• The Computational Complexity of Nash Equilibria in Concisely Represented Games
• The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games
• The NP-completeness column: finding needles in haystacks
• The relative complexity of NP search problems
• The traveling salesman problem. A computational study.
• Totally Balanced Games and Games of Flow

Cited in

(21)

• The computational complexity of cordial and equitable labelling
• A new algorithm to solve the generalized Nash equilibrium problem
• Steepest ascent can be exponential in bounded treewidth problems
• Pareto optimality in coalition formation
• Computation of the random arrival rule for bankruptcy problems
• On the polynomial time computation of equilibria for certain exchange economies
• Computing Equilibria with Partial Commitment
• The weighted set covering game: a vaccine pricing model for pediatric immunization
• ON COMPUTATIONAL COMPLEXITY OF HIERARCHICAL OPTIMIZATION
• Computational complexity of some intelligent computing systems
• A direct reduction from k-player to 2-player approximate Nash equilibrium
• Recent development in computational complexity characterization of Nash equilibrium
• Communication complexity of correlated equilibrium with small support
• Applications of Algebra for Some Game Theoretic Problems
• Coordination problems on networks revisited: statics and dynamics
• Complexity of stability in trading networks
• Computing simple mechanisms: Lift-and-round over marginal reduced forms
• scientific article; zbMATH DE number 7730634 (Why is no real title available?)
• Semidefinite programming for min-max problems and games
• Computation of equilibrium values in the Baron and Ferejohn bargaining model
• Properties and applications of dual reduction

Describes a project that uses

Uses Software

• Concorde
• GAMUT

This page was built for publication: Computing equilibria: a computational complexity perspective

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q847807)