Abstract:

We consider small-influence anonymous games with a large number of players $n$ where every player has two actions. For this class of games we present a best-reply dynamic with the following two properties. First, the dynamic reaches Nash approximate equilibria fast (in at most $cn log n$ steps for some constant $c>0$). Second, Nash approximate equilibria are played by the dynamic with a limit frequency of at least $1-e^-c'n$ for some constant $c'>0$.

Website