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