Equilibria problems on games: complexity versus succinctness

DOI10.1016/J.JCSS.2011.01.001MaRDI QIDQ657923zbMATH OpenOpenAlexFDO

Authors Carme Àlvarez, Joaquim Gabarró, Maria Serna

Publication date 11 January 2012

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.2011.01.001

zbMATH Keywords

complexity classesextensive gamessuccinct representationsstrategic games, Nash equilibria

Mathematics Subject Classification ID

Noncooperative games (91A10) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Games in extensive form (91A18)

Recommendations

• Algorithms and Computation
• Mathematical Foundations of Computer Science 2005
• scientific article; zbMATH DE number 2243403
• The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games
• The Computational Complexity of Nash Equilibria in Concisely Represented Games

Cites work

• scientific article; zbMATH DE number 5301288 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 719756 (Why is no real title available?)
• scientific article; zbMATH DE number 2086616 (Why is no real title available?)
• scientific article; zbMATH DE number 2243403 (Why is no real title available?)
• scientific article; zbMATH DE number 3078991 (Why is no real title available?)
• A course in game theory.
• Algorithmic Game Theory
• Algorithms and Computation
• Algorithms – ESA 2005
• Algorithms, games, and the internet
• Automata, Languages and Programming
• Automata, Languages and Programming
• Computing correlated equilibria in multi-player games
• Computing equilibria in multi-player games
• Mathematical Foundations of Computer Science 2005
• On the Complexity of Equilibria Problems in Angel-Daemon Games
• On the Complexity of Game Isomorphism
• Symmetries and the complexity of pure Nash equilibrium
• The Computational Complexity of Nash Equilibria in Concisely Represented Games
• The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games
• The complexity of computing a Nash equilibrium
• The complexity of pure Nash equilibria
• The computational complexity of equivalence and isomorphism problems
• The influence of neighbourhood and choice on the complexity of finding pure Nash equilibria

Cited in

(17)

• The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games
• On the complexity of problems on simple games
• Algorithms – ESA 2005
• The complexity of game isomorphism
• On Dedekind's problem for complete simple games
• Simulating cardinal preferences in Boolean games: a proof technique
• The complexity of decision problems about equilibria in two-player Boolean games
• Some results of Maria Serna on strategic games: complexity of equilibria and models
• Multilinear games
• Precise complexity of the core in dichotomous and additive hedonic games
• Algorithms and Computation
• Weighted Boolean formula games
• Mathematical Foundations of Computer Science 2005
• On the Complexity of Equilibria Problems in Angel-Daemon Games
• A duality principle for selection games
• On the Complexity of Game Isomorphism
• Computational aspects of uncertainty profiles and angel-daemon games

This page was built for publication: Equilibria problems on games: complexity versus succinctness

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