Hardness of Approximation Between P and NP. Aviad Rubinstein

can hope for is a polynomial lower bound.

      Indeed, our communication complexity results do not directly fit into the “between P and NP” theme of this book. However, we chose to include them because they provide further evidence that real players may not converge to a Nash equilibrium. More importantly, en route to obtaining our communication complexity lower bounds, we develop a construction of a hard-to-find Brouwer fixed point. This construction will be useful in Chapters 6 and 16.

Our Results

      We study both two-player games with a large number (N) of actions, and two-action games with a large number (n) of players. The trivial solution of communicating every player’s entire utility function in normal form requires O(N2) and O(n2n) communication, respectively.¹ For constant approximation, no non-trivial lower bounds were previously known for the general model, and even for the restricted case of randomized query complexity (see Subsection 3.3) both settings were stated as open questions in Fearnley et al. [2013] and Babichenko [2016], Chen et al. [2017], Hart and Nisan [2013], respectively. For n-player, Hart and Mansour [2010] gave an exp(n) lower bound on the communication complexity of exact Nash equilibrium in n-player games as also exp(n),² and even for an approximate parameter of 1/ poly(n) the problem was open [Nisan 2009a].

      For two-player games, we prove a polynomial lower bound on the communication complexity:

Theorem 3.1

      There exists a constant ϵ > 0 such that the randomized communication complexity (BPP^cc)of ϵ-Nash equilibrium in two-player N × N games is at least Nϵ.

      For n-player games, we consider a two-party communication problem where the set of players [n] is divided into two disjoint subsets [n] = nA ⊍ nB. Alice holds the utilities of the players in nA, and Bob holds the utilities of the players in nB. In particular, this communication problem is easier than the n-parties communication problem where each player holds his own utility function. Furthermore, our negative result holds for the notion of weak approximate Nash equilibrium [Babichenko et al. 2016], which in particular implies the same negative result for the standard notion of approximate Nash equilibrium (see also Definition 2.3).

Theorem 3.2

      There exists a constant ϵ> 0 such that the randomized communication complexity (BPP^cc)of (ϵ, ϵ)-weak approximate Nash equilibrium in n-player binary-action games is at least 2^ϵn.

3.1 Uncoupled Dynamics

      An underlying assumption of the Nash equilibrium solution is that players predict correctly the (mixed) action of their opponents (or alternatively predict correctly their expected payoff at each action). One justification for this problematic assumption, which appears in the seminal work of John Nash [Nash 1951], is that in some scenarios players may learn the behavior of their opponents in cases where the game is played repeatedly. This idea led to an extensive study of learning dynamics and their convergence to Nash equilibrium (see, e.g., [Young 2004, Hart and Mas-Colell 2013, Kalai and Lehrer 1993]). One natural, and general, class of adaptive dynamics is that of uncoupled dynamics [Hart and Mas-Colell 2003, 2006], where it is assumed that players do not know the utilities of their opponents (but observe their past behavior). The question on the existence of uncoupled dynamics that lead to Nash equilibrium is quite well understood [Babichenko 2012, Foster and Young 2006, Germano and Lugosi 2007, Hart and Mas-Colell 2006]. Several uncoupled dynamics that converge to approximate Nash equilibrium (or pure Nash equilibrium [Young 2009]) are known. All these dynamics are based on an exhaustive search principle, where at the moment a player realizes she is acting sub-optimally she updates her action to a random one (rather than to an optimal one or a better one). One criticism of these dynamics is that convergence to equilibrium may take an unreasonably long time in large games where the exhaustive search is done over a large space. This led to the study of the rate of convergence of uncoupled dynamics. As pointed out by Conitzer and Sandholm [2004], for every solution concept (in particular equilibria solutions), the (randomized) communication complexity of a solution is identical (up to a logarithmic factor) to the rate of convergence by any (randomized) uncoupled dynamics to the solution. This observation initiated the communication complexity study in games. As was mentioned above, the communication complexity, and thus also the rate of convergence of uncoupled dynamics, was known only for exact or pure Nash equilibrium. The question on the rate of convergence of uncoupled dynamics to approximate Nash equilibrium was an open question. Given the fact that all known positive results introduce dynamics that converge to approximate Nash equilibrium, this question is central. Our results for communication complexity resolve this open question, yielding the following negative results for uncoupled dynamics:

       Corollary 3.1

      Uncoupled dynamics. There exists a constant ϵ > 0 such that any uncoupled dynamics require:

      2-player. At least poly(N) rounds to converge to an ϵ-Nash equilibrium in two-player N × N games.

      n-player. At least 2^Ω(n) rounds to converge to an ϵ-Nash equilibrium (or even (ϵ, ϵ)-weak approximate Nash equilibrium) in n-player binary-action games.

3.2 Techniques

      Proving communication complexity lower bounds for Nash equilibrium is notoriously challenging for two reasons. The first reason, as is common in hardness of Nash equilibrium in other models, is totality: there always exists at least one (exact) equilibrium, and the proof of existence induces a non-trivial (yet inefficient) algorithm for finding it. In order to construct hard instances we must carefully hide the equilibrium (we can’t just remove it), and make sure that the above algorithm is indeed inefficient for our instances.

      Another reason for the communication complexity of approximate equilibrium being an open question for a long time is the fact that there exist efficient non-deterministic communication protocols (polylog(N) for two-player, poly(n) for n-player): verification of equilibrium (exact or approximate) requires only constant communication, and small-representation approximate equilibria always exist (e.g., by Lipton et al. [2003]). Therefore, the communication complexity lower bounds for approximate equilibria, as we prove in this chapter, show an exponential gap between the non-deterministic and randomized (or even deterministic) communication complexity of a total search problem. We are certainly not the first to show such separations (see, e.g., [Karchmer et al. 1995, Raz and McKenzie 1999, Raz and Wigderson 1990]).³ But such separations are still not very common in communication complexity, and for a good reason: for decision problems, they are impossible! The deterministic communication complexity is upper-bounded by the product of the non-deterministic and co-non-deterministic communication complexities [Aho et al. 1983].

      The first ingredient in our proof is a construction of a special continuous function f : [0, 1]ⁿ → [0, 1]ⁿ whose approximate fixed points are hard to find. The construction is inspired by that of Hirsch et al. [1989], and the main new ingredient is the use of error-correcting codes to replace the l∞ inapproximability with l₂ inapproximability. The construction appears in Chapter 4. The second ingredient in our proof is the simulation theorems for randomized communication complexity due to Anshu et al. [2017] and Göös et al. [2017].

      The main steps in our proofs are as follows. First, we prove a randomized query complexity hardness result for the problem of finding the end of a line in a particular constant-degree graph. Then we use a simulation theorem of Anshu et al. [2017] and Göös et al. [2017] to “lift” this