Abstract
We revisit the complexity of deciding, given a {\it bimatrix game,} whether it has a {\it Nash equilibrium} with certain natural properties; such decision problems were early known to be NP-hard~\cite{GZ89}. We show that NP-hardness still holds under two significant restrictions in simultaneity: the game is {\it win-lose} (that is, all {\it utilities} are 0 or 1) and {\it symmetric}. To address the former restriction, we design win-lose {\it gadgets} and a win-lose reduction; to accomodate the latter restriction, we employ and analyze the classical {\it GHR-symmetrization}~\cite{GHR63} in the win-lose setting. Thus, {\it 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.