The Computational Complexity of Nash Equilibria in Concisely Represented Games
From MaRDI portal
Publication:2947564
DOI10.1145/2189778.2189779zbMath1322.68110OpenAlexW2127451547MaRDI QIDQ2947564
Grant Schoenebeck, Salil P. 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
Analysis of algorithms and problem complexity (68Q25) Noncooperative games (91A10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Inapproximability of Nash Equilibrium ⋮ Ranking games ⋮ On the complexity of constrained Nash equilibria in graphical games ⋮ Simulating cardinal preferences in Boolean games: a proof technique ⋮ Computing equilibria: a computational complexity perspective ⋮ The complexity of decision problems about equilibria in two-player Boolean games ⋮ Weighted Boolean Formula Games ⋮ PPAD-complete approximate pure Nash equilibria in Lipschitz games ⋮ Equilibria of graphical games with symmetries ⋮ On the Complexity of Equilibria Problems in Angel-Daemon Games ⋮ PPAD-complete pure approximate Nash equilibria in Lipschitz games ⋮ The complexity of game isomorphism ⋮ Equilibria problems on games: complexity versus succinctness ⋮ New complexity results about Nash equilibria ⋮ Symmetries and the complexity of pure Nash equilibrium
