  Nash equilibrium is a central concept in game theory. Several Nash solvers
exist, yet none scale to normal-form games with many actions and many players,
especially those with payoff tensors too big to be stored in memory. In this
work, we propose an approach that iteratively improves an approximation to a
Nash equilibrium through joint play. It accomplishes this by tracing a
previously established homotopy that defines a continuum of equilibria for the
game regularized with decaying levels of entropy. This continuum asymptotically
approaches the limiting logit equilibrium, proven by McKelvey and Palfrey
(1995) to be unique in almost all games, thereby partially circumventing the
well-known equilibrium selection problem of many-player games. To encourage
iterates to remain near this path, we efficiently minimize average deviation
incentive via stochastic gradient descent, intelligently sampling entries in
the payoff tensor as needed. Monte Carlo estimates of the stochastic gradient
from joint play are biased due to the appearance of a nonlinear max operator in
the objective, so we introduce additional innovations to the algorithm to
alleviate gradient bias. The descent process can also be viewed as repeatedly
constructing and reacting to a polymatrix approximation to the game. In these
ways, our proposed approach, average deviation incentive descent with adaptive
sampling (ADIDAS), is most similar to three classical approaches, namely
homotopy-type, Lyapunov, and iterative polymatrix solvers. The lack of local
convergence guarantees for biased gradient descent prevents guaranteed
convergence to Nash, however, we demonstrate through extensive experiments the
ability of this approach to approximate a unique Nash in normal-form games with
as many as seven players and twenty one actions (several billion outcomes) that
are orders of magnitude larger than those possible with prior algorithms.
