  We study the problem of computing approximate Nash equilibria (epsilon-Nash
equilibria) in normal form games, where the number of players is a small
constant. We consider the approach of looking for solutions with constant
support size. It is known from recent work that in the 2-player case, a
1/2-Nash equilibrium can be easily found, but in general one cannot achieve a
smaller value of epsilon than 1/2. In this paper we extend those results to the
k-player case, and find that epsilon = 1-1/k is feasible, but cannot be
improved upon. We show how stronger results for the 2-player case may be used
in order to slightly improve upon the epsilon = 1-1/k obtained in the k-player
case.
