Recent development in computational complexity characterization of Nash equilibrium

DOI10.1016/J.COSREV.2007.09.002zbMATH Open1302.68135OpenAlexW1988766353MaRDI QIDQ458453FDOQ458453

Authors: Xi Chen, Xiaotie Deng 

Publication date: 7 October 2014

Published in: Computer Science Review (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cosrev.2007.09.002

Recommendations

• Complexity of pure-strategy Nash equilibria in non-cooperative games
• Computing equilibria: a computational complexity perspective
• The complexity of computing a Nash equilibrium
• The complexity of computing a Nash equilibrium
• On the Complexity of Nash Equilibria and Other Fixed Points

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to computer science (68-02) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Research exposition (monographs, survey articles) pertaining to game theory, economics, and finance (91-02) Noncooperative games (91A10) 2-person games (91A05)

Cites Work

• Title not available (Why is that?)
• Non-cooperative games
• Equilibrium points in n -person games
• Theory of games and economic behavior.
• Title not available (Why is that?)
• The logic of animal conflict
• On equilibria in finite games
• Complementary pivot theory of mathematical programming
• Title not available (Why is that?)
• The Core of an N Person Game
• A Social Equilibrium Existence Theorem*
• Existence of an Equilibrium for a Competitive Economy
• How easy is local search?
• On the complexity of the parity argument and other inefficient proofs of existence
• The fundamental theorem of algebra and complexity theory
• Title not available (Why is that?)
• Equilibrium Points of Bimatrix Games
• The Approximation of Fixed Points of a Continuous Mapping
• The Linear Complementarity Problem
• Smoothed analysis of algorithms
• A note on approximate Nash equilibria
• Polynomial algorithms for approximating Nash equilibria of bimatrix games
• Algorithms, games, and the internet
• A Partition Theorem for Euclidean n-Space
• On total functions, existence theorems and computational complexity
• Algorithmic Aspects of the Core of Combinatorial Optimization Games
• Efficient Algorithms for Constant Well Supported Approximate Equilibria in Bimatrix Games
• The complexity of computing a Nash equilibrium
• On the Complexity of 2D Discrete Fixed Point Problem
• On the complexity of market equilibria with maximum social welfare
• An interior point potential reduction algorithm for the linear complementarity problem
• Randomized pivot algorithms for \(P\)-matrix linear complementarity problems
• On the complexity of price equilibria
• The approximation complexity of win-lose games
• Leontief economies encode nonzero sum two-player games
• Hard-to-Solve Bimatrix Games
• Title not available (Why is that?)
• Simple search methods for finding a Nash equilibrium

Cited In (1)

• Computing equilibria: a computational complexity perspective

This page was built for publication: Recent development in computational complexity characterization of Nash equilibrium

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