2019/07/24 by Bilò, Vittorio, Mavronicolas, Marios
#Computational Complexity (cs.CC) #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1907.10468
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~\citeGZ89. 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~\citeGHR63 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.