The Communication Complexity of Local Search
share
We study the following communication variant of local search. There is some fixed, commonly known graph G. Alice holds f_A and Bob holds f_B, both are functions that specify a value for each vertex. The goal is to find a local maximum of f_A+f_B with respect to G, i.e., a vertex v for which (f_A+f_B)(v)≥ (f_A+f_B)(u) for every neighbor u of v. Our main result is that finding a local maximum requires polynomial (in the number of vertices) bits of communication. The result holds for the following families of graphs: three dimensional grids, hypercubes, odd graphs, and degree 4 graphs. We provide applications of our main result in two domains, exact potential games and combinatorial auctions. First, we show that finding a pure Nash equilibrium in 2-players N-action exact potential games requires polynomial (in N) communication. We also show that finding a pure Nash equilibrium in n-player 2-action exact potential games requires exponential (in n) communication. The second domain that we consider is combinatoiral auctions, in which we prove that finding a local maximum of a combinatorial auctions requires exponential (in the number of items) communication even when the valuations are submodular. Each one of the results demonstrates an exponential separation between the non-deterministic communication complexity and the randomized communication complexity of a total search problem.
READ FULL TEXT