Pure-Circuit: Tight Inapproximability for PPAD
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910600148287488 |
|---|---|
| author | Deligkas, Argyrios Fearnley, John Hollender, Alexandros Melissourgos, Themistoklis |
| author_facet | Deligkas, Argyrios Fearnley, John Hollender, Alexandros Melissourgos, Themistoklis |
| contents | 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 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2209_15149 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Pure-Circuit: Tight Inapproximability for PPAD Deligkas, Argyrios Fearnley, John Hollender, Alexandros Melissourgos, Themistoklis Computational Complexity Computer Science and Game Theory 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 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. |
| title | Pure-Circuit: Tight Inapproximability for PPAD |
| topic | Computational Complexity Computer Science and Game Theory |
| url | https://arxiv.org/abs/2209.15149 |