Sébastien Hémon, Miklos Santha and Michel de Rougemont. Approximate Nash Equilibria for multi-players Games. Symposium on Algorithmic Game theory (SAGT 08) Paderborn, Germany April - May 2008

We consider Games of complete information with r players, and study the existence of polynomial time algorithms for \eps-approximate Nash equilibria in the additive and multiplicative sense. For the additive approximation, we prove an \frac{r-1}{r} lower bound on \eps for strategies using a support less than \sqrt[r-1]{\log{n}} where n is the maximum number of pure strategies, and give a polynomial time algorithm which computes an \frac{r-1}{r}-approximate Equilibrium. For the multiplicative approximation, we prove a Lipton-result to approximate a Nash Equilibrium. If we assume that the gains of the players at a Nash Equilibrium are greater than a value g, we find an \eps-approximate Nash equilibrium whose support is included in the support of the Nash equilibrium of size \frac{\log n.r}{g.\eps^2}. We exhibit a class of games where this hypothesis does not hold and where the support size of such an \eps-approximate Nash equilibrium is greater than \frac{n}{2.(1+\eps)}.

• hemon.08.sagt.pdf