Hardness of Approximation Between P and NP. Aviad Rubinstein

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

Hardness of Approximation Between P and NP - Aviad Rubinstein


Скачать книгу
alt="image"/> of our reduction.3

       Lemma 2.6

      Let G = (A, B, E) be a bipartite (dA, dB)-bi-regular graph, and let nA ≜ |A|, nB ≜ |B|; set also nnB + nA and image. Let image 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 image, such that:

      and

       Proof

      Suppose that we place each aA 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 nO(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 image be real numbers satisfying the following properties for some imageimage. Then image.

       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 image(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 (α1(β1),…, αN(βN)). The standard bounded error two-party probabilistic communication complexity of the simulated problem D is denoted by image.

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

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

image

      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


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