Pure-Circuit: Tight Inapproximability for PPAD

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