Carregant...
Carregant...

Vés al contingut (premeu Retorn)

The complexity of game isomorphism

Autor
Gabarro, J.; Garcia-Holgado, A.; Serna, M.
Tipus d'activitat
Document cientificotècnic
Data
2010
Codi
LSI-10-23-R
Repositori
http://hdl.handle.net/2117/91166 Obrir en finestra nova
Resum
We address the question of whether two multiplayer strategic games are equivalent and the computational complexity of deciding such a property. We introduce two notions of isomorphisms, strong and weak. Each one of those isomorphisms preserves a different structure of the game. Strong isomorphisms are defined to preserve the utility functions and Nash equilibria. Weak isomorphisms preserve only the player's preference relations and thus pure Nash equilibria. We show that the computational comple...
Citació
Gabarró, J., García, A., Serna, M. "The Complexity of game isomorphism". 2010.
Paraules clau
Boolean formula isomorphism, Boolean formulas, Circuit isomorphism, Computational complexity, Formula games, Game isomorphism, Graph isomorphism, Succinct representations
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals

Participants

Arxius