In the recent paper of~\cite{BR16}, the authors show that, for any constant \varepsilon > 0"> 1 0 − 15 0 the communication complexity of -approximate Nash equilibria in 2 -player n n games is n ( ) , 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 -approximate correlated equilibria.

For our upper bounds, we provide a communication protocol that outputs a -approximate correlated equilibrium for multiplayer multi-action games after exchanging O ( m n 4 − 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 ( n − 1 ) 1 10 , the two players need to communicate ( − 1 2 log n ) -bits of information to compute any -correlated equilibrium in the game. For the m -players, 2 -action setting we show a lower bound of ( m ) bits, which matches the upper bound up to polylogarithmic terms and shows that the linear dependence on the number of players is unavoidable.