Hardness of Approximation Between P and NP - Aviad Rubinstein ACM Books

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

N × N games is at least Nϵ.

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

image

      such that Alice’s utility depends on image only, Bob’s utility depends on image only, and all ϵ4-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 image, where:

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

      • image and image.

      Each of Bob’s actions corresponds to an ordered tuple image, 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;

      • image and image are triples of indexes.

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

image

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

image

      Given the first component x ∈ [−1, 2]4m of Alice’s strategy, we define two decoding functions Dv, Dw :[−1, 2]4m → {0, 1}n 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−1(Rv(x)) ∈ {0, 1}2n+log(n+1), where E−1 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 image iff he guesses correctly the vertex Dv(x), and the corresponding β operation on this vertex. Namely, image if vB = Dv(x) and image, and image otherwise. We similarly define Bob’s third component image with respect to Dw(x).

      Note that Bob knows the indexes image (for every v); thus to achieve image 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 image 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, image = 1 if image, and image otherwise. We similarly define Alice’s third component image.

      Finally, the first component of Bob’s utility is given by:

image

      where the function image is as defined in Proposition 3.1.

       3.5.4.2 Analysis of Game

      In this subsection, we prove the reduction from SIMULATION END-OF-THE-LINE to finding an ϵ4-ANE. The proof proceeds via a sequence of lemmas that establish the structure of any ϵ4-ANE.

      In every ϵ4-ANE image, it holds that image with probability of at least 1 − ϵ2 (where the probability is taken over image).

      Proof We denote image as the vector of expectations, and image as the vector of variances. For every x we can rewrite

      Since the variance of the yi’s, as well as that of image and image, does not depend on x, Alice’s best response to Скачать книгу