The complexity of game isomorphism

DOI10.1016/J.TCS.2011.07.022zbMATH Open1227.91016OpenAlexW2052601701MaRDI QIDQ650900FDOQ650900

Authors: Joaquim Gabarró, Alina García, Maria Serna 

Publication date: 7 December 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.07.022

Recommendations

• On the Complexity of Game Isomorphism
• On the hardness of game equivalence under local isomorphism
• Equilibria problems on games: complexity versus succinctness
• Weak isomorphism of extensive games.
• Symmetries and the Complexity of Pure Nash Equilibrium

zbMATH Keywords

computational complexitygraph isomorphismBoolean formulasgame isomorphismBoolean formula isomorphismcircuit isomorphismformula gamessuccinct representations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Game theory (91A99) Spaces of games (91A70)

Cites Work

• Algorithmic Game Theory
• Title not available (Why is that?)
• A course in game theory.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Algorithms, games, and the internet
• The canonical extensive form of a game form. II: Representation
• Title not available (Why is that?)
• Limiting distributions of the number of pure strategy Nash equilibria in \(n\)-person games
• Asymptotic expected number of Nash equilibria of two-player normal form games
• Title not available (Why is that?)
• Monotone circuits for monotone weighted threshold functions
• The complexity of computations by networks
• The Formula Isomorphism Problem
• The Computational Complexity of Nash Equilibria in Concisely Represented Games
• On the computational complexity of some classical equivalence relations on boolean functions
• Weak isomorphism of extensive games.
• On Threshold Circuits and Polynomial Computation
• Title not available (Why is that?)
• Equilibria problems on games: complexity versus succinctness
• A note on isomorphism and strategic equivalence of cooperative games

Cited In (11)

• Some results of Maria Serna on strategic games: complexity of equilibria and models
• Quantum games with strategies induced by basis change rules
• Weighted Boolean formula games
• Quantification and statistical analysis of topological features of recursive trees
• Computational aspects of uncertainty profiles and angel-daemon games
• Strong isomorphism in Eisert-Wilkens-Lewenstein type quantum games
• On the Complexity of Game Isomorphism
• Project games
• New Computational Paradigms
• On the hardness of game equivalence under local isomorphism
• Weak isomorphism of extensive games.

This page was built for publication: The complexity of game isomorphism

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