Computing Approximate Nash Equilibria in Polymatrix Games

摘要

In an -Nash equilibrium, a player can gain at most by unilaterally changing his behavior. For two-player (bimatrix) games with payoffs in [0, 1], the best-known achievable in polynomial time is 0.3393 (Tsaknakis and Spirakis in Internet Math 5(4):365-382, 2008). 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 -hard. Our main result is that a -Nash equilibrium of an n-player polymatrix game can be computed in time polynomial in the input size and . Inspired by the algorithm of Tsaknakis and Spirakis [28], our algorithm uses gradient descent style approach on the maximum regret of the players. We also show that this algorithm can be applied to efficiently find a -Nash equilibrium in a two-player Bayesian game.