Tight Inapproximability for Generalized Circuits

Generalized circuits are a fundamental tool for establishing PPAD-hardness and membership of approximate equilibrium problems. Despite their importance, the complexity of finding approximate solutions has remained unresolved for a wide range of approximation parameters. We settle this question by establishing a tight threshold at $\epsilon =1\mathrm{/}6$. Specifically, we prove that $\epsilon$-GCircuit is PPAD-complete for every constant $0<\epsilon <1\mathrm{/}6$, even when restricted to four gate types, and polynomial-time solvable for every constant $\epsilon \ge 1\mathrm{/}6$. This closes the gap between the previously known hardness bound of $1\mathrm{/}10$ and the polynomial-time solvability bound of $1\mathrm{/}2$. We further investigate the relaxation in which a fraction $\delta$ of the gates may be violated. We establish polynomial-time solvability of $(\epsilon ,\delta )$-GCircuit for every constant $\epsilon >0$ and $\delta >1\mathrm{/}5$, and of the fan-out-one formulations of $\delta$-Pure-Circuit for every constant $\delta >1\mathrm{/}8$. These results follow from a decomposition theorem for directed graphs of maximum in-degree two and establish that the PCP-for-PPAD conjecture cannot be true for the aforementioned values of $\epsilon$ and $\delta$, unless PPAD = P. To showcase the contribution of our positive results, we apply them to a variety of problems in algorithmic game theory, including public goods games, financial networks, Bayesian, polymatrix, and graphical games, and obtain improved approximation guarantees.