On the complexity of deciding bimatrix games similarity

摘要

In this paper, we show that it is NP-complete to decide whether two bimatrix games share a common Nash equilibrium. Furthermore, it is co-NP-hard to decide whether two bimatrix games have exactly the same set of Nash equilibria.