Hardness of Approximation Between P and NP. Aviad Rubinstein

Hardness of Approximation Between P and NP

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, = 1 if , and otherwise. We similarly define Alice’s third component .

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

where the function 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 ϵ⁴-ANE. The proof proceeds via a sequence of lemmas that establish the structure of any ϵ⁴-ANE.

Lemma 3.3

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

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

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