Pure-Circuit: Strong 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 \lt 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 a direct reduction from PURE-CIRCUIT. In particular, we prove that finding an $\varepsilon$-well-supported Nash equilibrium in a polymatrix game is PPAD-hard for all $\varepsilon \lt 1/3$, and that this result is tight for two-action games.