The Complexity of Computational Problems About Nash Equilibria in Symmetric Win-Lose Games

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 (Gilboa and Zemel in Games Econ Behav 1(1):80–93, 1989). 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 (Griesmer et al. in On symmetric bimatrix games, IBM research paper RC-959, IBM Corp., T. J. Watson Research Center, 1963) 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.