Hardness of Approximation Between P and NP. Aviad Rubinstein

of our reduction.³

       Lemma 2.6

      Let G = (A, B, E) be a bipartite (dA, dB)-bi-regular graph, and let nA ≜ |A|, nB ≜ |B|; set also n ≜ nB + nA and . Let be an arbitrary partition of B into disjoint subsets of size ρ. There is a quasi-polynomial deterministic algorithm (alternatively, linear-time randomized algorithm) that finds a partition of A into , such that:

      and

       Proof

      Suppose that we place each a ∈ A into a uniformly random Si. By Chernoff bound and union bound, (2.2) and (2.3) hold with high probability. Now, by Chernoff bound for k-wise independent variables (Theorem 2.4), it suffices to partition A using a Θ(log n)-wise independent distribution. Such distribution can be generated with a sample space of n^{O(log n)} (e.g., [Alon et al. 1986]). Therefore, we can enumerate over all possibilities in quasi-polynomial time. By the probabilistic argument, we will find at least one partition that satisfies (2.2) and (2.3).

      ■

       2.7.5 How to Catch a Far-from-Uniform Distribution

      The following lemma due to Daskalakis and Papadimitriou [2009] implies that

       Lemma 2.7

      Lemma 3 in the full version of Daskalakis and Papadimitriou [2009]. Let be real numbers satisfying the following properties for some . Then .

       2.7.6 Simulation Theorem

      Let D : {0, 1}^N → {0, 1} be a decision problem. We consider the following query complexity model (called also decision tree complexity). Each query is an index k ∈ [N] and the answer is the k-th bit of the input. The randomized query complexity of D is denoted by (D), where δ is the allowed probability of error.

      We also consider the following communication complexity model. Here, for every k ∈ [N], Alice holds a vector ak ∈ {0, 1}^M and Bob holds an index βk ∈ [M], for some M = poly(N). Their goal is to compute D for the input (α₁(β₁),…, αN(β_N)). The standard bounded error two-party probabilistic communication complexity of the simulated problem D is denoted by .

      To “lift” from query complexity hardness to communication complexity, we use the following recent simulation theorem for BPP, due to Göös et al. [2017].

Theorem 2.5

      BPP simulation theorem, [Göös et al. 2017]. There exists M = poly(N) such that for any constants 0 < δ <1/2,

1. As usual, n is the size of the description of the instance, i.e., the size of the circuits S and P.

2. Note that we need an ϵ-biased set for a large field . Such constructions are not as common in the literature, which mostly focuses on the field . To the best of our knowledge, existing explicit constructions for larger fields require much larger cardinality. Nevertheless, for our modest pseudo-randomness desiderata, we could actually use the explicit construction from Alon et al. [1992]. For ease of presentation, we prefer to brute-force derandomize the construction from Azar et al. [1998].

3. Do not confuse this with the quasi-polynomial lower bound we obtain for the running time of the community detection problem.

      PART II

       COMMUNICATION COMPLEXITY

      3

       Communication Complexity of Approximate Nash Equilibrium

      The main motivation for studying the complexity of approximate Nash equilibrium is the insight about the relevance of Nash equilibrium as a predictive solution concept: if specialized algorithms cannot compute an (approximate) equilibrium, it is unreasonable to expect selfish agents to “naturally” converge to one. (See also discussions in the introduction, as well as Daskalakis et al. [2009a], Hart and Mansour [2010], Nisan [2009b].) Although extremely useful and the main focus of this book, lower bounds on computational complexity suffer from an obvious caveat: we actually don’t know how to truly prove any computational lower bounds: All our computational lower bounds inherently rely on complexity assumptions (such as NP ≠ P or PPAD ≠ P); even though these assumptions are widely accepted by computer scientists, they make these theorems less accessible to game theorists and economists. For example, it is not clear how they relate to the uncoupled dynamics model studied in game theory [Babichenko 2012, Hart and Mas-Colell 2003, 2006].

      In this part of the book, we prove unconditional lower bounds on the communication complexity of approximate Nash equilibrium. In the communication complexity model, each player knows her own utility function, and we restrict the amount of information exchanged between players in order to agree on an approximate Nash equilibrium. The players in this model are unreasonably powerful beings with unlimited computational power. In this sense, obtaining lower bounds even in this setting is more convincing than our computational complexity results. Furthermore, our lower bounds on communication complexity translate immediately to the uncoupled dynamics model mentioned above (see also Subsection 3.1). The tradeoff is that the computational complexity lower bounds we can prove are stronger. Take two-player games with N actions, for example. The main result in this book is that no polynomial time algorithm can find an approximate equilibrium. In the communication complexity model, per contra, it is trivial for both players to send their entire N × N