An Efficient PTAS for Two-Strategy Anonymous Games

Details An Efficient PTAS for Two-Strategy Anonymous Games An Efficient PTAS for Two-Strategy Anonymous Games

2008-12-12

arxiv.org/abs/0812.2277v1

Computer Science

Computer Science and Game Theory

Scientific paper

We present a novel polynomial time approximation scheme for two-strategy anonymous games, in which the players' utility functions, although potentially different, do not differentiate among the identities of the other players. Our algorithm computes an $eps$-approximate Nash equilibrium of an $n$-player 2-strategy anonymous game in time $poly(n) (1/eps)^{O(1/eps^2)}$, which significantly improves upon the running time $n^{O(1/eps^2)}$ required by the algorithm of Daskalakis & Papadimitriou, 2007. The improved running time is based on a new structural understanding of approximate Nash equilibria: We show that, for any $eps$, there exists an $eps$-approximate Nash equilibrium in which either only $O(1/eps^3)$ players randomize, or all players who randomize use the same mixed strategy. To show this result we employ tools from the literature on Stein's Method.

Affiliated with

Also associated with

No associations

Rating

An Efficient PTAS for Two-Strategy Anonymous Games does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An Efficient PTAS for Two-Strategy Anonymous Games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Efficient PTAS for Two-Strategy Anonymous Games will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-609232