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

• Algorithmic Game Theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• A course in game theory.
• Title not available (Why is that?)
• Symmetries and the complexity of pure Nash equilibrium
• Title not available (Why is that?)
• Title not available (Why is that?)
• The complexity of pure Nash equilibria
• Title not available (Why is that?)
• Title not available (Why is that?)
• Algorithms, games, and the internet
• Computing correlated equilibria in multi-player games
• The complexity of computing a Nash equilibrium
• Automata, Languages and Programming
• Computing equilibria in multi-player games
• The influence of neighbourhood and choice on the complexity of finding pure Nash equilibria
• Automata, Languages and Programming
• The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games
• The Computational Complexity of Nash Equilibria in Concisely Represented Games
• Algorithms – ESA 2005
• The computational complexity of equivalence and isomorphism problems
• On the Complexity of Equilibria Problems in Angel-Daemon Games
• On the Complexity of Game Isomorphism
• Mathematical Foundations of Computer Science 2005
• Algorithms and Computation

Cited In (15)

• 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
• 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
• Weighted Boolean Formula Games
• Algorithms – ESA 2005
• Simulating cardinal preferences in Boolean games: a proof technique
• 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

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)