Generalized circuits have a precise difficulty cutoff for approximate solutions
Tight Inapproximability for Generalized Circuits
Computer Science and Game TheoryComputational Complexity
Summary
Figuring out approximate solutions to generalized circuits is important for understanding certain hard computer problems. The authors found a clear boundary: when the allowed error is less than 1/6, the problem is hard to solve; if it’s 1/6 or more, it can be solved quickly. They also studied cases where some parts don’t need to be exactly right and showed when these are easy or still hard. Their work narrows down the complexity of these problems and helps improve algorithms in game theory and finance models.
What this means in practice
- •For algorithm designers: Use precise complexity thresholds to optimize algorithms for equilibrium problems in games and economic networks.
- •For financial modelers: Improve approximations for stability and risk analysis in financial networks based on new hardness characterizations.
A theory result. No direct application yet.
Authors
Panagiotis Kanellopoulos, Themistoklis Melissourgos
Abstract
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 $\varepsilon=1/6$. Specifically, we prove that $\varepsilon$-GCircuit is PPAD-complete for every constant $0<\varepsilon<1/6$, even when restricted to four gate types, and polynomial-time solvable for every constant $\varepsilon\ge1/6$. This closes the gap between the previously known hardness bound of $1/10$ and the polynomial-time solvability bound of $1/2$. We further investigate the relaxation in which a fraction $δ$ of the gates may be violated. We establish polynomial-time solvability of $(\varepsilon,δ)$-GCircuit for every constant $\varepsilon>0$ and $δ>1/5$, and of the fan-out-one formulations of $δ$-Pure-Circuit for every constant $δ>1/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 $\varepsilon$ and $δ$, 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.