On the Approximation of Nash Equilibria in Sparse Win-Lose Multi-player Games

Abstract A polymatrix game is a multi-player game over n players, where each player chooses a pure strategy from a list of its own pure strategies. The utility of each player is a sum of payoffs it gains from the two player's game from all its neighbors, under its chosen strategy and that of its neighbor. As a natural extension to two-player games (a.k.a. bimatrix games), polymatrix games are widely used for multi-agent games in real world scenarios. In this paper we show that the problem of approximating a Nash equilibrium in a polymatrix game within the polynomial precision is PPAD-hard, even in sparse and win-lose ones. This result further challenges the predictability of Nash equilibria as a solution concept in the multi-agent setting. We also propose a simple and efficient algorithm, when the game is further restricted. Together, we establish a new dichotomy theorem for this class of games. It is also of independent interest for exploring the computational and structural properties in Nash equilibria.