Deligkas, Argyrios and Fearnley, John and Hollender, Alexandros and Melissourgos, Themistoklis (2023) Tight Inapproximability for Graphical Games. In: 37th AAAI Conference on Artificial Intelligence, 2023-02-07 - 2023-02-14, Washington DC, USA.
Deligkas, Argyrios and Fearnley, John and Hollender, Alexandros and Melissourgos, Themistoklis (2023) Tight Inapproximability for Graphical Games. In: 37th AAAI Conference on Artificial Intelligence, 2023-02-07 - 2023-02-14, Washington DC, USA.
Deligkas, Argyrios and Fearnley, John and Hollender, Alexandros and Melissourgos, Themistoklis (2023) Tight Inapproximability for Graphical Games. In: 37th AAAI Conference on Artificial Intelligence, 2023-02-07 - 2023-02-14, Washington DC, USA.
Abstract
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.
Item Type: | Conference or Workshop Item (Paper) |
---|---|
Additional Information: | Published proceedings: _not provided_ |
Uncontrolled Keywords: | Game Theory; Equilibrium |
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: | 13 Jan 2023 11:10 |
Last Modified: | 16 May 2024 21:36 |
URI: | http://repository.essex.ac.uk/id/eprint/34180 |
Available files
Filename: Tight Inapproximability for Graphical Games.pdf