2016/08/23 by Yakov Babichenko, Aviad Rubinstein, Babichenko, Yakov +1 · 1 voice
Computer Science · #Computational Complexity (cs.CC) #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #cs.CC #cs.GT
paper · pdf · doi:10.48550/arxiv.1608.06580
arxiv published 2016/08/23 · arxiv updated 2016/09/13
For a constant ε, we prove a poly(N) lower bound on the (randomized) communication complexity of ε-Nash equilibrium in two-player NxN games. For n-player binary-action games we prove an exp(n) lower bound for the (randomized) communication complexity of (ε,ε)-weak approximate Nash equilibrium, which is a profile of mixed actions such that at least (1-ε)-fraction of the players are ε-best replying.