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 ∈ achievable in polynomial time is 0.3393 [23]. In general, for n-player games an ∈-Nash equilibrium can be computed in polynomial time for an ∈ 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 ∈ 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 [23], our algorithm uses gradient descent on the maximum regret of the players.
展开▼
