Reducibility among equilibrium problems

DOI10.1145/1132516.1132526MaRDI QIDQ2931370zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

Nash equilibrium

Mathematics Subject Classification ID

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

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

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
• A note on approximate Nash equilibria
• From duels to battlefields: computing equilibria of Blotto and other games
• 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)