Approximate Equilibria in Games with Few Players

Understand

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.