# On the Communication Complexity of Approximate Nash Equilibria

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Feb 2013.

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

- [Provably Efficient Policy Optimization for Two-Player Zero-Sum Markov Games](https://mlsanity.com/paper/2102.08903/) (2021)
- [Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games](https://mlsanity.com/paper/2303.12287/) (2023)
- [Smooth Nash Equilibria: Algorithms and Complexity](https://mlsanity.com/paper/2309.12226/) (2023)
- [Algorithmic Collusion and the Complexity of Information-Value-Free Equilibria](https://mlsanity.com/paper/2609.22757/) (2026)
- [An active learning method for solving competitive multi-agent decision-making and control problems](https://mlsanity.com/paper/2212.12561/) (2022)

## Abstract (arXiv)

We study the problem of computing approximate Nash equilibria of bimatrix games, in a setting where players initially know their own payoffs but not the payoffs of the other player. In order for a solution of reasonable quality to be found, some amount of communication needs to take place between the players. We are interested in algorithms where the communication is substantially less than the contents of a payoff matrix, for example logarithmic in the size of the matrix. When the communication is polylogarithmic in the number of strategies n, we show how to obtain epsilon-approximate Nash equilibria for epsilon approximately 0.438, and for well-supported approximate equilibria we obtain epsilon approximately 0.732. For one-way communication we show that epsilon=1/2 is achievable, but no constant improvement over 1/2 is possible, even with unlimited one-way communication. For well-supported equilibria, no value of epsilon less than 1 is achievable with one-way communication. When the players do not communicate at all, epsilon-Nash equilibria can be obtained for epsilon=3/4, and we also give a lower bound of slightly more than 1/2 on the lowest constant epsilon achievable.