2008-01-18-SAGT < Publications

Publications

Publications.2008-01-18-SAGTr1.6 - 20 Feb 2008 - 15:44 - Main.akimtopic end

%PUBLIHEADER%


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)}.

   * [[%LRDEDOWNLOAD%papers/hemon.08.sagt.pdf][hemon.08.sagt.pdf]]

to top

End of topic
Skip to action links | Back to top

Edit | Attach image or document | Printable version | Raw text | More topic actions
Revisions: | r1.6 | > | r1.5 | > | r1.4 | Total page history | Backlinks

You are here: Publications > 2008-01-18-SAGT

to top