Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR17-071 | 9th May 2017 06:10

Bounds for the Communication Complexity of Two-Player Approximate Correlated Equilibria

RSS-Feed




Revision #1
Authors: Young Kun Ko, Arial Schvartzman
Accepted on: 9th May 2017 06:10
Downloads: 1206
Keywords: 


Abstract:

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.



Changes to previous version:

Improved Lower Bound, Fixed Upper Bound, Name Typo fixed


Paper:

TR17-071 | 14th April 2017 23:28

Bounds for the Communication Complexity of Two-Player Approximate Correlated Equilibria





TR17-071
Authors: Young Kun Ko, Arial Schvartzman
Publication: 23rd April 2017 19:09
Downloads: 921
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint