Tight Inapproximability for Graphical Games
Authors: Argyrios Deligkas, John Fearnley, Alexandros Hollender, Themistoklis Melissourgos
AAAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We provide a complete characterization for the computational complexity of finding approximate equilibria in two-action graphical games. We consider the two most well-studied approximation notions: ε-Nash equilibria (ε-NE) and ε-well-supported Nash equilibria (ε-WSNE), where ε [0, 1]. We prove that computing an ε-NE is PPAD-complete for any constant ε < 1/2, while a very simple algorithm (namely, letting all players mix uniformly between their two actions) yields a 1/2-NE. On the other hand, we show that computing an ε-WSNE is PPAD-complete for any constant ε < 1, while a 1-WSNE is trivial to achieve, because any strategy profile is a 1-WSNE. All of our lower bounds immediately also apply to graphical games with more than two actions per player. |
| Researcher Affiliation | Academia | Royal Holloway, United Kingdom University of Liverpool, United Kingdom EPFL, Switzerland University of Essex, United Kingdom |
| Pseudocode | No | The paper describes algorithms in prose (e.g., 'The algorithm proceeds in two steps. In the first step...'), but does not include structured pseudocode or clearly labeled algorithm blocks. |
| Open Source Code | No | The paper does not contain any explicit statements or links indicating that open-source code for the described methodology is provided. |
| Open Datasets | No | This paper is theoretical and does not conduct experiments on datasets, thus no information on publicly available datasets or access is relevant or provided. |
| Dataset Splits | No | This paper is theoretical and does not involve experimental validation with dataset splits. |
| Hardware Specification | No | This paper is theoretical and does not describe experiments requiring hardware, thus no hardware specifications are provided. |
| Software Dependencies | No | This paper is theoretical and does not mention any specific software dependencies with version numbers for experimental replication. |
| Experiment Setup | No | This paper is theoretical and does not include details about an experimental setup, hyperparameters, or training configurations. |