TR16-055 Authors: Tim Roughgarden, Omri Weinstein

Publication: 12th April 2016 20:46

Downloads: 2239

Keywords:

We study the two-party communication complexity of finding an approximate Brouwer fixed point of a composition

of two Lipschitz functions $g\circ f : [0,1]^n \to [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 \emph{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:

(i) The deterministic two-party communication complexity of finding an $\epsilon=\Omega(1/\log^2 N)$-approximate

Nash equilibrium in an $N\times N$ bimatrix game (where each player knows only his own payoff matrix) is at least

$N^\gamma$ for some constant $\gamma>0$. (In contrast, the \emph{nondeterministic} communication complexity

of this problem is only $O(\log^6 N)$).

(ii) The deterministic (Number-In-Hand) multiparty communication complexity of finding an $\epsilon=\Omega(1)$-Nash

equilibrium in a $k$-player constant-action game is at least $2^{\Omega(k/\log k)}$ (while the nondeterministic

communication complexity is only $O(k)$).