[Lrde Annonce] article pour SAGT 2008

We are pleased to announce that the following paper has been accepted for publication at the first Symposium on Algorithmic Game Theory (SAGT 2008) that will take place at Paderborn, Germany from April 30th to May 2nd. Sébastien Hémon, Miklos Santha and Michel de Rougemont. Approximate Nash Equilibria for multi-players Games. http://publis.lrde.epita.fr/2008-01-18-SAGT 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)}. -- Daniela Becker