Deligkas, Argyrios, Fearnley, John, Alexandros, Hollender and Themistoklis, Melissourgos
(2022)
Pure-Circuit: Strong Inapproximability for PPAD.
In: FOCS 2022, 2022-10-31 - 2022-11-3.
|
Text
strong_inapproximability_PPAD(1).pdf - Author Accepted Manuscript Download (366kB) | Preview |
Abstract
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 ? < 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 a direct reduction from PURE-CIRCUIT. In particular, we prove that finding an ?-well-supported Nash equilibrium in a polymatrix game is PPAD-hard for all ? < 1/3, and that this result is tight for two-action games.
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Uncontrolled Keywords: | TFNP, PPAD, approximation, Nash equilibrium, polymatrix games, generalized circuit |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 07 Oct 2022 10:24 |
| Last Modified: | 31 Aug 2023 09:39 |
| DOI: | 10.1109/FOCS54457.2022.00022 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3165033 |
Dimensions
Dimensions
