Nash equilibria: complexity, symmetries, and approximation

DOI10.1016/J.COSREV.2009.03.003zbMATH Open1303.91010OpenAlexW122730496MaRDI QIDQ458482FDOQ458482

Constantinos Daskalakis

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.2009.03.003

zbMATH Keywords

complexityNash equilibria

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to computer science (68-02) 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?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Non-cooperative games
• Algorithmic Game Theory
• An Optimization Approach for Approximate Nash Equilibria
• On a Generalization of the Lemke–Howson Algorithm to Noncooperative N-Person Games
• On the Complexity of Nash Equilibria and Other Fixed Points
• New complexity results about Nash equilibria
• On the complexity of the parity argument and other inefficient proofs of existence
• Congestion games with player-specific payoff functions
• Equilibrium Points of Bimatrix Games
• The Approximation of Fixed Points of a Continuous Mapping
• A note on approximate Nash equilibria
• On total functions, existence theorems and computational complexity
• New algorithms for approximate Nash equilibria in bimatrix games
• The women of Cairo: equilibria in large anonymous games
• Algorithmic mechanism design (extended abstract)
• The complexity of computing a Nash equilibrium
• On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
• Nash and correlated equilibria: Some complexity considerations
• Games of fixed rank: a hierarchy of bimatrix games
• Approximate Nash equilibria in anonymous games
• Computing equilibria in multi-player games
• On oblivious PTAS's for nash equilibrium
• An Efficient PTAS for Two-Strategy Anonymous Games
• Computing Equilibria of N-Person Games
• Exponential lower bounds for finding Brouwer fixed points

Cited In (6)

• A note on the symmetry of all Nash equilibria in games with increasing best replies
• Title not available (Why is that?)
• Title not available (Why is that?)
• Settling Some Open Problems on 2-Player Symmetric Nash Equilibria
• On the Complexity of Nash Equilibria and Other Fixed Points
• Title not available (Why is that?)

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• The Complexity of Computing a Nash Equilibrium 👍 👎
• Symmetries and the complexity of pure Nash equilibrium 👍 👎
• On the Complexity of Nash Equilibria and Other Fixed Points 👍 👎
• Symmetries and the Complexity of Pure Nash Equilibrium 👍 👎
• Approximations of Nash equilibria 👍 👎
• The complexity of pure Nash equilibria 👍 👎
• The complexity of computational problems about Nash equilibria in symmetric win-lose games 👍 👎
• On the Complexity of Approximating a Nash Equilibrium 👍 👎

This page was built for publication: Nash equilibria: complexity, symmetries, and approximation

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