Hardness of Approximation Between P and NP. Aviad Rubinstein
complexity hardness. We use the construction in Chapter 4 to embed this line as a continuous Lipschitz function f : [0, 1]n → [0, 1]n. Finally, we build on ideas from Babichenko [2016], McLennan and Tourky [2005], and Shmaya [2012] to construct a two-player (respectively n-player) “imitation game” that simulates the short communication protocol for the computation of f, as well as a fixed point verification. In particular, every (approximate) Nash equilibrium of the game corresponds to an approximate fixed point of f, which in turn corresponds to an end of a line.
Since in this chapter we are proving unconditional intractability results, we have the privilege of reasoning about an explicit distribution of hard instances. In particular, it suffices to begin with the END-OF-THE-LINE special case of the END-OF-A-LINE problem, where the graph consists of just one line—and we want to find the end of that line. This hardly changes the proof, but it makes the notation a little simpler. For example, it suffices to prove that a decision problem (find the most significant bit of the end of the line) is hard. Furthermore, our hardness now holds for the interesting case where the game has a unique Nash equilibrium.
3.3 Additional Related Literature
Pure Nash Equilibrium. The communication complexity of pure Nash equilibrium has been studied before: in two-player N × N games it is poly(N) [Conitzer and Sandholm 2004], and in n-player games it is exp(n) [Hart and Mansour 2010].
Approximation Protocols. For two-player N × N games and ϵ ≈ 0.382, Czumaj et al. [2015] show that polylog(N) communication is sufficient for computing an ∊-approximate Nash equilibrium (improving over a protocol for ϵ ≈ 0.438 due to Goldberg and Pastink [2014]).
Query Complexity. There are several interesting results on the more restricted model of query complexity of approximate Nash equilibria, where the algorithm is assumed to have black-box access to the normal form representation of the utility function. Note that our communication complexity lower bounds immediately extend to this model as well.
Hart and Nisan [2013] prove that any deterministic algorithm needs to query at least an exponential number of queries to compute any ϵ-well-supported Nash equilibrium—and even any ϵ-correlated equilibrium. Babichenko [2016] showed that any randomized algorithm requires an exponential number of queries to find an ϵ-well-supported Nash equilibrium. Chen et al. [2017] extended Babichenko’s result to an almost-exponential (2Ω(n/ logn)) lower bound on the query complexity of ϵ-approximate Nash equilibrium. Note that our lower bound here is not only bigger (saving the log n factor), but also holds for the more general notion of weak approximate Nash equilibrium, and in the more general model of communication complexity.
Goldberg and Roth [2016] give a polynomial upper bound on the query complexity of ϵ-WSNE for any family of games that have any concise representation. This result is to be contrasted with (a) Babichenko’s query complexity lower bound, which uses a larger family of games, and (b) our lower bounds on the computational complexity of succinctly represented games (Theorem 5.1).
A much older yet very interesting and closely related result is that of Hirsch et al. [1989]. They show that any deterministic algorithm for computing a Brouwer fixed point in the oracle model must make an exponential -in the dimension n and the approximation ϵ-number of queries for values of the function. Our construction here builds upon and improves over Hirsch et al. [1989] by working with the l2-norm instead of the l∞-norm.
Correlated Equilibrium. For the related notion of correlated equilibrium, in n-player games with a constant number of actions, it is known that even exact correlated equilibrium can be computed using only poly(n)-communication (see [Hart and Mansour 2010, Jiang and Leyton-Brown 2015, Papadimitriou and Roughgarden 2008]. Interestingly, for exact correlated equilibria, there is an exponential gap between the above communication protocol and the query complexity lower bound of Babichenko and Barman [2015] and Hart and Nisan [2013]. Goldberg and Roth [2016] characterize the query complexity of approximate coarse correlated equilibrium in games with many players. Further discussion on correlated equilibria appears in Section 3.6.
Communication Complexity of Finding Fixed Points. For the related problem of finding a fixed point, Roughgarden and Weinstein [2016] study the communication complexity of an approximate fixed point of the decomposition. Namely, Alice holds a Lipschitz function f : A→B and Bob holds a Lipschitz function g : B→A, where A and B are compact convex sets, and their goal is to compute a fixed point of the decomposition g ◦ f. Roughgarden and Weinstein prove that the following version of this problem is communicationally hard: find an approximate fixed point of g ◦ f on a grid of A, when it is promised that such an approximate fixed point on the grid exists (the problem is not total).
Complexity of Equilibrium and Price of Anarchy. As discussed earlier, the main motivation for studying the (communication) complexity of Nash equilibrium is understanding its relevance as a predictive solution concept. This is a good place to mention a recent work of Roughgarden [2014], which highlights another important motivation for studying the complexity of Nash equilibrium: understanding the quality of equilibria. The Price of Anarchy (PoA) of a game is the ratio between the social welfare (sum of players’ utilities) in an optimum strategy profile, and the social welfare in the worst Nash equilibrium of that game. Roughgarden [2014] provides the following widely applicable recipe for lower bounds on PoA: if a Nash equilibrium can be found efficiently (in particular, via the non-deterministic protocol due to Lipton et al. [2003]), but approximating the optimal social welfare requires a higher communication complexity (even for non-deterministic protocols, e.g., by reduction from set disjointness), then clearly not all Nash equilibria yield high social welfare.
3.4 Proof Overview
The formal proofs appear in Section 3.5. Below we present the main ideas of the proof. As mentioned in the Introduction, the proof consists of four main steps. Below we present the ideas of each step.
Query Complexity of End-of-the-Line
Our proof starts with the following query complexity hardness result (Lemma 3.2): There exists a constant degree graph G = (V, E) with 2Θ(n) vertices, such that finding the end of a line in G requires 2Ω(n) queries. In fact, we prove the hardness result for directed graph G where each vertex has outgoing and incoming degree 2. Therefore, the successor and predecessor of each vertex are binary variables. In particular, for each v ϵ V, the information about its role in the line can be represented using only three bits, which we denote I(v) ≜ (T(v), P(v), S(v)) ∈ {0,1}3:
(a) Whether the line goes through v, which is denoted by T(v),
(b) Who is the successor of v (if v is on the line), which is denoted by S(v),
(c) Who is the predecessor of v (if v is on the line), which is denoted by P(v).
Lemma 3.1
QUERY END-OF-A-LINE; informal. Finding an end of a line with high probability requires 2Ω(n) queries to I.
From Query Complexity to Communication Complexity
We use a recent simulation theorem to “lift” our randomized query complexity lower bound to a randomized communication complexity bound.
The simulated communicationally hard problem has the following form. For each v ∈ V, Alice holds a triplet of vectors αT,v,