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

No. 6: AAAI-21 Technical Tracks 6

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 35

AAAI Technical Track on Game Theory and Economic Paradigms

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.

10.1609/aaai.v35i6.16699