The complexity of game isomorphism

DOI10.1016/j.tcs.2011.07.022zbMath1227.91016MaRDI QIDQ650900

Joaquim Gabarró, Alina García, Maria J. 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 complexity; graph isomorphism; Boolean formulas; game isomorphism; Boolean formula isomorphism; circuit isomorphism; formula games; succinct representations

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

91A99: Game theory

91A70: Spaces of games

Related Items

Strong isomorphism in Eisert-Wilkens-Lewenstein type quantum games, Quantum games with strategies induced by basis change rules, Some results of Maria Serna on strategic games: complexity of equilibria and models, Computational aspects of uncertainty profiles and angel-daemon games, Weighted Boolean Formula Games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Equilibria problems on games: complexity versus succinctness
• A note on isomorphism and strategic equivalence of cooperative games
• Monotone circuits for monotone weighted threshold functions
• On the computational complexity of some classical equivalence relations on boolean functions
• Weak isomorphism of extensive games.
• The canonical extensive form of a game form. II: Representation
• 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
• The Computational Complexity of Nash Equilibria in Concisely Represented Games
• The complexity of computations by networks
• On Threshold Circuits and Polynomial Computation
• The Formula Isomorphism Problem
• Algorithms, games, and the internet
• Algorithmic Game Theory