Multi-player Approximate Nash Equilibria

In this paper we study the complexity of finding approximate Nash equilibria in multi-player normal-form games. First, for any constant number n, we present a polynomial-time algorithm for computing a relative 1-1 1+(n-1) n-Nash equilibrium in arbitrary nplayer games and a relative 1-1 1+(n-1) n-1-Nash equilibrium in symmetric n-player games. Next, we show that there is an additive ε-well-supported Nash equilibrium, for any ε > 0, with support equal to O(ln(nm/ε)/ε 2), where m is the number of pure strategies. Finally, we prove that finding additive approximate Nash equilibria is easy in random multi-player games. * Research partially supported by the Centre for Discrete Mathematics and its Applications (DIMAP) and by the EPSRC awards EP/D063191/1 and EP/G069034/1.