The complexity of solution concepts in Lipschitz games

Thesis

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 via the probabilistic method that n-player Lipschitz games with m strategies per player have pure 𝜖-approximate Nash equilibria, for 𝜖 ≥ λ√8n log(2mn). They left open, however, the question of how hard it is to find such an equilibrium. In this work, we develop an efficient reduction from more general games to Lipschitz games. We use this reduction to study both the query and computational complexity of algorithms finding λ-approximate pure Nash equilibria of λ-Lipschitz games and related classes.

We show a query lower bound exponential in nλ/𝜖 against randomized algorithms finding 𝜖- approximatepure Nash equilibria of n-player, λ-Lipschitz games. We additionally present the first PPAD-completeness result for finding pure Nash equilibria in a class of finite, non-Bayesian games (we show this for λ-Lipschitz polymatrix games for suitable pairs of values 𝜖 and λ) in which both the proof of PPAD-hardness and the proof of containment in PPAD require novel approaches (in fact, our approach implies containment in PPAD for any class of Lipschitz games in which payoffs from mixed-strategy profiles can be deterministically computed), and present a definition of “randomized PPAD”. We define and subsequently analyze the class of “Multi-Lipschitz games”, a generalization of Lipschitz games involving player-specific Lipschitz parameters in which the value of interest appears to be the average of the individual Lipschitz parameters. We discuss a dichotomy of the deterministic query complexity of finding 𝜖-approximate Nash equilibria of general games and, subsequently, a query lower bound for λ-Lipschitz games in which any non-trivial value of 𝜖 requires exponentially-many queries to achieve. We examine which parts of this extend to the concepts of approximate correlated and coarse correlated equilibria, and in the process generalize the edge-isoperimetric inequalities to generalizations of the hypercube. Finally, we improve the block update algorithm presented by Goldberg and Marmolejo to break the potential boundary of a 0.75-approximation factor, presenting a randomized algorithm achieving a 0.7368-approximate Nash equilibrium making polynomially-many profile queries of an n-player 1/n−1 -Lipschitz game with an unbounded number of actions.

Authors: Katzman, M

• DOI: 10.5287/ora-5rqe1mkzg
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Keywords: PPAD; Lipschitz games; Computational complexity; Query complexity
• Subjects: Game theory; Computational complexity