The Computational Complexity of Nash Equilibria in Concisely Represented Games
DOI10.1145/2189778.2189779zbMATH Open1322.68110OpenAlexW2127451547MaRDI QIDQ2947564FDOQ2947564
Authors: Grant Schoenebeck, Salil Vadhan 
Publication date: 24 September 2015
Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)
Full work available at URL: http://nrs.harvard.edu/urn-3:HUL.InstRepos:12763606
Recommendations
- The complexity of computing a Nash equilibrium
- The complexity of computing a Nash equilibrium
- The complexity of computational problems about Nash equilibria in symmetric win-lose games
- On the complexity of constrained Nash equilibria in graphical games
- On the complexity of approximating a Nash equilibrium
- scientific article; zbMATH DE number 6783488
- On the computational complexity of decision problems about multi-player Nash equilibria
- On the computational complexity of decision problems about multi-player Nash equilibria
- On the computability of Nash equilibria
- The complexity of pure Nash equilibria
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Noncooperative games (91A10)
Cited In (32)
- Some results of Maria Serna on strategic games: complexity of equilibria and models
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the complexity of constrained Nash equilibria in graphical games
- Query complexity of approximate nash equilibria
- The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games
- Weighted Boolean formula games
- The complexity of computing a Nash equilibrium
- PPAD-complete pure approximate Nash equilibria in Lipschitz games
- The Complexity of Nash Equilibria in Limit-Average Games
- New complexity results about Nash equilibria
- Symmetries and the complexity of pure Nash equilibrium
- Good neighbors are hard to find: Computational complexity of network formation
- Algorithms and Computation
- Inapproximability of Nash equilibrium
- On computational complexity of membership test in flow games and linear production games
- On the Complexity of Equilibria Problems in Angel-Daemon Games
- The complexity of game isomorphism
- Inapproximability of NP-Complete Variants of Nash Equilibrium
- Equilibria of graphical games with symmetries
- Polynomial-time computation of exact correlated equilibrium in compact games
- Simulating cardinal preferences in Boolean games: a proof technique
- The complexity of decision problems about equilibria in two-player Boolean games
- Complexity of Verifying Game Equilibria
- Computing lexicographically safe Nash equilibria in finite two-person games with tight game forms given by oracles
- PPAD-complete approximate pure Nash equilibria in Lipschitz games
- Ranking games
- Equilibria problems on games: complexity versus succinctness
- On the complexity of Nash equilibria of action-graph games
- Logarithmic Query Complexity for Approximate Nash Computation in Large Games
- On sparse discretization for graphical games
- Computing equilibria: a computational complexity perspective
This page was built for publication: The Computational Complexity of Nash Equilibria in Concisely Represented Games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947564)
