Equilibria problems on games: complexity versus succinctness

DOI10.1016/J.JCSS.2011.01.001zbMATH Open1230.91006OpenAlexW2094143906MaRDI QIDQ657923FDOQ657923

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)

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