Let
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 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
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
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
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
3. Do not confuse this with the quasi-polynomial lower bound
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 utility matrix; hence the most we can hope for is a polynomial lower bound.
Indeed,
