Pure-Circuit: Strong Inapproximability for PPAD
share
The current state-of-the-art methods for showing inapproximability in PPAD arise from the ε-Generalized-Circuit (ε-GCircuit) problem. Rubinstein (2018) showed that there exists a small unknown constant ε for which ε-GCircuit is PPAD-hard, and subsequent work has shown hardness results for other problems in PPAD by using ε-GCircuit as an intermediate problem. We introduce Pure-Circuit, a new intermediate problem for PPAD, which can be thought of as ε-GCircuit pushed to the limit as ε→ 1, and we show that the problem is PPAD-complete. We then prove that ε-GCircuit is PPAD-hard for all ε < 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 ε-well-supported Nash equilibria in two-action polymatrix games, as well as for finding approximate equilibria in threshold games.
READ FULL TEXT