Tight Inapproximability for Graphical Games

09/30/2022
by   Argyrios Deligkas, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset