Reducibility among equilibrium problems

DOI10.1145/1132516.1132526zbMATH Open1301.68161OpenAlexW2125413339MaRDI QIDQ2931370FDOQ2931370

Authors: Paul W. Goldberg, Christos Papadimitriou 

Publication date: 25 November 2014

Published in: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1132516.1132526

Recommendations

• The complexity of computing a Nash equilibrium
• The complexity of computing a Nash equilibrium
• The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games
• New complexity results about Nash equilibria
• A direct reduction from \(k\)-player to 2-player approximate Nash equilibrium

zbMATH Keywords

Nash equilibrium

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Noncooperative games (91A10) Games involving graphs (91A43)

Cited In (18)

• On the complexity of constrained Nash equilibria in graphical games
• A direct reduction from \(k\)-player to 2-player approximate Nash equilibrium
• Properties and applications of dual reduction
• Approximate equilibria in strongly symmetric games
• Reducible equilibrium properties: comments on recent existence results
• Action-graph games
• The complexity of uniform Nash equilibria and related regular subgraph problems
• Games with tolerant players
• From duels to battlefields: computing equilibria of Blotto and other games
• A note on approximate Nash equilibria
• Approximate Equilibria for Strategic Two Person Games
• Imitation games and computation
• Random bimatrix games are asymptotically easy to solve (a simple proof)
• Equilibria of graphical games with symmetries
• Polynomial-time computation of exact correlated equilibrium in compact games
• Well supported approximate equilibria in bimatrix games
• New algorithms for approximate Nash equilibria in bimatrix games
• Computing equilibria: a computational complexity perspective

This page was built for publication: Reducibility among equilibrium problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2931370)