Hardness of Approximation Between P and NP. Aviad Rubinstein

, 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.