On the hardness of game equivalence under local isomorphism^∗

ALBCOM Research Group, Departament de Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya, Jordi Girona 1-3, Ω Building, 08034 Barcelona, Spain.
gabarro@lsi.upc.edu, agarcia@lsi.upc.edu, mjserna@lsi.upc.edu

Received: 13 October 2011
Accepted: 31 August 2012

Abstract

We introduce a type of isomorphism among strategic games that we call local isomorphism. Local isomorphisms is a weaker version of the notions of strong and weak game isomorphism introduced in [J. Gabarro, A. Garcia and M. Serna, Theor. Comput. Sci. 412 (2011) 6675–6695]. In a local isomorphism it is required to preserve, for any player, the player’s preferences on the sets of strategy profiles that differ only in the action selected by this player. We show that the game isomorphism problem for local isomorphism is equivalent to the same problem for strong or weak isomorphism for strategic games given in: general, extensive and formula general form. As a consequence of the results in [J. Gabarro, A. Garcia and M. Serna, Theor. Comput. Sci. 412 (2011) 6675–6695] this implies that local isomorphism problem for strategic games is equivalent to (a) the circuit isomorphism problem for games given in general form, (b) the boolean formula isomorphism problem for formula games in general form, and (c) the graph isomorphism problem for games given in explicit form.