On the Communication Complexity of Approximate Fixed Points
Tim Roughgarden, Omri Weinstein · 2016
We study the two-party communication complexity of finding an approximate Brouwer fixed point of a composition of two Lipschitz functions g o f: [0,1]n→ [0,1]n, where Alice holds f and Bob holds g. We prove an exponential (in n) lower bound on the deterministic communication complexity of this problem. Our technical approach is to adapt the Raz-McKenzie simulation theorem (FOCS 1999) into geometric settings, thereby "smoothly lifting" the deterministic query lower bound for finding an approximate fixed point (Hirsch, Papadimitriou and Vavasis, Complexity 1989) from the oracle model to the two-party model. Our results also suggest an approach to the well-known open problem of proving strong lower bounds on the communication complexity of computing approximate Nash equilibria. Specifically, we show that a slightly "smoother" version of our fixed-point computation lower bound (by an absolute constant factor) would imply that: The deterministic two-party communication complexity of finding an ∈ = Ω(1/log2N)-approximate Nash equilibrium in an N × N bimatrix game (where each player knows only his own payoff matrix) is at least Nγfor some constant γ > 0. (In contrast, the nondeterministic communication complexity of this problem is only O(log6N)). ; The deterministic (Number-In-Hand) multiparty communication complexity of finding an ∈ = Ω(1)-Nash equilibrium in a k-player constant-action game is at least 2Ω(k/log k)(while the nondeterministic communication complexity is only O(k)).