Nash equilibria: complexity, symmetries, and approximation
From MaRDI portal
Publication:458482
DOI10.1016/j.cosrev.2009.03.003zbMath1303.91010OpenAlexW122730496MaRDI QIDQ458482
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
Noncooperative games (91A10) 2-person games (91A05) Research exposition (monographs, survey articles) pertaining to game theory, economics, and finance (91-02) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On total functions, existence theorems and computational complexity
- Games of fixed rank: a hierarchy of bimatrix games
- Exponential lower bounds for finding Brouwer fixed points
- New complexity results about Nash equilibria
- A note on approximate Nash equilibria
- New algorithms for approximate Nash equilibria in bimatrix games
- 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
- On the complexity of the parity argument and other inefficient proofs of existence
- Congestion games with player-specific payoff functions
- Approximate Nash equilibria in anonymous games
- The women of Cairo: equilibria in large anonymous games
- Non-cooperative games
- Algorithmic mechanism design (extended abstract)
- The complexity of computing a Nash equilibrium
- On the Complexity of Nash Equilibria and Other Fixed Points
- An Optimization Approach for Approximate Nash Equilibria
- On oblivious PTAS's for nash equilibrium
- Equilibrium Points of Bimatrix Games
- Algorithmic Game Theory
- An Efficient PTAS for Two-Strategy Anonymous Games
- The Approximation of Fixed Points of a Continuous Mapping
- Computing Equilibria of N-Person Games
- On a Generalization of the Lemke–Howson Algorithm to Noncooperative N-Person Games
