The Computational Complexity of Nash Equilibria in Concisely Represented Games

DOI10.1145/2189778.2189779MaRDI QIDQ2947564zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

Nash equilibriumcomputational game theorygraph gamescircuit gamesconcise games

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Noncooperative games (91A10)

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

Cited in

(32)

• Some results of Maria Serna on strategic games: complexity of equilibria and models
• scientific article; zbMATH DE number 5942357 (Why is no real title available?)
• scientific article; zbMATH DE number 6866347 (Why is no real title available?)
• 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
• Logarithmic Query Complexity for Approximate Nash Computation in Large Games
• On the complexity of Nash equilibria of action-graph 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)