Hardness of Approximation Between P and NP. Aviad Rubinstein
Читать онлайн книгу.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
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
• x ∈ [−1, 2]4m, where the interval [−1, 2] is discretized into {−1, −1 + ϵ,…, 2 − ϵ, 2};
•
Each of Bob’s actions corresponds to an ordered tuple
• 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;
•
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}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
Note that Bob knows the indexes
Going back to Alice, the second component of her utility is given by
Finally, the first component of Bob’s utility is given by:
where the function
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.
Lemma 3.3
In every ϵ4-ANE
Proof We denote
Since the variance of the yi’s, as well as that of