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 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 ( 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.
展开▼
