  Nearly a decade ago, Azrieli and Shmaya introduced the class of
$\lambda$-Lipschitz games in which every player's payoff function is
$\lambda$-Lipschitz with respect to the actions of the other players. They
showed that such games admit $\epsilon$-approximate pure Nash equilibria for
certain settings of $\epsilon$ and $\lambda$. They left open, however, the
question of how hard it is to find such an equilibrium. In this work, we
develop a query-efficient reduction from more general games to Lipschitz games.
We use this reduction to show a query lower bound for any randomized algorithm
finding $\epsilon$-approximate pure Nash equilibria of $n$-player,
binary-action, $\lambda$-Lipschitz games that is exponential in
$\frac{n\lambda}{\epsilon}$. In addition, we introduce ``Multi-Lipschitz
games,'' a generalization involving player-specific Lipschitz values, and
provide a reduction from finding equilibria of these games to finding
equilibria of Lipschitz games, showing that the value of interest is the sum of
the individual Lipschitz parameters. Finally, we provide an exponential lower
bound on the deterministic query complexity of finding $\epsilon$-approximate
correlated equilibria of $n$-player, $m$-action, $\lambda$-Lipschitz games for
strong values of $\epsilon$, motivating the consideration of explicitly
randomized algorithms in the above results. Our proof is arguably simpler than
those previously used to show similar results.
