Hardness of Approximation Between P and NP. Aviad Rubinstein

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

f is 0(1)-Lipschitz in ||·||₂ norm.

      3. f is local in the sense that it can be defined as an interpolation between a few (in fact, 64) functions, , that do not depend on the lines I and such that:

      (a) If the first m-tuple of coordinates of x is 6h-close to the encoded vertex E(v), but the second m-tuple of coordinates of x is 6h-far from any encoded vertex E(w), then for every I₂ ∈ {0, 1}³.

      (b) If the second m-tuple of coordinates of x is 6h-close to the encoded vertex E(w), but the first m-tuple of coordinates of x is 6h-far from any encoded vertex E(v), then for every I₁ ∈ {0, 1}³.

      (c) If the first m-tuple of coordinates of x is 6h-close to the encoded vertex E(v), and the second m-tuple of coordinates of x is 6h-close to the encoded vertex E(w), then f_(I(v),I(w)(x) = f(x).

      (d) If none of the above conditions are satisfied, then for every I₁, I₂ ∈ {0, 1}³.

       3.5.4 Two-Player Game

       Theorem 3.3

      Theorem 3.1, restated. There exists a constant ϵ > 0 such that the communication complexity of ϵ-Nash equilibrium in two-player N × N games is at least Nϵ.

      We construct a two-player game between Alice and Bob of size NA × NB for

      such that Alice’s utility depends on only, Bob’s utility depends on only, and all ϵ⁴-approximate Nash equilibria of the game correspond to a δ-fixed point of f from Proposition 3.1. By property 1 in Proposition 3.1, any fixed point of f corresponds to a non-trivial end or start of a line in I.

       3.5.4.1 The Game

      In this subsection we construct our reduction from SIMULATION END-OF-THE-LINE to the problem of finding an ϵ-WSNE.

      Strategies. Recall that δ is the desired approximation parameter for a Brouwer fixed point in the construction of Proposition 3.1. We let ϵ be a sufficiently small constant; in particular, ϵ = Ο(δ) (this will be important later for Inequality (3.10)).

      Each of Alice’s actions corresponds to an ordered tuple , where:

      • x ∈ [−1, 2]^4m, where the interval [−1, 2] is discretized into {−1, −1 + ϵ,…, 2 − ϵ, 2};

      • and .

      Each of Bob’s actions corresponds to an ordered tuple , where:

      • y ∈ [−1, 2]^4m, where the interval [−1, 2] is discretized into {−1, −1 + ϵ,…, 2 − ϵ, 2};

      • vB, wB ∈ {0, 1}^2n+log(n+1) are vertices in the graph G;

      • and are triples of indexes.

      Utilities. Alice’s and Bob’s utilities decompose as

      The first component of Alice’s utility depends only on the first components of her and Bob’s strategies; it is given by:

      Given the first component x ∈ [−1, 2]^4m of Alice’s strategy, we define two decoding functions Dv, Dw :[−1, 2]^4m → {0, 1}ⁿ as follows. Let Rv(x) ∈ {0, 1}^m be the rounding of the first m-tuple of coordinates of x to {0, 1}^m; let Dv(x) = E⁻¹(Rv(x)) ∈ {0, 1}^2n+log(n+1), where E⁻¹ denotes the decoding of the error-correcting code from Subsection 3.5.3. We define Dw(x) ∈ {0, 1}^2n+log(n+1) analogously with respect to the second m-tuple of coordinates of x. The second component of Bob’s utility is now given by iff he guesses correctly the vertex D_v(x), and the corresponding β operation on this vertex. Namely, if vB = Dv(x) and , and otherwise. We similarly define Bob’s third component with respect to Dw(x).

      Note that Bob knows the indexes (for every v); thus to achieve Bob needs to guess correctly only the vertices Dv(x), Dw(x) and announce the corresponding triplet of β indexes.

      Going back to Alice, the second component of her utility is given by iff she guesses correctly the triplet I(vB) = (T(vB), S(vB), P(vB)) when the calculation of T, S, P is done by the decomposition of α(βB). Namely,

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