Equilibria problems on games: complexity versus succinctness

DOI10.1016/j.jcss.2011.01.001zbMath1230.91006OpenAlexW2094143906MaRDI QIDQ657923

Joaquim Gabarró, Carme Àlvarez, Maria J. 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) Games in extensive form (91A18) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Some results of Maria Serna on strategic games: complexity of equilibria and models ⋮ Simulating cardinal preferences in Boolean games: a proof technique ⋮ Weighted Boolean Formula Games ⋮ Computational aspects of uncertainty profiles and angel-daemon games ⋮ The complexity of game isomorphism ⋮ A duality principle for selection games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The influence of neighbourhood and choice on the complexity of finding pure Nash equilibria
• Symmetries and the complexity of pure Nash equilibrium
• The computational complexity of equivalence and isomorphism problems
• The complexity of computing a Nash equilibrium
• The Computational Complexity of Nash Equilibria in Concisely Represented Games
• On the Complexity of Equilibria Problems in Angel-Daemon Games
• On the Complexity of Game Isomorphism
• The complexity of pure Nash equilibria
• The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games
• Algorithms, games, and the internet
• Algorithmic Game Theory
• Automata, Languages and Programming
• Automata, Languages and Programming
• Algorithms – ESA 2005
• Mathematical Foundations of Computer Science 2005
• Algorithms and Computation
• Computing correlated equilibria in multi-player games