Computing equilibria: a computational complexity perspective
From MaRDI portal
Publication:847807
DOI10.1007/s00199-009-0448-yzbMath1192.91035OpenAlexW2070377170MaRDI QIDQ847807
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
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
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
