Hardness of Approximation Between P and NP. Aviad RubinsteinЧитать онлайн книгу.
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 xv in [−1, 2]Θ(n) and each edge (v, w) in G into a (continuous) path in [−1, 2]Θ(n) that connects the corresponding points xv and xw. 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 xv 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 xv, xw, 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) ||·||2-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 xv, and sends βT,v, βS,v, βT,v; Alice replies with
By Property 2, we have:
Corollary 3.3
CC(BROUWER); informal. Finding a (normalized) ||·||2-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
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
• 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
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 2cn for some constant c.
After that, we explain how we can strengthen this result in two aspects: first to improve the constant-number-of-action to binary-action, second to improve the ϵ-well-supported Nash equilibrium to (ϵ, ϵ)-weak approximate equilibrium.
The idea is to replace a single player—Alice—who chooses x in the ϵ-grid of [−1, 2]Θ(n) by a population of Θ(n) players