Pure-Circuit: Tight Inapproximability for PPAD

Abstract

The current state-of-the-art methods for showing inapproximability in PPAD arise from the $\epsilon$-Generalized-Circuit ($\epsilon$-GCircuit) problem. Rubinstein (2018) showed that there exists a small unknown constant $\epsilon$ for which $\epsilon$-GCircuit is PPAD-hard, and subsequent work has shown hardness results for other problems in PPAD by using $\epsilon$-GCircuit as an intermediate problem. We introduce Pure-Circuit, a new intermediate problem for PPAD, which can be thought of as $\epsilon$-GCircuit pushed to the limit as $\epsilon \to 1$, and we show that the problem is PPAD-complete. We then prove that $\epsilon$-GCircuit is PPAD-hard for all $\epsilon <0.1$ by a reduction from Pure-Circuit, and thus strengthen all prior work that has used GCircuit as an intermediate problem from the existential-constant regime to the large-constant regime. We show that stronger inapproximability results can be derived by reducing directly from Pure-Circuit. In particular, we prove tight inapproximability results for computing approximate Nash equilibria and approximate well-supported Nash equilibria in graphical games, for finding approximate well-supported Nash equilibria in polymatrix games, and for finding approximate equilibria in threshold games.

This journal version combines the results of two prior conference papers: "Pure-Circuit: Strong Inapproximability for PPAD" published in FOCS 2022, and "Tight Inapproximability for Graphical Games" (arXiv:2209.15151) published in AAAI 2023

References in corpus (1)

• On the Complexity of Equilibrium Computation in First-Price Auctions