Nearly a decade ago, Azrieli and Shmaya introduced the class of λ-Lipschitz games in which every player's payoff function is λ-Lipschitz with respect to the actions of the other players. They showed that such games admit ϵ-approximate pure Nash equilibria for certain settings of ϵ and λ. 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 ϵ-approximate pure Nash equilibria of n-player, binary-action, λ-Lipschitz games that is exponential in nλ/ϵ. 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 average of the individual Lipschitz parameters. Finally, we provide an exponential lower bound on the deterministic query complexity of finding ϵ-approximate Nash equilibria of n-player, m-action, λ-Lipschitz games for strong values of ϵ, motivating the consideration of explicitly randomized algorithms in the above results.

Lipschitz games, in which there is a limit λ (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 ϵ-approximate pure Nash equilibria, for ϵ≥λ8nlog⁡(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 ϵ-approximate pure equilibria is PPAD-complete, for suitable pairs of values ϵ(n), λ(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. When instead considering games where only payoffs from pure action profiles can be deterministically computed, we provide two equivalent definitions of “randomized PPAD” and show that the generalized problem belongs to this class.