Symmetries and the complexity of pure Nash equilibrium

DOI10.1016/J.JCSS.2008.09.001zbMATH Open1154.91352OpenAlexW2162589776MaRDI QIDQ1004282FDOQ1004282

Authors: Felix Brandt, Felix Fischer, Markus Holzer 

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

Recommendations

• Symmetries and the Complexity of Pure Nash Equilibrium
• Equilibria of graphical games with symmetries
• Nash equilibria: complexity, symmetries, and approximation
• The complexity of pure Nash equilibria
• scientific article; zbMATH DE number 2243403

zbMATH Keywords

computational complexitygame theorysymmetriespure Nash equilibriumnormal-form games

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (22)

• DYNAMICS OF CHOICE RESTRICTION IN LARGE GAMES
• A note on the symmetry of all Nash equilibria in games with increasing best replies
• Nash equilibria: complexity, symmetries, and approximation
• Dynamic Restriction of Choices: Synthesis of Societal Rules
• Subgames within large games and the heuristic of imitation
• QBF Modeling: Exploiting Player Symmetry for Simplicity and Efficiency
• 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
• Query complexity of approximate equilibria in anonymous games
• Weighted Boolean Formula Games
• Equilibria of graphical games with symmetries
• Symmetric games revisited
• Mixed-strategy Nash equilibrium for a discontinuous symmetricN-player game
• Pairwise-interaction games
• Equilibria problems on games: complexity versus succinctness
• On the complexity of Pareto-optimal Nash and strong equilibria
• On the complexity of Pareto-optimal Nash and strong equilibria
• Symmetries and the Complexity of Pure Nash Equilibrium
• Title not available (Why is that?)
• Equilibrium computation of the Hart and Mas-Colell bargaining model
• Nash equilibria in symmetric graph games with partial observation

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

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