
arXiv: 2209.15149
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.
FOS: Computer and information sciences, TFNP, Networks and circuits as models of computation; circuit complexity, 610, Computational Complexity (cs.CC), Approximation algorithms, Nash equilibrium, 620, Computer Science - Computational Complexity, generalized circuit, Computer Science - Computer Science and Game Theory, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), PPAD, Algorithmic game theory and complexity, approximation, Computer Science and Game Theory (cs.GT)
FOS: Computer and information sciences, TFNP, Networks and circuits as models of computation; circuit complexity, 610, Computational Complexity (cs.CC), Approximation algorithms, Nash equilibrium, 620, Computer Science - Computational Complexity, generalized circuit, Computer Science - Computer Science and Game Theory, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), PPAD, Algorithmic game theory and complexity, approximation, Computer Science and Game Theory (cs.GT)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
