Hardness of Approximation Between P and NP. Aviad Rubinstein

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

СКАЧАТЬ this result in two aspects: first to improve the constant-number-of-action to binary-action, second to improve the ϵ-well-supported Nash equilibrium to (ϵ, ϵ)-weak approximate equilibrium.

      The idea is to replace a single player—Alice—who chooses x in the ϵ-grid of [−1, 2]^Θ(n) by a population of Θ(n) players ; each player . in the population is responsible for the i th coordinate of x. The payoff of player . is given by −|x_i − yi|². This incentivizes player . to play a single action, or two adjacent actions, in the ϵ-grid of the segment [−1,2] (in every WSNE). By looking at the action profile of all . players, we get the same phenomenon as in the two-player case: every point x in the support of Alice’s players belongs to the same ϵ-cube of the ϵ-grid.

      Now, we replace the guess of v ∈ {0,1}^Θ(n), which is done by Bob, by population of size Θ (n) where again each player is responsible to a single coordinate of v. Again, in a WSNE all players will guess correctly.

      Similarly for the guess of β: we think of β ∈ [M]³ as an element of [0,1}^3logM and we construct a population of 3 log M players; each controls a single bit.

      Similarly for Alice’s guesses of IA(v) and IA(v): we construct 6 players, and each chooses a bit.

      Finally, we again replace the choice of y ∈ [−1, 2]^Θ(n) by a population of Θ(n) players . Each is responsible to a single coordinate. The payoff of player is given by . The analysis of this game is very similar to the two-player game analysis.

       n-Player Game: (ϵ, ϵ)-Weak ANE and Binary Actions

      In the above reduction, the x-type (and y-type) players have 3/ϵ actions each. To construct a binary action game, we use the technique of Babichenko [2016]. We replace each such player by a population of 3/ϵ players, each located at a point in the ϵ-grid of the segment [−1, 2]. A player that is located at j ∈ [−1,2](on the ϵ-grid) has to choose between the two points j or j + ϵ. In a WSNE, all players located to the left of yi will choose j + ϵ, and all players located to the right of yi will choose j.

      More tricky is to generalize this reduction to weak approximate equilibria. Recall that in weak approximate equilibria, a constant fraction of players may play an arbitrary suboptimal action. Here we take into account both;

      1. Players that are not ϵ-best replying, and

      2. Players that are ϵ-best replying, but put small positive weight on the inferior action (among the two) and the realization of their mixed action turns out to be the inferior action.

      In order to be immune from this small constant fraction of irrational players, we use error-correcting codes.⁵ Let Eβ:{0,1}^{3 log M} → {0,1}^{Θ(3 log M)} be a good binary error-correcting code. Instead of having a population of size 3 log M that tries to guess β, we replace it by a population of size Θ(3 log M) where each player tries to guess his bit in the encoding of β. Now even if a small constant fraction of players will act irrationally, the decoding of the action profile of the β-type players will turn out to be ß. We use the same idea for all types of populations (x-type, y-type, v-type, and I-type). This idea completes the reduction for weak approximate equilibria.

3.5 Proofs

      In Subsection 3.5.1 we prove a randomized query lower bound for the end-of-the-line problem. In Subsection 3.5.2 we show how the lower bounds of Subsection 3.5.1 can be “lifted” to get a hard problem in the randomized communication complexity models. In Subsections 3.5.3, 3.5.4, and 3.5.5 we reduce the communicationally hard end-of-any-line problem to the approximate Nash equilibrium problem.

       3.5.1 A Randomized Query Complexity Lower Bound

      Let G be a directed graph with the vertices V = {0, 1}ⁿ ×{0, 1}ⁿ × [n + 1]. Each vertex (v₁, v₂, k), where v₁, v₂ ∈ {0, 1}ⁿ and k ∈ [n], has two outgoing edges to the vertices and , where vj(0) = (v₁,…, vj₋₁,0, vj+₁,…, vn). We call the 0-successor of v, and the 1-successor of v. Each vertex v = (v₁, v₂, n + 1) has a single outgoing edge to the vertex (v₂, v₁, 0). Note that the incoming degree of each vertex v = (v₁, v₂, k) ∈ V is at most two. For k = 1 there is a single incoming edge from (v₂, v₁, n + 1). For k > 1 there are two incoming edges from and from . We call the 0-predecessor of v, and the 1-predecessor of v.

      We define the QUERY END-OF-THE-LINE to be the problem of finding the end of a line in G that starts at the point 0_2n+1. More formally, we represent a line in G by a triple I(v) ≜ (T(v), S(v), P(v)) where T(v) ∈ {0, 1} indicates whether the line goes through v, S(v) ϵ {0, 1} indicates who is the successor of v, and P(v) ∈ {0, 1} indicates who is the predecessor of v (here we use the fact that each vertex has outgoing and incoming degree of at most two). Throughout the chapter, we slightly abuse notation and use S(v)/P(v) to refer both to the bits and to the corresponding vertices (i.e., the S(v)/P(v)-successor/predecessor of v). The end of the line is the vertex v* such that T(v*) = 1 but T(S(v*)) = 0.

       Definition 3.1

      QUERY END-OF-THE-LINE.

      Input: A line I = (T, S, P) over the graph G that starts at the point 0_2n+1.

      Output: The first bit ([v*]₁) of the end-of-the-line СКАЧАТЬ