# Communication complexity of approximate Nash equilibria

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Aug 2016.

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

- [Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games](https://mlsanity.com/paper/2111.06008/) (2021)
- [Fast swap regret minimization and applications to approximate correlated equilibria](https://mlsanity.com/paper/2310.19647/) (2023)

## Abstract (arXiv)

For a constant ε, we prove a poly(N) lower bound on the (randomized) communication complexity of ε-Nash equilibrium in two-player NxN games. For n-player binary-action games we prove an exp(n) lower bound for the (randomized) communication complexity of (ε,ε)-weak approximate Nash equilibrium, which is a profile of mixed actions such that at least (1-ε)-fraction of the players are ε-best replying.