Tight Inapproximability for Graphical Games

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: $\epsilon$-Nash equilibria ($\epsilon$-NE) and $\epsilon$-well-supported Nash equilibria ($\epsilon$-WSNE), where $\epsilon \in [0,1]$. We prove that computing an $\epsilon$-NE is PPAD-complete for any constant $\epsilon <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 $\epsilon$-WSNE is PPAD-complete for any constant $\epsilon <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.