In an ε-Nash equilibrium, a player can gain at most ε by unilaterally changing his behaviour. For two-player (bimatrix) games with payoffs in [0,1], the best-known e achievable in polynomial time is 0.3393. In general, for n-player games an ε-Nash equilibrium can be computed in polynomial time for an e that is an increasing function of n but does not depend on the number of strategies of the players. For three-player and four-player games the corresponding values of e are 0.6022 and 0.7153, respectively. Polymatrix games are a restriction of general n-player games where a player's payoff is the sum of payoffs from a number of bimatrix games. There exists a very small but constant ε such that computing an ε-Nash equilibrium of a polymatrix game is PPAD-hard. Our main result is that an (0.5 + δ)-Nash equilibrium of an n-player polymatrix game can be computed in time polynomial in the input size and 1/δ. Inspired by the algorithm of Tsaknakis and Spirakis, our algorithm uses gradient descent on the maximum regret of the players.
展开▼
