Pure-Circuit: Tight Inapproximability for PPAD

The current state-of-the-art methods for showing inapproximability in PPAD arise from the varepsilon-Generalized-Circuit (varepsilon-GCircuit) problem. Rubinstein (2018) showed that there exists a small unknown constant varepsilon for which varepsilon-GCircuit is PPAD-hard, and subsequent work has shown hardness results for other problems in PPAD by using varepsilon-GCircuit as an intermediate problem. We introduce Pure-Circuit, a new intermediate problem for PPAD, which can be thought of as varepsilon-GCircuit pushed to the limit as varepsilon rightarrow 1, and we show that the problem is PPAD-complete. We then prove that varepsilon-GCircuit is PPAD-hard for all varepsilon < 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.