Symmetries and the complexity of pure Nash equilibrium

DOI10.1016/J.JCSS.2008.09.001MaRDI QIDQ1004282zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

computational complexitygame theorysymmetriespure Nash equilibriumnormal-form games

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(24)

• Some results of Maria Serna on strategic games: complexity of equilibria and models
• Mixed-strategy Nash equilibrium for a discontinuous symmetric \(N\)-player game
• A note on the symmetry of all Nash equilibria in games with increasing best replies
• Nash equilibria: complexity, symmetries, and approximation
• Weighted Boolean formula games
• Subgames within large games and the heuristic of imitation
• Dynamic Restriction of Choices: Synthesis of Societal Rules
• Query complexity of approximate equilibria in anonymous games
• Dynamics of choice restriction in large games
• QBF Modeling: Exploiting Player Symmetry for Simplicity and Efficiency
• Reasoning in large games with unboundedly many players
• The computation of Nash equilibrium in fashion games via semi-tensor product method
• Nash equilibria in symmetric games with partial observation
• Query complexity of approximate equilibria in anonymous games
• Equilibria of graphical games with symmetries
• Symmetric games revisited
• 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
• scientific article; zbMATH DE number 7136658 (Why is no real title available?)
• 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)