Tight Inapproximability for Graphical Games

Deligkas, Argyrios, Fearnley, John, Hollender, Alexandros and Melissourgos, Themistoklis (2023) Tight Inapproximability for Graphical Games. In: AAAI 2023.

Text
Settling_Graphical_Games.pdf - Author Accepted Manuscript
Download (475kB) | Preview

Official URL: http://dx.doi.org/10.1609/aaai.v37i5.25695

Abstract

<jats:p>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 ε is in [0,1]. We prove that computing an ε-NE is PPAD-complete for any constant ε smaller than 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 ε smaller than 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.</jats:p>

Item Type:	Conference or Workshop Item (Unspecified)
Depositing User:	Symplectic Admin
Date Deposited:	22 Nov 2022 16:53
Last Modified:	15 Mar 2024 05:23
DOI:	10.1609/aaai.v37i5.25695
Related URLs:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3166323