Hardness of Approximation Between P and NP. Aviad Rubinstein

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

      with probability 1 − O(ϵ4) (where the probability is taken over and ).

Lemma 3.8

      In every ϵ⁴-ANE with probability 1 − O(ϵ4).

       Proof

      Follows immediately from Lemmas 3.6 and 3.7 and the “locality” condition in Proposition 3.1.

      ■

      The following corollary completes the analysis of the 2-player game.

Corollary 3.5

      In every ϵ⁴-ANE .

       Proof

      We recall that in Lemma 3.3 we have proved that

      with probability 1 − O(ϵ4). This also implies that x is, with high probability, close to its expectation:

      with probability 1 − O(ϵ4). Where the first inequality follows from the triangle inequaltiy, the second follows from the Arithmetic-Mean Geometric-Mean inequality (AM-GM inequalty), the third follows from convexity of , and the last follows from Lemma 3.3.

      Using that f is O(1)-Lipschitz together with Equation (3.5), we get that

      with probability 1 − O(ϵ4).

      By Lemma 3.8 we know that with probability 1 − O(ϵ4), which implies that

      Using similar arguments to those of Lemma 3.3 we can show that

      with probability 1 − O(ϵ4). As in the derivation of Equation (3.5), this implies:

      with probability 1 − O(ϵ4).

      With probability 1 − O(ϵ2), Inequalities (3.5), (3.4), (3.9), (3.8), (3.7), (3.6) hold simultaneously. In such a case, by the triangle inequality and by applying the inequalities in the exact order above, we have

       Proof

      Proof of Theorem 3.1. Any communication protocol that solves the ϵ⁴-Nash equilibrium problem in games of size N × N for N = 2^Θ(n) induces a communication protocol for the problem SIMULATION END-OF-THE-LINE: Alice constructs her utility in the above presented game using her private information of the αs, Bob constructs his utility using the βs. They implement the communication protocol to find an ϵ⁴-Nash equilibrium, and then both of them know , which is a δ-approximate fixed point of f (by Corollary 3.5). Using D_v, they decode the vertex v* and they know the first coordinate of v*.

      Using Corollary 3.4, we deduce that the communication complexity of ϵ⁴-Nash equilibrium in games of size 2^Θ(n) × 2^Θ(n) is at least 2^Ω(n).

      ■

       3.5.5 n-player Game

       Theorem 3.4

      Theorem 3.2, restated. There exists a constant ϵ > 0 such that the communication complexity of (ϵ, ϵ)-weak approximate Nash equilibrium in n-player binary-action games is at least 2^ϵn.