# Tight Inapproximability for Graphical Games

arXiv: https://arxiv.org/abs/2209.15151 · HTML: https://mlsanity.com/paper/2209.15151/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Sep 2022.

## Built on by (most cited first, 2 of 2)

- [Expected Variational Inequalities](https://mlsanity.com/paper/2502.18605/) (2025)
- [On the Computational Complexity of Performative Prediction](https://mlsanity.com/paper/2601.20180/) (2026)

## Abstract (arXiv)

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 ∈ [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.