On the complexity of approximating a Nash equilibrium
From MaRDI portal
Publication:2933653
DOI10.1145/2483699.2483703zbMATH Open1301.91001OpenAlexW2126211987MaRDI QIDQ2933653FDOQ2933653
Authors: Constantinos Daskalakis 
Publication date: 5 December 2014
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/1721.1/73096
Recommendations
Analysis of algorithms and problem complexity (68Q25) Noncooperative games (91A10) Approximation algorithms (68W25) 2-person games (91A05)
Cited In (39)
- Settling the complexity of computing two-player Nash equilibria
- Title not available (Why is that?)
- Title not available (Why is that?)
- Approximating Wardrop Equilibria with Finitely Many Agents
- Title not available (Why is that?)
- A direct reduction from \(k\)-player to 2-player approximate Nash equilibrium
- Zero-sum polymatrix games with link uncertainty: a Dempster-Shafer theory solution
- The Computational Complexity of Nash Equilibria in Concisely Represented Games
- Inapproximability of Nash equilibrium
- Learning Stationary Nash Equilibrium Policies in \(n\)-Player Stochastic Games with Independent Chains
- Constant rank two-player games are PPAD-hard
- Query complexity of approximate nash equilibria
- Nash equilibria: complexity, symmetries, and approximation
- Approximating Nash equilibria in tree polymatrix games
- Semidefinite Programming and Nash Equilibria in Bimatrix Games
- On the complexity of succinct zero-sum games
- Title not available (Why is that?)
- The complexity of computing a Nash equilibrium
- The Complexity of Nash Equilibria in Limit-Average Games
- Inapproximability of Nash equilibrium
- Approximations of Nash equilibria
- Title not available (Why is that?)
- On oblivious PTAS's for nash equilibrium
- Computing approximate Nash equilibria in polymatrix games
- On Nash-equilibria of approximation-stable games
- Approximating the best Nash equilibrium in \(n^{o(\log n)}\)-time breaks the exponential time hypothesis
- Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium
- Computing Nash equilibria by iterated polymatrix approximation
- The Computation of Approximate Generalized Feedback Nash Equilibria
- Inapproximability of NP-Complete Variants of Nash Equilibrium
- On tightness of the Tsaknakis-Spirakis algorithm for approximate Nash equilibrium
- On the Complexity of Nash Equilibria and Other Fixed Points
- Can almost everybody be almost happy?
- The approximation complexity of win-lose games
- Logarithmic Query Complexity for Approximate Nash Computation in Large Games
- Equilibrium paths in discounted supergames
- Solving zero-sum games using best-response oracles with applications to search games
- On the difficulty of approximately maximizing agreements.
- Approximating Nash equilibria and dense subgraphs via an approximate version of Carathéodory's theorem
This page was built for publication: On the complexity of approximating a Nash equilibrium
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2933653)
