Hardness of Approximation Between P and NP. Aviad Rubinstein

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

Читать онлайн книгу Hardness of Approximation Between P and NP - Aviad Rubinstein страница 23

Автор:
Жанр:
Серия:
Издательство:
Hardness of Approximation Between P and NP - Aviad Rubinstein ACM Books

Скачать книгу

alt="image"/> does not affect image

      ■

      A similar lemma holds for the second m-tuple of x and the vertex w:

      In every ϵ4-ANE image, if the second m-tuple of coordinates of image is 6h-close to the binary encoding E(w) of a vertex w, then

image

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

      In every ϵ4-ANE image 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.

      In every ϵ4-ANE image.

       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 image, 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 image 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 ϵ4-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 ϵ4-Nash equilibrium, and then both of them know image, which is a δ-approximate fixed point of f (by Corollary 3.5). Using Dv, they decode the vertex v* and they know the first coordinate of v*.

      Using Corollary 3.4, we deduce that the communication complexity of ϵ4-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.

Скачать книгу