On the complexity of deciding bimatrix games similarity (Q955038)

The paper deals with computational aspects of finding Nash equilibria in bimatrix games. The attention is focused on specific situation of similarity between two games, namely whether they share a common Nash equilibrium (so called weak similarity) or if their sets of Nash equilibria are identical (strong similarity). It is shown that the decision about the weak similarity represents an NP-complete problem, meanwhile the complexity of the verification of the strong similarity is co-NP-hard.