Deligkas, Argyrios and Fearnley, John and Hollender, Alexandros and Melissourgos, Themistoklis (2024) Pure-Circuit: Tight Inapproximability for PPAD. Journal of the ACM, 71 (5). pp. 1-48. DOI https://doi.org/10.1145/3678166 (In Press)
Deligkas, Argyrios and Fearnley, John and Hollender, Alexandros and Melissourgos, Themistoklis (2024) Pure-Circuit: Tight Inapproximability for PPAD. Journal of the ACM, 71 (5). pp. 1-48. DOI https://doi.org/10.1145/3678166 (In Press)
Deligkas, Argyrios and Fearnley, John and Hollender, Alexandros and Melissourgos, Themistoklis (2024) Pure-Circuit: Tight Inapproximability for PPAD. Journal of the ACM, 71 (5). pp. 1-48. DOI https://doi.org/10.1145/3678166 (In Press)
Abstract
<jats:p> The current state-of-the-art methods for showing inapproximability in <jats:sans-serif>PPAD</jats:sans-serif> arise from the ɛ-Generalized-Circuit (ɛ- <jats:sc>GCircuit</jats:sc> ) problem. Rubinstein (2018) showed that there exists a small unknown constant ɛ for which ɛ- <jats:sc>GCircuit</jats:sc> is <jats:sans-serif>PPAD</jats:sans-serif> -hard, and subsequent work has shown hardness results for other problems in <jats:sans-serif>PPAD</jats:sans-serif> by using ɛ- <jats:sc>GCircuit</jats:sc> as an intermediate problem. </jats:p> <jats:p> We introduce <jats:sc>Pure-Circuit</jats:sc> , a new intermediate problem for <jats:sans-serif>PPAD</jats:sans-serif> , which can be thought of as ɛ- <jats:sc>GCircuit</jats:sc> pushed to the limit as ɛ → 1, and we show that the problem is <jats:sans-serif>PPAD</jats:sans-serif> -complete. We then prove that ɛ- <jats:sc>GCircuit</jats:sc> is <jats:sans-serif>PPAD</jats:sans-serif> -hard for all ɛ < 1/10 by a reduction from <jats:sc>Pure-Circuit</jats:sc> , and thus strengthen all prior work that has used <jats:sc>GCircuit</jats:sc> as an intermediate problem from the existential-constant regime to the large-constant regime. </jats:p> <jats:p> We show that stronger inapproximability results can be derived by reducing directly from <jats:sc>Pure-Circuit</jats:sc> . 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. </jats:p>
Item Type: | Article |
---|---|
Divisions: | Faculty of Science and Health Faculty of Science and Health > Computer Science and Electronic Engineering, School of |
SWORD Depositor: | Unnamed user with email elements@essex.ac.uk |
Depositing User: | Unnamed user with email elements@essex.ac.uk |
Date Deposited: | 10 Jul 2024 08:50 |
Last Modified: | 24 Oct 2024 12:17 |
URI: | http://repository.essex.ac.uk/id/eprint/38497 |
Available files
Filename: Pure-Circuit_Tight_Inapproximability_for_PPAD.pdf