Recent development in computational complexity characterization of Nash equilibrium

DOI10.1016/J.COSREV.2007.09.002MaRDI QIDQ458453zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

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)