Hardness of Approximation Between P and NP. Aviad Rubinstein

Чтение книги онлайн.

СКАЧАТЬ

       From Query Complexity to Communication Complexity

      We use a recent simulation theorem to “lift” our randomized query complexity lower bound to a randomized communication complexity bound.

      The simulated communicationally hard problem has the following form. For each v ∈ V, Alice holds a triplet of vectors αT,v, αS,v, αP,v ∈ {0, 1}^M where M = 2O⁽ⁿ⁾, and Bob holds a reasonably small input which is just a triplet of indexes βT,v, βS,v, βP,v ∈ [M]. T(v) is given by the decomposition T(v) = αT,v(βT,v) (similarly for the successor and predecessor). The simulation theorem of Göös et al. [2017] and Anshu et al. [2017] now implies:

       Corollary 3.2

      CC(SIMULATION END-OF-A-LINE); informal. Finding an end of a line requires 2^Ω(n) bits of communication.

       Embedding as a Continuous Function

      Our next step is to reduce the problem of finding an end of a line to that of finding a Brouwer fixed point. Here, we use the construction from Chapter 4.

      We embed the vertices of the discrete graph G in the continuous space [−1, 2]^Θ(n). Specifically, we embed each vertex v of G into a point x_v in [−1, 2]^Θ(n) and each edge (v, w) in G into a (continuous) path in [−1, 2]^Θ(n) that connects the corresponding points x_v and x_w. In particular, we construct a continuous Lipschitz function f :[−1, 2]^Θ(n) → [−1, 2]^Θ(n) such that:

      1. The computation of f can be done using local information about I. Namely, for points that are close to x_v it is sufficient to know I(v) to compute f. For points that are close to a path that corresponds to the edge (v, w) but far from the points x_v, x_w, it is sufficient to know whether (v, w) is an edge in the line (in particular, knowing either I(u) or I(v) suffices). For points that are far from all paths (v, w), f does not depend on I at all (and thus can be computed without any communication).

      2. Any (normalized) ||·||₂-approximate fixed point of f can be mapped (efficiently) back to an end of some line in I.

      Property 1 induces the following efficient communication protocol for computing f(x): Bob finds v such that x is close to x_v, and sends βT,v, βS,v, βT,v; Alice replies with and they each use I(v) to locally compute f(x). (Similarly, if x is close to the path corresponding to edge (v, w), they use a similar protocol to compute I(v) and I(w).)

      By Property 2, we have:

       Corollary 3.3

      CC(BROUWER); informal. Finding a (normalized) ||·||₂-approximate fixed point of f requires 2^Ω(n) bits of communication.

       Two-Player Game

      Naively thinking, we would like to design a game where Alice chooses a point x ∈ [−1, 2]^Θ(n) (on the ε-grid) and Bob chooses a point y ∈ [−1, 2]^Θ(n) (on the ε-grid). Alice’s utility will be given by , and Bob’s utility will be given by⁴ . Then, by applying similar arguments to those in Babichenko [2016], McLennan and Tourky [2005], Rubinstein [2016], and Shmaya [2012], we can deduce that every approximate Nash equilibrium corresponds to an approximate fixed point, and thus also to an end of a line.

      However, the above idea is obviously incorrect because Bob’s utility depends on f, whereas in the communication problem his utility should depend on the βs only. Our key idea is to use the fact that f can be computed locally to design a somewhat similar game where similar phenomena to those in the “naive” game will occur in approximate equilibria.

      Bob doesn’t know f, but to compute f(x) he should only know the local information about the vertex (or vertices) that corresponds to x. We incentivize Alice and Bob to combine their private information about the corresponding vertex (or vertices) by the following utilities structure.

      • Alice’s first component of utility is given by . As in the “naive” game, in any approximate Nash equilibrium Alice will play points in the ϵ-cube of the ϵ-grid that contains with probability close to one.

      • Bob tries to guess the vertex v (or the vertices v, w) that corresponds to the point x. Since x (almost always) belongs to the same ϵ-cube, in any (approximate) Nash equilibrium, his guess should be correct (with high probability). In addition, Bob should announce the β indexes βT, βS, and βP of v (of v and w). Again, we incentivize him to do so by defining that he should “guess” also these β indexes, and in an (approximate) equilibrium his guess should be correct with high probability (w.h.p.).

      • We want Alice to announce I(v) (similarly for w in the case of two vertices). Thus, we ask her to guess the decomposition αvB(βB) where vB and βB are the announced v and β by Bob. In (approximate) equilibrium, since Bob announces the correct v and β (w.h.p.), this incentivizes her to announce the correct I(v) (w.h.p.).

      • Now Bob uses the local information of I(v) (and I(w)) to compute f. Namely, his last utility component is defined by where fIA_(v),IA_(W) is Bob’s “estimation” of f under the relevant local information announced by Alice. In (approximate) equilibrium Alice announces the correct local information (w.h.p.); thus Bob computes f correctly (w.h.p.).

      Summarizing, the (approximate) equilibrium analysis of the presented game is similar to the analysis of the naive game, because in (approximate) equilibrium f is computed correctly (w.h.p.). But unlike the naive game, here Alice’s utility depends only on the αs and Bob’s utility only on the βs.

       n-Player Game: ϵ-WSNE

      The n-player game reduction is based on the same ideas as the two-player reduction. For clarity, we present first the idea of a reduction that proves the following weaker result:

      There exists a constant ϵ > 0 such that the communication complexity of ϵ-well-supported approximate Nash equilibrium in n-player games with a constant number of actions for each player is at least 2^cn for some constant c.

      After СКАЧАТЬ