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

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