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.

1. In fact, “more than six decades” is an understatement: Irving Fisher’s thesis from 1891 dealt with the closely related question of convergence to market equilibria [Brainard and Scarf 2000].

2. Assuming P ≠ PPAD; see the discussion in the next section about this assumption.

3. Under a complexity assumption stronger than P ≠ PPAD that we call the Exponential Time Hypothesis (ETH) for PPAD; see Section 1.2 for details.

4. This guarantee is actually without loss of generality [Papadimitriou 1994], but this is not so important for our purposes.

5. Here work is measured by the number of oracle calls rather than running time; indeed this model will be the starting point of our reductions for query and communication complexity.

6. There is also a stricter notion that requires x to be close to an x* for which f(x*) = x* exactly. See, e.g., Etessami and Yannakakis [2010].

7. Both the approximate Caratheodory’s theorem and the resulting algorithm have been described by many researchers (e.g., [Arora et al. 2012, Lipton et al. 2003]); however, the presentation in Barman [2015] is our favorite.

      2

      Preliminaries

Notation

      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

      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}ⁿ, we denote

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

2.1 Nash Equilibrium and Relaxations

      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∆A_j 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),

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

      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:

      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),

       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).

Definition 2.3

      (ϵ, δ)-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:

       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:

2.2 PPAD and END-OF-A-LINE

      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 0_n 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 0_n 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 u ≠ v we have S(u) = v, but P(v) ≠ u; we also allow the algorithm to