Pure-Circuit: tight inapproximability for PPAD

Journal article

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 ε < 1/10 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.

Authors: Deligkas, A; Fearnley, J; Hollender, A; Melissourgos, T

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Association for Computing Machinery
• Journal: Journal of the ACM
• Volume: 71
• Issue: 5
• Article number: 31
• Publication date: 2024-07-15
• Acceptance date: 2024-05-28
• DOI: 10.1145/3678166
• EISSN: 1557-735X
• ISSN: 0004-5411
• Language: English
• Keywords: Nash equilibrium; TFNP; PPAD; generalized circuit; FFR; approximation