| Summary: | <p>The current state-of-the-art methods for showing inapproximability in <span data-="">PPAD</span> arise from the ε-Generalized-Circuit (ε-<span data-="">GCircuit</span>) problem. Rubinstein (2018) showed that there exists a small unknown constant ε for which ε-<span data-="">GCircuit</span> is <span data-="">PPAD</span>-hard, and subsequent work has shown hardness results for other problems in <span data-="">PPAD</span> by using ε-<span data-="">GCircuit</span> as an intermediate problem.</p>
<p>We introduce <span data-="">Pure-Circuit</span>, a new intermediate problem for <span data-="">PPAD</span>, which can be thought of as ε-<span data-="">GCircuit</span> pushed to the limit as ε → 1, and we show that the problem is <span data-="">PPAD</span>-complete. We then prove that ε-<span data-="">GCircuit</span> is <span data-="">PPAD</span>-hard for all ε < 1/10 by a reduction from <span data-="">Pure-Circuit</span>, and thus strengthen all prior work that has used <span data-="">GCircuit</span> as an intermediate problem from the existential-constant regime to the large-constant regime.</p>
<p>We show that stronger inapproximability results can be derived by reducing directly from <span data-="">Pure-Circuit</span>. 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.</p>
|
|---|