Symmetries and the complexity of pure Nash equilibrium

DOI10.1016/J.JCSS.2008.09.001zbMath1154.91352OpenAlexW2162589776MaRDI QIDQ1004282

Markus Holzer, Felix Fischer, Felix Brandt

Publication date: 2 March 2009

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2008.09.001

zbMATH Keywords

computational complexitygame theorysymmetriespure Nash equilibriumnormal-form games

Mathematics Subject Classification ID

Other game-theoretic models (91A40) General equilibrium theory (91B50)

Related Items (17)

On the Complexity of Pareto-optimal Nash and Strong Equilibria ⋮ Equilibrium computation of the Hart and Mas-Colell bargaining model ⋮ Reasoning in large games with unboundedly many players ⋮ Query Complexity of Approximate Equilibria in Anonymous Games ⋮ The computation of Nash equilibrium in fashion games via semi-tensor product method ⋮ Weighted Boolean Formula Games ⋮ Query complexity of approximate equilibria in anonymous games ⋮ On the complexity of Pareto-optimal Nash and strong equilibria ⋮ Equilibria of graphical games with symmetries ⋮ Mixed-strategy Nash equilibrium for a discontinuous symmetricN-player game ⋮ Equilibria problems on games: complexity versus succinctness ⋮ DYNAMICS OF CHOICE RESTRICTION IN LARGE GAMES ⋮ Symmetric games revisited ⋮ Pairwise-Interaction Games ⋮ Nash equilibria in symmetric graph games with partial observation ⋮ Subgames within large games and the heuristic of imitation ⋮ Dynamic Restriction of Choices: Synthesis of Societal Rules

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Equilibria of graphical games with symmetries
• The influence of neighbourhood and choice on the complexity of finding pure Nash equilibria
• How easy is local search?
• On uniform circuit complexity
• Subjectivity and correlation in randomized strategies
• A global Newton method to compute Nash equilibria.
• A class of games possessing pure-strategy Nash equilibria
• Non-cooperative games
• The complexity of computing a Nash equilibrium
• The Computational Complexity of Nash Equilibria in Concisely Represented Games
• Simple Local Search Problems that are Hard to Solve
• Constant Depth Reducibility
• The complexity of pure Nash equilibria
• Log Depth Circuits for Division and Related Problems
• Approximate Local Search in Combinatorial Optimization
• On Context-Free Languages

This page was built for publication: Symmetries and the complexity of pure Nash equilibrium