Pure-Circuit: Strong Inapproximability for PPAD
Preprint
Abstract
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 < 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 $\varepsilon$-well-supported Nash equilibria in two-action polymatrix games, as well as for finding approximate equilibria in threshold games.
Keywords
All Related Versions
This publication has 30 references indexed in Scilit:
- Web and Internet Economics2022
- The Hairy Ball problem is PPAD-completeJournal of Computer and System Sciences, 2021
- Settling the Complexity of Computing Approximate Two-Player Nash Equilibria2016
- Computing Approximate Nash Equilibria in Polymatrix GamesAlgorithmica, 2015
- On the complexity of 2D discrete fixed point problemTheoretical Computer Science, 2009
- Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities2009
- The Complexity of Computing a Nash EquilibriumSIAM Journal on Computing, 2009
- The complexity of equilibria: Hardness results for economies via a correspondence with gamesTheoretical Computer Science, 2008
- On the complexity of the parity argument and other inefficient proofs of existenceJournal of Computer and System Sciences, 1994
- Neuer beweis für die invarianz der dimensionszahl und des gebietesAbhandlungen aus dem Mathematischen Seminar der Universitat Hamburg, 1928