Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR17-061 | 3rd April 2017 20:18

Communication Complexity of Correlated Equilibrium in Two-Player Games

RSS-Feed




TR17-061
Authors: Anat Ganor, Karthik C. S.
Publication: 10th April 2017 04:21
Downloads: 867
Keywords: 


Abstract:

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 small approximation values, this answers an open question of Babichenko and Rubinstein (STOC 2017). Our lower bound is obtained via a direct reduction from the unique set disjointness problem.



ISSN 1433-8092 | Imprint