  We investigate the problem of equilibrium computation for "large" $n$-player
games. Large games have a Lipschitz-type property that no single player's
utility is greatly affected by any other individual player's actions. In this
paper, we mostly focus on the case where any change of strategy by a player
causes other players' payoffs to change by at most $\frac{1}{n}$. We study
algorithms having query access to the game's payoff function, aiming to find
$\epsilon$-Nash equilibria. We seek algorithms that obtain $\epsilon$ as small
as possible, in time polynomial in $n$.
  Our main result is a randomised algorithm that achieves $\epsilon$
approaching $\frac{1}{8}$ for 2-strategy games in a {\em completely uncoupled}
setting, where each player observes her own payoff to a query, and adjusts her
behaviour independently of other players' payoffs/actions. $O(\log n)$
rounds/queries are required. We also show how to obtain a slight improvement
over $\frac{1}{8}$, by introducing a small amount of communication between the
players.
  Finally, we give extension of our results to large games with more than two
strategies per player, and alternative largeness parameters.
