2022/07/20 by Paul W. Goldberg, Goldberg, Paul W., Matthew J. Katzman +1
Decision Sciences · Economics, Econometrics and Finance · #Game Theory and Applications #Economic theories and models #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.2207.09962
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 pure ε-approximate 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 pure ε-approximate 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.