2017/04/04 by Anat Ganor, Ganor, Anat, C. S. Karthik +1
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Applications #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.1704.01104
openalex publication_date 2017/04/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.