Hardness of Approximation Between P and NP. Aviad Rubinstein

Читать онлайн книгу.

Hardness of Approximation Between P and NP - Aviad Rubinstein


Скачать книгу
PPAD-hard (Corollary 8.1).

      We also prove intractability in different models: query complexity, communication complexity, and uncoupled dynamics (settling a long list of open questions from Babichenko [2012, 2016], Chen et al. [2017], Fearnley et al. [2013], Hart and Mansour [2010], Hart and Nisan [2013], Nisan [2009a], Roughgarden and Weinstein [2016]. The main advantage of these results is that they are unconditional, i.e., they do not rely on complexity assumptions such as ETH for PPAD, or P ≠ NP. In particular, in the setting where each player knows her own utility function, even computationally unbounded players have to communicate almost all their private information in order to reach even an approximate equilibrium.

      2

      Preliminaries

      We use 0n (respectively 1n) to denote the length-n vectors whose value is 0 (1) in every coordinate. For vectors x, y ∈ ℝn, we let

image

      denote the normalized 2-norm. Unless specified otherwise, when we say that x and y are Δ-close (or Δ-far), we mean Δ-close in normalized 2-norm. Similarly, for a binary string π ∈ {0, 1}n, we denote

image

      For a graph G = (V, E) and SV, we use den(S) ∈ [0, 1] to denote the density of subgraph S,

image

      A mixed strategy of player i is a distribution xi over i’s set of actions, Ai. We say that a vector of mixed strategies x ∈ × j∆Aj is a Nash equilibrium if every strategy ai in the support of every xi is a best response to the actions of the mixed strategies of the rest of the players, x−i. Formally, for every ai ∈ supp(xi),

image

      Equivalently, x is a Nash equilibrium if each mixed strategy xi is a best response to x−i:

image

      Each of those equivalent definitions can be generalized to include approximation in a different way.

       Definition 2.1

      ϵ-approximate Nash Equilibrium. We say that x is an ϵ-Approximate Nash Equilibrium (ϵ-ANE) if each xi is an ϵ-best response to x−i:

image

      On the other hand, we generalize the first definition of Nash equilibrium in the following stricter definition:

       Definition 2.2

      ϵ-well-supported Nash Equilibrium. x is an ϵ-Well-Supported Nash Equilibrium (ϵ-WSNE) if every ai in the support of xi is an ϵ-best response to x−i: for every ai ∈ supp(xi),

image

       WeakNash

      We can further relax the (already more lenient) notion of ϵ-ANE by requiring that the ϵ-best response condition only hold for most of the players (rather than all of them).

      (ϵ, δ)-WeakNash [Babichenko et al. 2016]. We say that x isan (∈, δ)-WeakNash if for a (1 − δ)-fraction of i’s, xi is an ϵ-best mixed response to x−i:

image

       Definition 2.4

      (∈, δ)-well-supported WeakNash. x is an (∈, δ)-well-supported WeakNash if for a (1 − δ)-fraction of i’s, every ai in the support of xi is an ϵ-best response to x−i:

image

      The END-OF-A-LINE of a problem considers an implicitly represented, exponential-size, directed graph whose vertices have in- and out-degree at most 1 (this is without loss of generality). The special vertex 0n has in-degree 0, and the goal is to find another odd-degree vertex. The graph is a union of lines and cycles, so in particular the line starting at 0n ends with another odd-degree vertex.

      The graph is implicitly defined with functions S, P that, for each vertex, give its Successor (outgoing neighbor) and Predecessor (incoming neighbor). In the computational variant of END-OF-A-LINE, S, P are given as explicit circuits, whereas in the query complexity variant they are given as oracles. There is also a communication complexity variant, whose definition is more involved and is deferred to Section 3.4.

      In the formal definition of the computational variant, we also have to consider the case that S, P are inconsistent, i.e., for some uv we have S(u) = v, but P(v) ≠ u; we also allow the algorithm to


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