The Complexity of Computational Problems about Nash Equilibria in Symmetric Win-Lose Games
share
We revisit the complexity of deciding, given a bimatrix game, whether it has a Nash equilibrium with certain natural properties; such decision problems were early known to be NP-hard <cit.>. We show that NP-hardness still holds under two significant restrictions in simultaneity: the game is win-lose (that is, all utilities are 0 or 1) and symmetric. To address the former restriction, we design win-lose gadgets and a win-lose reduction; to accomodate the latter restriction, we employ and analyze the classical GHR-symmetrization <cit.> in the win-lose setting. Thus, symmetric win-lose bimatrix games are as complex as general bimatrix games with respect to such decision problems. As a byproduct of our techniques, we derive hardness results for search, counting and parity problems about Nash equilibria in symmetric win-lose bimatrix games.
READ FULL TEXT