The complexity of game isomorphism

DOI10.1016/J.TCS.2011.07.022MaRDI QIDQ650900zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(11)

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

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)