Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with correlated equilibrium:
TR17-061 | 3rd April 2017
Anat Ganor, Karthik C. S.

Communication Complexity of Correlated Equilibrium in Two-Player Games

We show a communication complexity lower bound for finding a correlated equilibrium of a two-player game. More precisely, we define a two-player $N \times N$ game called the 2-cycle game and show that the randomized communication complexity of finding a 1/poly($N$)-approximate correlated equilibrium of the 2-cycle game is $\Omega(N)$. For ... more >>>

TR17-071 | 14th April 2017
Young Kun Ko, Arial Schvartzman

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

Revisions: 1

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 ... more >>>

ISSN 1433-8092 | Imprint