Issue |
RAIRO-Theor. Inf. Appl.
Volume 47, Number 2, April-June 2013
|
|
---|---|---|
Page(s) | 147 - 169 | |
DOI | https://doi.org/10.1051/ita/2012024 | |
Published online | 05 November 2012 |
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
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.
Mathematics Subject Classification: 68Q17
Key words: Game isomorphism / succinct representations / strategic games / formula games / computational complexity / circuit isomorphism / boolean formula isomorphism / graph isomorphism
© EDP Sciences 2012
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.