In the recent paper of~\cite{BR16}, the authors show that, for any constant $10^{-15} > \varepsilon > 0$ the communication complexity of $\varepsilon$-approximate Nash equilibria in $2$-player $n \times n$ games is $n^{\Omega(\varepsilon)}$, resolving the long open problem of whether or not there exists a polylogarithmic communication protocol. In this paper we address an open question they pose regarding the communication complexity of $2$-player $\varepsilon$-approximate correlated equilibria.

For our upper bounds, we provide a communication protocol that outputs a $\varepsilon$-approximate correlated equilibrium for multiplayer multi-action games after exchanging $\tilde{O}(m n^4 \varepsilon^{-4})$ bits, saving over the naive $O(m n^m)$-bits protocol when the number of players is large.

For our lower bounds, we exhibit a simple two player game that has a logarithmic information lower bound: for any $\Omega(n^{-1}) < \varepsilon < \frac{1}{10}$, the two players need to communicate $\Omega(\varepsilon^{-1/2} \log n)$-bits of information to compute any $\varepsilon$-correlated equilibrium in the game. For the $m$-players, $2$-action setting we show a lower bound of $\Omega(m)$ bits, which matches the upper bound up to polylogarithmic terms and shows that the linear dependence on the number of players is unavoidable.

Improved Lower Bound, Fixed Upper Bound, Name Typo fixed

In the recent paper of~\cite{BR16}, the authors show that, for any constant $10^{-15} > \varepsilon > 0$ the communication complexity of $\varepsilon$-approximate Nash equilibria in $2$-player $n \times n$ games is $n^{\Omega(\varepsilon)}$, resolving the long open problem of whether or not there exists a polylogarithmic communication protocol. In this paper we address an open question they pose regarding the communication complexity of $2$-player $\varepsilon$-approximate correlated equilibria.

For our upper bounds, we provide a communication protocol that outputs a $\varepsilon$-approximate correlated equilibrium after exchanging $\tilde{O}(n \varepsilon^{-2})$ bits, saving over the naive protocol which requires $O(n^2)$-bits. This is in sharp contrast to Nash equilibria where for sufficiently small constant $\varepsilon$, no $o(n^2)$-communication protocol is known. In the $m$-player, $n$-action setting, our protocol can be extended to a $\tilde{O}(nm)$-bit protocol.

For our lower bounds, we exhibit a simple two player game that has a logarithmic information lower bound: for any constant $\varepsilon < \frac{1}{8}$ the two players need to communicate $\Omega(\log n)$-bits of information to compute any $\varepsilon$-correlated equilibrium in the game. For the $m$-players, $2$-action setting we show a lower bound of $\Omega(m)$ bits, which matches the upper bound we provide up to polylogarithmic terms and shows that the dependence on the number of players is unavoidable.