  Lipschitz games, in which there is a limit $\lambda$ (the Lipschitz value of
the game) on how much a player's payoffs may change when some other player
deviates, were introduced about 10 years ago by Azrieli and Shmaya. They showed
via the probabilistic method that $n$-player Lipschitz games with $m$
strategies per player have pure $\epsilon$-approximate Nash equilibria, for
$\epsilon\geq\lambda\sqrt{8n\log(2mn)}$. Here we provide the first hardness
result for the corresponding computational problem, showing that even for a
simple class of Lipschitz games (Lipschitz polymatrix games), finding pure
$\epsilon$-approximate equilibria is PPAD-complete, for suitable pairs of
values $(\epsilon(n), \lambda(n))$. Novel features of this result include both
the proof of PPAD hardness (in which we apply a population game reduction from
unrestricted polymatrix games) and the proof of containment in PPAD (by
derandomizing the selection of a pure equilibrium from a mixed one). In fact,
our approach implies containment in PPAD for any class of Lipschitz games where
payoffs from mixed-strategy profiles can be deterministically computed.
