Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
258,925 characters · 97 sections · 186 citation commands
\thispagestyle{empty}
\addcontentsline{toc}{section}{Foreward}
This monograph is based on lecture notes from my mini-course “Complexity Theory, Game Theory, and Economics,” taught at the Bellairs Research Institute of McGill University, Holetown, Barbados, February 19--23, 2017, as the 29th McGill Invitational Workshop on Computational Complexity.
The goal of this monograph is twofold:
It consists of two five-lecture sequences: the {\em Solar Lectures,} focusing on the communication and computational complexity of computing equilibria; and the {\em Lunar Lectures,} focusing on applications of complexity theory in game theory and economics.\footnote{Cris Moore: “So when are the {\em stellar} lectures?”} No background in game theory is assumed.
Thanks are due to many people: Denis Therien and Anil Ada for organizing the workshop and for inviting me to lecture; Omri Weinstein, for giving a guest lecture on simulation theorems in communication complexity; Alex Russell, for coordinating the scribe notes; the scribes\footnote{Anil Ada, Amey Bhangale, Shant Boodaghians, Sumegha Garg, Valentine Kabanets, Antonina Kolokolova, Michal Kouck\'y, Cristopher Moore, Pavel Pudl\'ak, Dana Randall, Jacobo Tor\'an, Salil Vadhan, Joshua R. Wang, and Omri Weinstein.}, for putting together a terrific first draft; and all of the workshop attendees, for making the experience so unforgettable (if intense!). I also thank Yakov Babichenko, Mika G\"o\"os, Aviad Rubinstein, Eylon Yogev, and an anonymous reviewer for numerous helpful comments on earlier drafts of this monograph.
The writing of this monograph was supported in part by NSF award CCF-1524062, a Google Faculty Research Award, and a Guggenheim Fellowship. I would be very happy to receive any comments or corrections from readers.
Tim Roughgarden\\ Bracciano, Italy\\ December 2017\\ (Revised December 2019)
\addcontentsline{toc}{section}{Overview} \setcounter{footnote}{0}
There are 5 solar lectures and 5 lunar lectures. The solar lectures focus on the communication and computational complexity of computing an (approximate) Nash equilibrium. The lunar lectures are less technically intense and meant to be understandable even after consuming a rum punch; they focus on applications of computational complexity theory to game theory and economics.
\paragraph{Lecture 1: Introduction and wish list.} The goal of the first lecture is to get the lay of the land. We'll focus on the types of positive results about equilibria that we want, like fast algorithms and quickly converging distributed processes. Such positive results are possible in special cases (like zero-sum games), and the challenge for complexity theory is to prove that they cannot be extended to the general case. The topics in this lecture are mostly classical.
\paragraph{Lectures 2 and 3: The communication complexity of Nash equilibria.} These two lectures cover the main ideas in the recent paper of BR17, which proves strong communication complexity lower bounds for computing an approximate Nash equilibrium. Discussing the proof also gives us an excuse to talk about “simulation theorems” in the spirit of DBLP:journals/combinatorica/RazM99, which lift query complexity lower bounds to communication complexity lower bounds and have recently found a number of exciting applications.
\paragraph{Lecture 4: $\mathsf{TFNP}$, $\mathsf{PPAD}$, and all that.} In this lecture we begin our study of the {\em computational} complexity of computing a Nash equilibrium, where we want conditional but super-polynomial lower bounds. Proving analogs of $\mathsf{NP}$-completeness results requires developing customized complexity classes appropriate for the study of equilibrium computation.\footnote{Why can't we use the tried-and-true theory of $\mathsf{NP}$-completeness? Because the guaranteed existence (Theorem (ref)) and efficient verifiability of a Nash equilibrium imply that computing one is an easier task than solving an $\mathsf{NP}$-complete problem, under appropriate complexity assumptions (see Theorem (ref)).} This lecture also discusses the existing evidence for the intractability of these complexity classes, including some very recent developments.
\paragraph{Lecture 5: The computational complexity of computing an approximate Nash equilibrium of a bimatrix game.} The goal of this lecture is to give a high-level overview of Rubinstein's recent breakthrough result R16 that an ETH-type assumption for $\mathsf{PPAD}$ implies a quasi-polynomial-time lower bound for the problem of computing an approximate Nash equilibrium (which is tight, by Corollary (ref)).
Most of the lunar lectures have the flavor of “applied complexity theory.”\footnote{Not an oxymoron!} While the solar lectures build on each other to some extent, the lunar lectures are episodic and can be read independently of each other.
\paragraph{Lecture 1: The 2016 FCC Incentive Auction.} The recent FCC Incentive Auction is a great case study of how computer science has influenced real-world auction design. This lecture provides our first broader glimpse of the vibrant field called {\em algorithmic game theory}, at most 10% of which concerns the complexity of computing equilibria.
\paragraph{Lecture 2: Barriers to near-optimal equilibria.} This lecture concerns the “price of anarchy,” meaning the extent to which the Nash equilibria of a game approximate an optimal outcome. It turns out that nondeterministic communication complexity lower bounds can be translated, in black-box fashion, to lower bounds on the price of anarchy. We'll see how this translation enables a theory of “optimal simple auctions.”
\paragraph{Lecture 3: Barriers in markets.} You've surely heard of the idea of “market-clearing prices,” which are prices in a market such that supply equals demand. When the goods are divisible (milk, wheat, etc.), market-clearing prices exist under relatively mild technical assumptions. With indivisible goods (houses, spectrum licenses, etc.), market-clearing prices may or may not exist. It turns out that complexity considerations can be used to explain when such prices exist and when they do not. This is cool and surprising because the issue of equilibrium existence seems to have nothing to do with computation (in contrast to the Solar Lectures, where the questions studied are explicitly about computation).
\paragraph{Lecture 4: The borders of Border's theorem.} Border's theorem is a famous result in auction theory from 1991, about single-item auctions. Despite its fame, no one has been able to extend it to significantly more general settings. We'll see that complexity theory explains this mystery: significantly generalizing Border's theorem would imply that the polynomial hierarchy collapses!
\paragraph{Lecture 5: Tractable relaxations of Nash equilibria.} With the other lectures focused largely on negative results for computing Nash equilibria, for an epilogue we'll conclude with positive algorithmic results for relaxations of Nash equilibria, such as correlated equilibria.
\part{Solar Lectures}
\setcounter{chapter}{0}
\chapter{Introduction, Wish List, and Two-Player Zero-Sum Games} \titlerule
To an algorithms person (like the author), complexity theory is the science of why you can't get what you want. So what is it we want? Let's start with some cool positive results for a very special class of games---two-player zero-sum games---and then we can study whether or not they extend to more general games. For the first positive result, we'll review the famous Minimax theorem, and see how it leads to a polynomial-time algorithm for computing a Nash equilibrium of a two-player zero-sum game. Then we'll show that there are natural “dynamics” (basically, a distributed algorithm) that converge rapidly to an approximate Nash equilibrium.
Recall the game of rock-paper-scissors (or roshambo, if you like)\footnote{https://en.wikipedia.org/wiki/Rock-paper-scissors}: there are two players, each simultaneously picks a strategy from $\{ \text{rock}, \text{paper}, \text{scissors} \}$. If both players choose the same strategy then the game is a draw; otherwise, rock beats scissors, scissors beats paper, and paper beats rock.\footnote{Here are some fun facts about rock-paper-scissors. There's a World Series of RPS every year, with a top prize of at least \$50K. If you watch some videos from the event, you will see pure psychological warfare. Maybe this explains why some of the same players seem to end up in the later rounds of the tournament every year.
There's also a robot hand, built at the University of Tokyo, that plays rock-paper-scissors with a winning probability of 100% (check out the video). No surprise, a very high-speed camera is involved.}
Here's an idea: how about we play rock-paper-scissors, and you go first? This is clearly unfair---no matter what strategy you choose, I have a response that guarantees victory. But what if you only have to commit to a {\em probability distribution} over your three strategies (called a mixed strategy)? To be clear, the order of operations is: (i) you pick a distribution; (ii) I pick a response; (iii) nature flips coins to sample a strategy from your distribution. Now you can protect yourself---by picking a strategy uniformly at random, no matter what I do, you have an equal chance of a win, a loss, or a draw.
The {\em Minimax theorem} states that, in any game of “pure competition” like rock-paper-scissors, a player can always protect herself with a suitable randomized strategy---there is no disadvantage of having to move first. The proof of the Minimax theorem also gives as a byproduct a polynomial-time algorithm for computing a Nash equilibrium (by linear programming).
We specify a two-player zero-sum game with an $m \times n$ payoff matrix $A$ of numbers. The rows correspond to the possible choices of Alice (the “row player”) and the columns correspond to possible choices for Bob (the “column player”). Entry $A_{ij}$ contains Alice's payoff when Alice chooses row $i$ and Bob chooses column $j$. In a zero-sum game, Bob's corresponding payoff is automatically defined to be $-A_{ij}$. Throughout the solar lectures, we normalize the payoff matrix so that $|A_{ij}| \leq 1$ for all $i$ and $j$.\footnote{This is without loss of generality, by scaling.}
For example, the payoff matrix corresponding to rock-paper-scissors is: \\
\
Mixed strategies for Alice and Bob correspond to probability distributions $x$ and $y$ over rows and columns, respectively.\footnote{A {\em pure strategy} is the special case of a mixed strategy that is deterministic (i.e., allots all its probability to a single strategy).}
When speaking about Nash equilibria, one always assumes that players randomize independently. For a two-player zero-sum game $A$ and mixed strategies $x,y$, we can write Alice's expected payoff as \[ x^{\top} A y = \sum_{i,j} A_{ij} x_i y_j\,. \] Bob's expected payoff is the negative of this quantity, so his goal is to minimize the expression above.
The question that the Minimax theorem addresses is the following:
In a zero-sum game, there can only be a first-mover disadvantage. Going second gives a player the opportunity to adapt to what the other player does first. And the second player always has the option of choosing whatever mixed strategy she would have chosen had she gone first. But does going second ever strictly help? The Minimax theorem gives an amazing answer to the question above: {\em it doesn't matter!}
On the left-hand side of (ref), the row player moves first and the column player second. The column player plays optimally given the strategy chosen by the row player, and the row player plays optimally anticipating the column player's response. On the right-hand side of (ref), the roles of the two players are reversed. The Minimax theorem asserts that, under optimal play, the expected payoff of each player is the same in both scenarios.
The first proof of the Minimax theorem was due to von Neumann vN28 and used fixed-point-type arguments (which we'll have much more to say about later). von Neumann and Morgenstern vNM44, inspired by Ville V38, later realized that the Minimax theorem can be deduced from strong linear programming duality.\footnote{Dantzig D81 describes meeting John von Neumann on October 3, 1947: “In under a minute I slapped the geometric and the algebraic version of the [linear programming] problem on the blackboard. Von Neumann stood up and said `Oh that!' Then for the next hour and a half, he proceeded to give me a lecture on the mathematical theory of linear programs.
“At one point seeing me sitting there with my eyes popping and my mouth open (after all I had searched the literature and found nothing), von Neumann said: `I don't want you to think I am pulling all this out of my sleeve on the spur of the moment like a magician. I have just recently completed a book with Oskar Morgenstern on the Theory of Games. What I am doing is conjecturing that the two problems are equivalent.”
This equivalence between strong linear programming duality and the Minimax theorem is made precise in Dantzig D51, Gale et al. GKT51, and Adler A13.}
For example, the value of the rock-paper-scissors game is $0$ and $(u,u)$ is its unique min-max pair, where $u$ denotes the uniform probability distribution.
The min-max pairs are the optimal solutions of the two linear programs in the proof of Theorem (ref). Because the optimal solution of a linear program can be computed in polynomial time, so can a min-max pair.
In zero-sum games, a min-max pair is closely related to the notion of a Nash equilibrium, defined next.\footnote{If you think you learned this definition from the movie A Beautiful Mind, it's time to learn the correct definition!}
The pairs in Definition (ref) are sometimes called mixed Nash equilibria, to stress that players are allowed to randomize. (As opposed to a {\em pure} Nash equilibrium, where both players play deterministically.) Unless otherwise noted, we will always be concerned with mixed Nash equilibria.
There are several interesting consequences of Theorem (ref) and Proposition (ref):
Can we generalize Corollary (ref) to more general classes of games? After all, while two-player zero-sum games are important---von Neumann was largely focused on them, with applications ranging from poker to war---most game-theoretic situations are not purely zero-sum.\footnote{Games can even have a collaborative aspect, for example if you and I want to meet at some intersection in Manhattan. Our strategies are intersections, and either we both get a high payoff (if we choose the same strategy) or we both get a low payoff (otherwise).} For example, what about {\em bimatrix games}, in which there are still two players but the game is not necessarily zero-sum?\footnote{Notice that three-player zero-sum games are already more general than bimatrix games---to turn one of the latter into one of the former, add a dummy third player with only one strategy whose payoff is the negative of the combined payoff of the original two players. Thus the most compelling negative results would be for the case of bimatrix games.} Solar Lectures 4 and 5 are devoted to this question, and provide evidence that there is no polynomial-time algorithm for computing a Nash equilibrium (even an approximate one) of a bimatrix game.
Before proceeding to our second cool fact about two-player zero-sum games, let's take a step back and be clear about what we're trying to accomplish. Why do we care about computing equilibria of games, anyway?
In the first half of the lecture, we saw that a Nash equilibrium of a two-player zero-sum game can be computed in polynomial time using linear programming. It would be more compelling, however, to come up with a definition of a plausible process by which players can learn a Nash equilibrium. Such a result requires a behavioral model for what players do when not at equilibrium. The goal is then to investigate whether or not the process converges to a Nash equilibrium (for an appropriate notion of convergence), and if so, how quickly.
{\em Uncoupled dynamics} refers to a class of processes with the properties mentioned above. The idea is that each player initially knows only her own payoffs (and not those of the other players), \`{a} la the number-in-hand model in communication complexity.\footnote{If a player knows the game is zero-sum and also her own payoff matrix, then she automatically knows the other player's payoff matrix. Nonetheless, it is non-trivial and illuminating to investigate the convergence properties of general-purpose uncoupled dynamics in the zero-sum case, thereby identifying an aspiration point for the analysis of general games.} The game is then played repeatedly, with each player picking a strategy in each time step as a function only of her own payoffs and what transpired in the past.
Uncoupled dynamics have been studied at length in both the game theory and computer science literatures (often under different names). Specifying such dynamics boils down to a definition of how Alice and Bob choose strategies as a function of their payoffs and the joint history of play. Let's look at some famous examples.
One natural idea is to best respond to the observed behavior of your opponent.
Fictitious play has an interesting history:
Next we'll look at a different choice of dynamics with better convergence properties.
Fictitious play is “all-or-nothing”---even if two strategies have almost the same expected payoff against the opponent's empirical distribution, the slightly worse one is completely ignored in favor of the slightly better one. A more stable approach, and perhaps a more behaviorally plausible one, is to assume that players randomize, biasing their decision toward the strategies with the highest expected payoffs (again, against the empirical distribution of the opponent). In other words, each player plays a “noisy best response” against the observed play of the other player.
For example, already in 1957 Han57 considered dynamics where each player chooses a strategy with probability proportional to her expected payoff (against the empirical distribution of the other player's past play), and proved polynomial convergence to the Nash equilibrium payoffs in two-player zero-sum games. Even better convergence properties are possible if poorly performing strategies are abandoned more aggressively, corresponding to a “softmax” version of fictitious play.
Versions of smooth fictitious play have been studied independently in the game theory literature (beginning with FL95) and the computer science literature (beginning with FS99). It converges extremely quickly.
The $\epsilon$-approximate Nash equilibrium condition in Theorem (ref) is exactly what it sounds like: neither player can improve their expected payoff by more than $\epsilon$ via a unilateral deviation (see also Definition (ref), below).\footnote{Recall our assumption that payoffs have been scaled to lie in $[-1,1]$.}
There are two steps in the proof of Theorem (ref): (i) the noisy best response in smooth fictitious play is equivalent to the “Exponential Weights” algorithm, which has “vanishing regret”; and (ii) in a two-player zero-sum game, vanishing-regret guarantees translate to (approximate) Nash equilibrium convergence. The optional Sections (ref)--(ref) provide more details for the interested reader.
Theorem (ref) implies that smooth fictitious play can be used to define a randomized $O(\log^2 (n+m)/\epsilon^2)$-bit communication protocol for computing an $\epsilon$-$\mathsf{NE}$ of a two-player zero sum game.\footnote{This communication bound applies to the variant of smooth fictitious play where Alice (respectively, Bob) learns only a random sample from $y^t$ (respectively, $x^t$); see footnote (ref). Each such sample can be communicated to the other player in $\log (n+m)$ bits. Theorem (ref) continues to hold (with high probability over the samples) for this variant of smooth fictitious play FL95,FS99.} The goal of Solar Lectures 2 and 3 is to prove that there is no analogously efficient communication protocol for computing an approximate Nash equilibrium of a general bimatrix game.\footnote{The communication complexity of computing anything about a two-player zero-sum game is zero---Alice knows the entire game at the beginning (as Bob's payoff is the negative of hers) and can unilaterally compute whatever she wants. But it still makes sense to ask if the communication bound implied by smooth fictitious play can be replicated in non-zero-games (where Alice and Bob initially know only their own payoff matrices).} Ruling out low-communication protocols will in particular rule out any type of quickly converging uncoupled dynamics.\footnote{The relevance of communication complexity to fast learning in games was first pointed out by CS04.}
To elaborate on the first step of the proof of Theorem (ref), we need to explain the standard setup for online decision-making.
In smooth fictitious play, each of Alice and Bob are in effect solving the online decision-making problem (with actions corresponding to the game's strategies). For Alice, the reward vector $r^t$ is induced by Bob's action at time step $t$ (if Bob plays strategy $j$, then $r^t$ is the $j$th column of the game matrix $A$), and similarly for Bob (with reward vector equal to the $i$th row multiplied by $-1$). Next we interpret Alice's and Bob's behavior in smooth fictitious play as algorithms for online decision-making.
An {\em online decision-making algorithm} specifies for each $t$ the probability distribution $p^t$, as a function of the reward vectors $r^1,\ldots,r^{t-1}$ and realized actions $a^1,\ldots,a^{t-1}$ of the first $t-1$ time steps. An {\em adversary} for such an algorithm $\mathcal{A}$ specifies for each $t$ the reward vector $r^t$, as a function of the probability distributions $p^1,\ldots,p^t$ used by $\mathcal{A}$ on the first $t$ days and the realized actions $a^1,\ldots,a^{t-1}$ of the first $t-1$ days.
Here is a famous online decision-making algorithm, the “Exponential Weights (EW)” algorithm (see LW94,FS97).\footnote{Also known as the “Hedge” algorithm. The closely related “Multiplicative Weights” algorithm uses the update rule $w^{t+1}(a) = w^t(a) \cdot (1 + \eta^t r^t(a))$ instead of $w^{t+1}(a) = w^t(a) \cdot (e^{\eta^t r^t(a)})$ CBMS07.}
The EW algorithm maintains a weight, intuitively a “credibility,” for each action. At each time step the algorithm chooses an action with probability proportional to its current weight. The weight of each action evolves over time according to the action's past performance.
Inspecting the descriptions of smooth fictitious play and the EW algorithm, we see that we can rephrase the former as follows:
How should we assess the performance of an online decision-making algorithm like the EW algorithm, and do guarantees for the algorithm have any implications for smooth fictitious play?
One of the big ideas in online learning is to compare the time-averaged reward earned by an online algorithm with that earned by the best {\em fixed action} in hindsight.\footnote{There is no hope of competing with the best action {\em sequence} in hindsight: consider two actions and an adversary that flips a coin each time step to choose between the reward vectors $(1,0)$ and $(0,1)$.}
Note that, by linearity, there is no difference between considering the best fixed action and the best fixed distribution over actions (there is always an optimal pure action in hindsight).
We aspire to an online decision-making algorithm that achieves low regret, as close to 0 as possible. Because rewards lie in $[-1,1]$, the regret can never be larger than 2. We think of regret $\Omega(1)$ (as $T \rightarrow \infty$) as an epic fail for an algorithm.
It turns out that the EW algorithm has the best-possible worst-case regret guarantee (up to constant factors).\footnote{For the matching lower bound, with $n$ actions, consider an adversary that sets the reward of each action uniformly at random from $\{-1,1\}$ at each time step. Every online algorithm earns expected cumulative reward 0, while the expected cumulative reward of the best action in hindsight is $\Theta(\sqrt{T} \cdot \sqrt{\log n})$.}
See e.g. the book of CBL06 for a proof of Theorem (ref), which is not overly difficult.
An immediate corollary is that the number of time steps needed to drive the expected regret down to a small constant is only logarithmic in the number of actions---this is surprisingly fast!
Consider a zero-sum game $A$ with payoffs in $[-1,1]$ and some $\epsilon > 0$. Let $n$ denote the number of rows or the number of columns, whichever is larger, and set $T = \Theta((\log n)/\epsilon^2)$ so that the guarantee in Corollary (ref) holds with error $\epsilon/2$. Let $x^1,\ldots,x^T$ and $y^1,\ldots,y^T$ be the mixed strategies used by Alice and Bob throughout $T$ steps of smooth fictitious play. Let $\hat{x} = \tfrac{1}{T} \sum_{t=1}^T x^t$ and $\hat{y} = \tfrac{1}{T} \sum_{t=1}^T y^t$ denote the time-averaged strategies of Alice and Bob, respectively. We claim that $(\hat{x},\hat{y})$ is an $\epsilon\text{-}\mathsf{NE}$.
In proof, let \[ v = \frac{1}{T} \sum_{t=1}^T (x^t)^{\top}Ay^t \] denote Alice's time-averaged payoff. Alice and Bob both used (in effect) the EW algorithm to choose their strategies, so we can apply the vanishing regret guarantee in Corollary (ref) once for each player and use linearity to obtain
and
In particular, taking $x = \hat{x}$ in (ref) and $y = \hat{y}$ in (ref) shows that
Now consider a (pure) deviation from $(\hat{x},\hat{y})$, say by Alice to the row $i$. Denote this deviation by $e_i$. By inequality (ref) (with $x = e_i$) we have
Because Alice receives expected payoff at least $v-\tfrac{\epsilon}{2}$ in $(\hat{x},\hat{y})$ (by (ref)) and at most $v+\tfrac{\epsilon}{2}$ from any deviation (by (ref)), her $\epsilon\text{-}\mathsf{NE}$ conditions are satisfied. A symmetric argument applies to Bob, completing the proof.
A general bimatrix game is defined by two independent payoff matrices, an $m \times n$ matrix $A$ for Alice and an $m \times n$ matrix $B$ for Bob. (In a zero-sum game, $B=-A$.) The definition of an (approximate) Nash equilibrium is what you'd think it would be:
It has long been known that many of the nice properties of zero-sum games break down in general bimatrix games.\footnote{We already mentioned Shapley's 1964 example showing that fictitious play need not converge S64.}
Example (ref) shows that, unlike in zero-sum games, different Nash equilibria can result in different expected player payoffs. Similarly, the Nash equilibria of a bimatrix game do not generally form a convex set (unlike in the zero-sum case).
Nash equilibria of bimatrix games are not completely devoid of nice properties, however. For starters, we have guaranteed existence.
The proof is a fixed-point argument that we will have more to say about in Solar Lecture 2.\footnote{Von Neumann's alleged reaction when Nash told him his theorem nasar: “That's trivial, you know. That's just a fixed point theorem.”} Nash's theorem holds more generally for games with any finite number of players and strategies.
Nash equilibria of bimatrix games have nicer structure than those in games with three or more players. First, in bimatrix games with integer payoffs, there is a Nash equilibrium in which all probabilities are rational numbers with bit complexity polynomial in that of the game.\footnote{Exercise: prove this by showing that, after you've guessed the two support sets of a Nash equilibrium, you can recover the exact probabilities using two linear programs.} Second, there is a simplex-type pivoting algorithm, called the {\em Lemke-Howson algorithm} LH64, which computes a Nash equilibrium of a bimatrix game in a finite number of steps (see vS07 for a survey). Like the simplex method, the Lemke-Howson algorithm takes an exponential number of steps in the worst case M94,SvS04. The similarities between Nash equilibria of bimatrix games and optimal solutions of linear programs initially led to some optimism that computing the former might be as easy as computing the latter (i.e., might be a polynomial-time solvable problem). Alas, as we'll see, this does not seem to be the case.
The last topic of this lecture is some semi-positive results about {\em approximate} Nash equilibria in general bimatrix games. While simple, these results are important and will show up repeatedly in the rest of the lectures.
Here is a crucial result for us: there are always {\em sparse} approximate Nash equilibria.\footnote{A94 and LY94 independently proved a precursor to this result in the special case of zero-sum games. The focus of the latter paper is applications in complexity theory (like “anticheckers”).}\footnote{Exercise: there are arbitrarily large games where every exact Nash equilibrium has full support. Hint: generalize rock-paper-scissors. Alternatively, see Section (ref) of Solar Lecture 5.}
Theorem (ref) immediately implies the existence of an $\epsilon\text{-}\mathsf{NE}$ of an $n \times n$ bimatrix game with description length $O((\log^2 n)/\epsilon^2)$, with $\approx \log n$ bits used to describe each of the $O((\log n)/\epsilon^2)$ pure strategies in the multi-sets promised by the theorem. Moreover, if an all-powerful prover writes down an alleged such description on a publicly observable blackboard, then Alice and Bob can privately verify that the described pair of mixed strategies is indeed an $\epsilon\text{-}\mathsf{NE}$. For example, Alice can use the (publicly viewable) description of Bob's mixed strategy to compute the expected payoff of her best response and check that it is at most $\epsilon$ more than her expected payoff when playing the mixed strategy suggested by the prover. Summarizing:
Thus, if there {\em is} a polynomial lower bound on the deterministic or randomized communication complexity of computing an approximate Nash equilibrium, the only way to prove it is via techniques that don't automatically apply also to the problem's nondeterministic communication complexity. This observation rules out many of the most common lower bound techniques. In Solar Lectures 2 and 3, we'll see how to thread the needle using a {\em simulation theorem}, which lifts a deterministic or random query (i.e., decision tree) lower bound to an analogous communication complexity lower bound.
The second important consequence of Theorem (ref) is a limit on the strongest-possible computational hardness we could hope to prove for the problem of computing an approximate Nash equilibrium of a bimatrix game: at worst, the problem is quasi-polynomial-hard.
Because of the apparent paucity of natural problems with quasi-polynomial complexity, the quasi-polynomial-time approximation scheme (QPTAS) in Corollary (ref) initially led to optimism that there should be a PTAS for the problem. Also, if there {\em were} a reduction showing quasi-polynomial-time hardness for computing an approximate Nash equilibrium, what would be the appropriate complexity assumption, and what would the reduction look like? Solar Lectures 4 and 5 answer this question.
\chapter{Communication Complexity Lower Bound for Computing an Approximate Nash Equilibrium of a Bimatrix Game (Part I)} \titlerule
This lecture and the next consider the communication complexity of computing an approximate Nash equilibrium, culminating with a proof of the recent breakthrough polynomial lower bound of BR17. This lower bound rules out the possibility of quickly converging uncoupled dynamics in general bimatrix games (see Section (ref)).
Recall the setup: there are two players, Alice and Bob, each with their own payoff matrices $A$ and $B$. Without loss of generality (by padding), the two players have the same number $N$ of strategies. We consider a two-party model where, initially, Alice knows only $A$ and Bob knows only $B$. The goal is then for Alice and Bob to compute an approximate Nash equilibrium (Definition (ref)) with as little communication as possible.
This lecture and the next explain all of the main ideas behind the following result:
For our purposes, a randomized protocol with communication cost $b$ always uses at most $b$ bits of communication, and terminates with at least one player knowing an $\epsilon\text{-}\mathsf{NE}$ of the game with probability at least $\tfrac{1}{2}$ (over the protocol's coin flips).
Thus, while there are lots of obstacles to players reaching an equilibrium of a game (see also Section (ref)), communication alone is already a significant bottleneck. A corollary of Theorem (ref) is that there can be no uncoupled dynamics (Section (ref)) that converge to an approximate Nash equilibrium in a sub-polynomial number of rounds in general bimatrix games (cf., the guarantee in Theorem (ref) for smooth fictitious play in zero-sum games). This is because uncoupled dynamics can be simulated by a randomized communication protocol with logarithmic overhead (to communicate which strategy gets played each round).\footnote{See also footnote (ref) in Solar Lecture 1.} This corollary should be regarded as a fundamental contribution to pure game theory and economics.
The goal of this and the next lecture is to sketch a full proof of the lower bound in Theorem (ref) for deterministic communication protocols. We do really care about randomized protocols, however, as these are the types of protocols induced by uncoupled dynamics (see Section (ref)). The good news is that the argument for the deterministic case will already showcase all of the conceptual ideas in the proof of Theorem (ref). Extending the proof to randomized protocols requires substituting a simulation theorem for randomized protocols (we'll use only a simulation theorem for deterministic protocols, see Theorem (ref)) and a few other minor tweaks.\footnote{When BR17 first proved their result (in late 2016), the state-of-the-art in simultaneous theorems for randomized protocols was much more primitive than for deterministic protocols. This forced BR17 to use a relatively weak simulation theorem for the randomized case (by G+16), which led to a number of additional technical details in the proof. Amazingly, a full-blown randomized simulation theorem was published shortly thereafter A+17,GPW17! With this in hand, extending the argument here for deterministic protocols to randomized protocols is relatively straightforward.}
To illustrate the difficulty of proving a result like Theorem (ref), consider a naive attempt that tries to reduce, say, the {\sc Disjointness}\xspace problem to the problem of computing an $\epsilon$-$\mathsf{NE}$, with YES-instances mapped to games in which all equilibria have some property $\Pi$, and NO-instances mapped to games in which no equilibrium has property $\Pi$ (Figure (ref)).\footnote{Recall the {\sc Disjointness}\xspace function: Alice and Bob have input strings $a,b \in \{0,1\}^n$, and the output of the function is “0” if there is a coordinate $i \in \{1,2,\ldots,n\}$ with $a_i = b_i = 1$ and “1” otherwise. One of the first things you learn in communication complexity is that the nondeterministic communication complexity of {\sc Disjointness}\xspace (for certifying 1-inputs) is $n$ (see e.g. KN96,w15). And of course one of the most famous and useful results in communication complexity is that the function's randomized communication complexity (with two-sided error) is $\Omega(n)$ KS92,R92.} For the reduction to be useful, $\Pi$ needs to be some property that can be checked with little to no communication, such as “Alice plays her first strategy with positive probability” or “Bob's strategy has full support.” The only problem is that {\em this is impossible!} The reason is that the problem of computing an approximate Nash equilibrium has polylogarithmic {\em nondeterministic} communication complexity (because of the existence of sparse approximate equilibria, see Theorem (ref) and Corollary (ref)), while the {\sc Disjointness}\xspace function does not (for 1-inputs). A reduction of the proposed form would translate a nondeterministic lower bound for the latter problem to one for the former, and hence cannot exist.\footnote{Mika G\"o\"os (personal communication, January 2018) points out that there are more clever reductions from {\sc Disjointness}\xspace, starting with Raz and Wigderson RW90, that {\em can} imply strong lower bounds on the randomized communication complexity of certain problems with low nondeterministic communication complexity; and that it is plausible that a Raz-Wigderson-style proof, such as that for search problems in G\"o\"os and Pitassi GP18, could be adapted to give an alternative proof of Theorem (ref).}
Our failed reduction highlights two different challenges. The first is to resolve the typechecking error that we encountered between a standard decision problem, where there might or might not be a witness (like {\sc Disjointness}\xspace, where a witness is an element in the intersection), and a total search problem where there is always a witness (like computing an approximate Nash equilibrium, which is guaranteed to exist by Nash's theorem). The second challenge is to figure out how to prove a strong lower bound on the deterministic or randomized communication complexity of computing an approximate Nash equilibrium without inadvertently proving the same (non-existent) lower bound for nondeterministic protocols. To resolve the second challenge, we'll make use of simulation theorems that lift query complexity lower bounds to communication complexity lower bounds (see Section (ref)); these are tailored to a specific computational model, like deterministic or randomized protocols. For the first challenge, we need to identify a total search problem with high communication complexity. That is, for total search problems, which should be the analog of {\sc 3SAT} or {\sc Disjointness}\xspace? The correct answer turns out to be {\em fixed-point computation}.
This section and the next describe reductions from computing Nash equilibria to computing fixed points, and from computing fixed points to a path-following problem. These reductions are classical. The ingredients of the proof in Theorem (ref) are {\em reductions in the opposite direction}; these are discussed in Solar Lecture 3.
{\em Brouwer's fixed-point theorem} states that whenever you stir your coffee, there will be a point that ends up exactly where it began. Or if you prefer a more formal statement:
All of the hypotheses are necessary.\footnote{If convexity is dropped, consider rotating an annulus centered at the origin. If boundedness is dropped, consider $x \mapsto x+1$ on ${\mathbb R}$. If closedness is dropped, consider $x \mapsto \tfrac{x}{2}$ on $(0,1]$. If continuity is dropped, consider $x \mapsto (x+ \tfrac{1}{2}) \bmod 1$ on $[0,1]$. Many more general fixed-point theorems are known, and find applications in economics and elsewhere; see e.g. B85,M15.} We will be interested in a computational version of Brouwer's fixed-point theorem, the {\em {\sc $\epsilon$-BFP}\xspace problem}:
The {\sc $\epsilon$-BFP}\xspace problem, in its many different forms, plays a starring role in the study of equilibrium computation. The set $C$ is typically fixed in advance, for example to the $d$-dimensional hypercube. While much of the work on the {\sc $\epsilon$-BFP}\xspace problem has focused on the $\ell_{\infty}$ norm (e.g. HPV89), one innovation in the proof of Theorem (ref) is to instead use a normalized version of the $\ell_2$ norm (following R16).
Nailing down the problem precisely requires committing to a family of succinctly described continuous functions $f$. The description of the family used in the proof of Theorem (ref) is technical and best left to Section (ref). Often (and in these lectures), the family of functions considered contains only $O(1)$-Lipschitz functions.\footnote{Recall that a function $f$ mapping a metric space $(X,d)$ to itself is {\em $\lambda$-Lipschitz} if $d(f(x),f(y)) \le \lambda \cdot d(x,y)$ for all $x,y \in X$. That is, the function can only amplify distances between points by a $\lambda$ factor.} In particular, this guarantees the existence of an $\epsilon$-approximate fixed point with description length polynomial in the dimension and $\log \tfrac{1}{\epsilon}$ (by rounding an exact fixed point to its nearest neighbor on a suitably defined grid).
Fixed-point theorems have long been used to prove equilibrium existence results, including the original proofs of the Minimax theorem (Theorem (ref)) and Nash's theorem (Theorem (ref)).\footnote{In fact, the story behind von Neumann's original proof of the Minimax theorem is a little more complicated and nuanced; see K01 for a fascinating and detailed discussion.} Analogously, algorithms for computing (approximate) fixed points can be used to compute (approximate) Nash equilibria.
To provide further details, let's sketch why Nash's theorem (Theorem (ref)) reduces to Brouwer's fixed-point theorem (Theorem (ref)), following the version of the argument in G03.\footnote{This discussion is borrowed from f13.} Consider a bimatrix game $(A,B)$ and let $S_1,S_2$ denote the strategy sets of Alice and Bob (i.e., the rows and columns). The relevant convex compact set is $C = \Delta_1 \times \Delta_2$, where $\Delta_i$ is the simplex representing the mixed strategies over $S_i$. We want to define a continuous function $f:C \rightarrow C$, from mixed strategy profiles to mixed strategy profiles, such that the fixed points of $f$ are the Nash equilibria of this game. We define $f$ separately for each component $f_i:C \rightarrow \Delta_i$ for $i=1,2$. A natural idea is to set $f_i$ to be a best response of player $i$ to the mixed strategy of the other player. This does not lead to a continuous, or even well defined, function. We can instead use a “regularized” version of this idea, defining
where
and similarly for $f_2$ and $g_2$ (with Bob's payoff matrix $B$). The first term of the function $g_i$ encourages a best response while the second “penalty term” discourages big changes to player $i$'s mixed strategy. Because the function $g_i$ is strictly concave in $x'_i$, $f_i$ is well defined. The function $f=(f_1,f_2)$ is continuous (as you should check). By definition, every Nash equilibrium of the given game is a fixed point of $f$. For the converse, suppose that $(x_1,x_2)$ is not a Nash equilibrium, with Alice (say) able to increase her expected payoff by deviating unilaterally from $x_1$ to $x'_1$. A simple computation shows that, for sufficiently small $\epsilon > 0$, $g_1((1-\epsilon)x_1 + \epsilon x'_1,x_2) > g_1(x_1,x_2)$, and hence $(x_1,x_2)$ is not a fixed point of $f$ (as you should check).
Summarizing, an oracle for computing a Brouwer fixed point immediately gives an oracle for computing a Nash equilibrium of a bimatrix game. The same argument applies to games with any (finite) number of players. The same argument also shows that an oracle for computing an $\epsilon$-approximate fixed point in the $\ell_{\infty}$ norm can be used to compute an $O(\epsilon)$-approximate Nash equilibrium of a game. The first high-level goal of the proof of Theorem (ref) is to reverse the direction of the reduction---to show that the problem of computing an approximate Nash equilibrium is as general as computing an approximate fixed point, rather than merely being a special case.
This goal follows in the tradition of a sequence of celebrated computational hardness results last decade for computing an exact Nash equilibrium (or an $\epsilon$-approximate Nash equilibrium with $\epsilon$ polynomial in $\tfrac{1}{n}$) DGP09,CDT09.
There are a couple of immediate issues. First, it's not clear how to meaningfully define the {\sc $\epsilon$-BFP}\xspace problem in a two-party communication model---what are Alice's and Bob's inputs? We'll address this issue in Section (ref). Second, even if we figure out how to define the {\sc $\epsilon$-BFP}\xspace problem and implement goal \#1, so that the $\epsilon\text{-}\mathsf{NE}$ problem is at least as hard as the {\sc $\epsilon$-BFP}\xspace problem, what makes us so sure that the latter is hard? This brings us to our next topic---a “generic” total search problem that is hard almost by definition and can be used to transfer hardness to other problems (like {\sc $\epsilon$-BFP}\xspace) via reductions.\footnote{For an analogy, a “generic” hard decision problem for the complexity class $\mathsf{NP}$ is: given a description of a polynomial-time verifier, does there exist a witness (i.e., an input accepted by the verifier)?}
For equilibrium and fixed-point computation problems, it turns out that the appropriate “generic” problem involves following a path in a large graph; see also Figure (ref).
The restriction on the in- and out-degrees forces the graph $G$ to consist of vertex-disjoint paths and cycles, with at least one path (starting at the source $s$). The {\sc EoL}\xspace problem is a total search problem---there is always a solution, if nothing else the other end of the path that starts at $s$. Thus an instance of {\sc EoL}\xspace can always be solved by rotely following the path from $s$; the question is whether or not there is a more clever algorithm that always avoids searching the entire graph.
It should be plausible that the {\sc EoL}\xspace problem is hard, in the sense that there is no algorithm that always improves over rote path-following; see also Section (ref). But what does it have to do with the {\sc $\epsilon$-BFP}\xspace problem? A lot, it turns out.
The basic reason that fixed-point computation reduces to path-following is {\em Sperner's lemma}, which we recall next (again borrowing from f13). Consider a subdivided triangle in the plane (Figure (ref)). A {\em legal coloring} of its vertices colors the top corner vertex red, the left corner vertex green, and the right corner vertex blue. A vertex on the boundary must have one of the two colors of the endpoints of its side. Internal vertices are allowed to possess any of the three colors. A small triangle is {\em trichromatic} if all three colors are represented at its vertices.
Sperner's lemma then asserts that for every legal coloring, there is at least one trichromatic triangle.\footnote{The same result and proof extend by induction to higher dimensions. Every subdivided simplex in ${\mathbb R}^n$ with vertices legally colored with $n+1$ colors has an odd number of panchromatic subsimplices, with a different color at each vertex.}
The proof of Sperner's lemma shows that following a path from a canonical source vertex in a suitable graph leads to a trichromatic triangle. Thus, computing a trichromatic triangle of a legally colored subdivided triangle reduces to the {\sc EoL}\xspace problem. \footnote{We're glossing over some details. The graph in an instance of {\sc EoL}\xspace is directed, while the graph $G$ defined in the proof of Theorem (ref) is undirected. There is, however, a canonical way to direct the edges of the graph $G$. Also, the canonical source vertex in an {\sc EoL}\xspace instance has out-degree 1, while the source of the graph $G$ has degree $2k-1$ for some positive integer $k$. This can be rectified by splitting the source vertex of $G$ into $k$ vertices, a source vertex with out-degree 1 and $k-1$ vertices with in- and out-degree 1.}
Next we'll use Sperner's lemma to prove Brouwer's fixed-point theorem for a 2-dimensional simplex $\Delta$; higher-dimensional versions of Sperner's lemma (see footnote (ref)) similarly imply Brouwer's fixed-point theorem for simplices of arbitrary dimension.\footnote{Every compact convex subset of finite-dimensional Euclidean space is homeomorphic to a simplex of the same dimension (by scaling and radial projection, essentially), and homeomorphisms preserve fixed points, so Brouwer's fixed-point theorem carries over from simplices to all compact convex subsets of Euclidean space.} Let $f:\Delta \rightarrow \Delta$ be a $\lambda$-Lipschitz function (with respect to the $\ell_2$ norm, say).
Brouwer's fixed-point theorem now follows by taking the limit $\epsilon \rightarrow 0$ and using the continuity of $f$.
The second high-level goal of the proof of Theorem (ref) is to reverse the direction of the above reduction from {\sc $\epsilon$-BFP}\xspace to {\sc EoL}\xspace. That is, we would like to show that the problem of computing an approximate Brouwer fixed point is as general as every path-following problem (of the form in {\sc EoL}\xspace), rather than merely being a special case.
If we succeed in implementing goals \#1 and \#2, and also prove directly that the {\sc EoL}\xspace problem is hard, then we'll have proven hardness for the problem of computing an approximate Nash equilibrium.
The high-level plan for the proof in the rest of this and the next lecture is to show that \[ \text{a low-cost communication protocol for $\epsilon\text{-}\mathsf{NE}$} \] implies \[ \text{a low-cost communication protocol for $\epsilon$-{\sc 2BFP}\xspace}, \] where $\epsilon$-{\sc 2BFP}\xspace is a two-party version of the problem of computing a fixed point (to be defined), which then implies \[ \text{a low-cost communication protocol for {\sc 2EoL}\xspace}, \] where {\sc 2EoL}\xspace is a two-party version of the {\sc EoL}\xspace problem (to be defined), which then implies \[ \text{a low-query algorithm for {\sc EoL}\xspace}. \] Finally, we'll prove directly that the {\sc EoL}\xspace problem does not admit a low-query algorithm. This gives us four things to prove (hardness of {\sc EoL}\xspace and the three implications); we'll tackle them one by one in reverse order:
The first step (Section (ref)) is easy. The second step (Section (ref)) follows directly from one of the simulation theorems alluded to in Section (ref). The last two steps, which correspond to goals \#2 and \#1, respectively, are harder and deferred to Solar Lecture 3.
Most of the ingredients in this road map were already present in a paper by Roughgarden and Weinstein RW16, which was the first paper to define and study two-party versions of fixed-point computation problems, and to propose the use of simulation theorems in the context of equilibrium computation. One major innovation in BR17 is the use of the generic {\sc EoL}\xspace problem as the base of the reduction, thereby eluding the tricky interactions in RW16 between simulation theorems (which seem inherently combinatorial) and fixed-point problems (which seem inherently geometric). RW16 applied a simulation theorem directly to a fixed-point problem (relying on strong query complexity lower bounds for finding fixed points HPV89,B16), which yielded a hard but unwieldy version of a two-party fixed-point problem. It is not clear how to reduce this version to the problem of computing an approximate Nash equilibrium. BR17 instead apply a simulation theorem directly to the {\sc EoL}\xspace problem, which results in a reasonably natural two-party version of the problem (see Section (ref)). There is significant flexibility in how to interpret this problem as a two-party fixed-point problem, and the interpretation in BR17 (see Section (ref)) yields a version of the problem that is hard and yet structured enough to be solved using approximate Nash equilibrium computation. A second innovation in BR17 is the reduction from $\epsilon$-{\sc 2BFP}\xspace to $\epsilon\text{-}\mathsf{NE}$ (see Section (ref)) which, while not difficult, is both new and clever.\footnote{Very recently, GKP19 showed how to implement directly the road map of RW16, thereby giving an alternative proof of Theorem (ref).}
We consider the following “oracle” version of the {\sc EoL}\xspace problem. The vertex set $V$ is fixed to be $\{0,1\}^n$. Let $N = |V| = 2^n$. Algorithms are allowed to access the graph only through vertex queries. A query to the vertex $v$ reveals its alleged predecessor $pred(v)$ (if any, otherwise $pred(v)$ is NULL) and its alleged successor $succ(v)$ (or NULL if it has no successor). The interpretation is that the directed edge $(v,w)$ belongs to the implicitly defined directed graph $G=(V,E)$ if and only if both $succ(v)=w$ and $pred(w)=v$. These semantics guarantee that the graph has in- and out-degree at most 1.\footnote{For the proof of Theorem (ref), we could restrict attention to instances that are consistent in the sense that $succ(v)=w$ if and only if $pred(w)=v$. The computational hardness results in Solar Lectures 4 and 5 require the general (non-promise) version of the problem stated here.} We also assume that $pred(0^n)=NULL$, and interpret the vertex $0^n$ as the a priori known source vertex of the graph.
The version of the {\sc EoL}\xspace problem for this oracle model is:
According to our semantics, cases (iii) and (iv) imply that $v$ is a sink and source vertex, respectively. A solution is guaranteed to exist---if nothing else, the other end of the path of $G$ that originates with the vertex $0^n$.
It will sometimes be convenient to restrict ourselves to a “promise” version of the {\sc EoL}\xspace problem (which can only be easier), where the graph $G$ is guaranteed to be a single Hamiltonian path. Even in this special case, because every vertex query reveals information about at most three vertices, we have the following.
Slightly more formally, consider an adversary that always responds with values of $succ(v)$ and $pred(v)$ that are never-before-seen vertices (except as necessary to maintain the consistency of all of the adversary's answers, so that cases (iii) and (iv) never occur). After only $o(N)$ queries, the known parts of $G$ constitute a bunch of vertex-disjoint paths, and $G$ could be any Hamiltonian path of $V$ consistent with these. The end of this Hamiltonian path could be any of $\Omega(N)$ different vertices, and the algorithm has no way of knowing which one.\footnote{A similar argument, based on choosing a Hamiltonian path of $V$ at random, implies an $\Omega(N)$ lower bound for the randomized query complexity as well.}
Our next step is to use a “simulation theorem” to transfer our query lower bound for the {\sc EoL}\xspace problem to a communication lower bound for a two-party version of the problem, {\sc 2EoL}\xspace.\footnote{This monograph does not reflect a beautiful lecture given by Omri Weinstein at the associated workshop on the history and applications of simulation theorems (e.g., to the first non-trivial lower bounds for the clique vs.\ independent set problem G15). Contact him for his slides!} The exact definition of the {\sc 2EoL}\xspace problem will be determined by the output of the simulation theorem.
Consider an arbitrary function $f:\Sigma^N \rightarrow \Sigma$, where $\Sigma$ denotes a finite alphabet. There is an input $\mathbf{z} = (z_1,\ldots,z_N) \in \Sigma^N$, initially unknown to an algorithm. The algorithm can query the input $\mathbf{z}$ adaptively, with each query revealing $z_i$ for a coordinate $i$ of the algorithm's choosing. It is trivial to evaluate $f(\mathbf{z})$ using $N$ queries; the question is whether or not there is an algorithm that always does better (for some function $f$ of interest). For example, the query version of the {\sc EoL}\xspace problem in Proposition (ref) can be viewed as a special case of this model, with $\Sigma = \{0,1\}^n \times \{0,1\}^n$ (to encode $pred(v)$ and $succ(v)$) and $f(\mathbf{z})$ encoding the (unique) vertex at the end of the Hamiltonian path.
We now describe how a function $f:\Sigma^N \rightarrow \Sigma$ as above induces a two-party communication problem. The idea is to “factor” the input $\mathbf{z}=(z_1,\ldots,z_N)$ to the query version of the problem between Alice and Bob, so that neither player can unilaterally figure out any coordinate of $\mathbf{z}$. We use an {\sc Index}\xspace gadget for this purpose, as follows. (See also Figure (ref).)
Note that the $y_i$th entry of $A_i$---Bob's index into Alice's block---is playing the role of $z_i$ in the original problem. Thus each block $A_i$ of Alice's input can be thought of as a “bag of garbage,” which tells Alice a huge number of possible values for the $i$th coordinate of the input without any clue about which is the real one. Meanwhile, Bob's indices tell him the locations of the real values, without any clues about what these values are.
If $f$ can be evaluated with a query algorithm that always uses at most $q$ queries, then the induced two-party problem can be solved using $O(q \log N)$ bits of communication. For Alice can just simulate the query algorithm; whenever it needs to query the $i$th coordinate of the input, Alice asks Bob for his index $y_i$ and supplies the query algorithm with $A_i[y_i]$. Each of the at most $q$ questions posed by Alice can be communicated with $\approx \log N$ bits, and each answer from Bob with $\approx \log M = O(\log N)$ bits.
There could also be communication protocols for the two-party problem that look nothing like such a straightforward simulation. For example, Alice and Bob could send each other the exclusive-or of all of their input bits. It's unclear why this would be useful, but it's equally unclear how to prove that it {\em can't} be useful. The remarkable {\em Raz-McKenzie simulation theorem} asserts that there are no communication protocols for the two-party problem that improve over the straightforward simulation of a query algorithm.
The proof, which is not easy but also not unreadable, shows how to extract a good query algorithm from an arbitrary low-cost communication protocol (essentially by a potential function argument).
The original Raz-McKenzie theorem DBLP:journals/combinatorica/RazM99 and the streamlined version by GPW18 are both restricted to deterministic algorithms and protocols, and this is the version we'll use in this monograph. Recently, GPW17 and A+17 proved the analog of Theorem (ref) for randomized query algorithms and randomized communication protocols (with two-sided error).\footnote{Open question: prove a simulation theorem for quantum computation.} This randomized simulation theorem simplifies the original proof of Theorem (ref) (which pre-dated GPW17,A+17) to the point that it's almost the same as the argument given here for the deterministic case.\footnote{For typechecking reasons, the argument for randomized protocols needs to work with a decision version of the {\sc EoL}\xspace problem, such as “is the least significant bit of the vertex at the end of the Hamiltonian path equal to 1?”}
The Raz-McKenzie theorem provides a generic way to generate a hard communication problem from a hard query problem. We can apply it in particular to the {\sc EoL}\xspace problem, and we call the induced two-party problem {\sc 2EoL}\xspace.\footnote{DBLP:journals/combinatorica/RazM99 stated their result for the binary alphabet and for total functions. GPW18 note that it applies more generally to arbitrary alphabets and partial functions, which is important for its application here. For further proof details of these extensions, see RW16.}
The next statement is an immediate consequence of Proposition (ref) and Theorem (ref).
A matching upper bound of $O(N \log N)$ is trivial, as Bob always has the option of sending Alice his entire input.
Corollary (ref) concludes the second step of the proof of Theorem (ref) and furnishes a generic hard total search problem. The next order of business is to transfer this communication complexity lower bound to the more natural {\sc $\epsilon$-BFP}\xspace and $\epsilon\text{-}\mathsf{NE}$ problems via reductions.
\chapter{Communication Complexity Lower Bound for Computing an Approximate Nash Equilibrium of a Bimatrix Game (Part II)} \titlerule
This lecture completes the proof of Theorem (ref). As a reminder, this result states that if Alice's and Bob's private inputs are the two payoff matrices of an $N \times N$ bimatrix game, and $\epsilon$ is a sufficiently small constant, then $N^{\Omega(1)}$ communication is required to compute an $\epsilon$-approximate Nash equilibrium (Definition (ref)), even when randomization is allowed. In terms of the proof road map in Section (ref), it remains to complete steps 3 and 4. This corresponds to implementing Goals \#1 and \#2 introduced in the last lecture---reversing the direction of the classical reductions from the {\sc $\epsilon$-BFP}\xspace problem to path-following and from the $\epsilon\text{-}\mathsf{NE}$ problem to the {\sc $\epsilon$-BFP}\xspace problem.
We know from Corollary (ref) that {\sc 2EoL}\xspace, the two-party version of the {\sc End-of-the-Line} problem defined in Section (ref), has large communication complexity. This section transfers this lower bound to a two-party version of an approximate fixed point problem, by reducing the {\sc 2EoL}\xspace problem to it.
We next define our two-party version of the {\sc $\epsilon$-BFP}\xspace problem, the $\epsilon$-{\sc 2BFP}\xspace problem. The problem is parameterized by the dimension $d$ and an approximation parameter $\epsilon$. The latter should be thought of as a sufficiently small constant (independent of $d$).
The normalized $\ell_2$ norm of a point in the hypercube (or the difference between two such points) is always between 0 and 1. If a point $x \in H$ is {\em not} an $\epsilon$-approximate fixed point with respect to this norm, then $f(x)$ and $x$ differ by a constant amount in a constant fraction of the coordinates. This version of the problem can only be easier than the more traditional version, which uses the $\ell_{\infty}$ norm.
To finish the description of the $\epsilon$-{\sc 2BFP}\xspace problem, we need to explain how Alice and Bob interpret their inputs as jointly defining a continuous function.
Our reduction from {\sc 2EoL}\xspace to $\epsilon$-{\sc 2BFP}\xspace will use no communication---Alice and Bob will simply reinterpret their {\sc 2EoL}\xspace inputs as $\epsilon$-{\sc 2BFP}\xspace inputs in a specific way, and a solution to the {\sc 2EoL}\xspace instance will be easy to recover from any approximate fixed point.
Figure (ref) shows the key intuition: graphs of paths and cycles naturally lead to continuous functions, where the gradient of the function “follows the line” and fixed points correspond to sources and sinks of the graph. Following the line (i.e., “gradient ascent”) guarantees discovery of an approximate fixed point; the goal will be to show that no cleverer algorithm is possible.
This idea originates in HPV89, who considered approximate fixed points in the $\ell_{\infty}$ norm. R16 showed how to modify the construction so that it works even for the normalized $\ell_2$ norm. BR17 used the construction from R16 in their proof of Theorem (ref); our treatment here includes some simplifications.
Before explaining exactly how to interpret graphs as continuous functions, we need to set up an embedding of every possible graph on a given vertex set into the hypercube.
Let $V = \{0,1\}^n$ and $N=|V|=2^n$. Let $K$ denote the complete undirected graph with vertex set $V$---all edges that could conceivably be present in an {\sc EoL}\xspace instance (ignoring their orientations). Decide once and for all on an embedding $\sigma$ of $K$ into $H=[0,1]^d$, where $d = \Theta(n) = \Theta(\log N)$, with two properties:\footnote{By an {\em embedding}, we mean a function $\sigma$ that maps each edge $(v,w)$ of $K$ to a continuous path in $H$ with endpoints $\sigma(v)$ and $\sigma(w)$.}
Property (P1) asserts that the images of two different vertices differ by a constant amount in a constant fraction of their coordinates.\footnote{In the original construction of HPV89, vertices of $K$ could potentially be mapped to points of $H$ that differ significantly in only one coordinate. This construction is good enough to prevent spurious approximate fixed points in the $\ell_{\infty}$ norm, but not in the normalized $\ell_2$ norm.} One natural way to achieve this property is via an error-correcting code with constant rate. The simplest way to achieve both properties is to take a random straight-line embedding. Each vertex $v \in V$ is mapped to a point in $\{ \tfrac{1}{4}, \tfrac{3}{4} \}^d$, with each coordinate set to $\tfrac{1}{4}$ or $\tfrac{3}{4}$ independently with 50/50 probability.\footnote{For reasons related to the omitted technical details, it's convenient to have a “buffer zone” between the embedding of the graph and the boundary of the hypercube.} Each edge is mapped to a straight line between the images of its endpoints. Provided $d=cn$ for a sufficiently large constant $c$, properties (P1) and (P2) both hold with high probability.\footnote{In the two-party communication model, we need not be concerned about efficiently constructing such an embedding. Because Alice and Bob have unbounded computational power, they can both compute the lexicographically first such embedding in advance of the protocol. When we consider computational lower bounds in Solar Lecture 5, we'll need an efficient construction.}
The point of properties (P1) and (P2) is to classify the points of $H$ into three categories: (i) those close to the image of a (unique) vertex of $K$; (ii) those not close to the image of any vertex but close to the image of a (unique) edge of $K$; and (iii) points not close to the image of any vertex or edge of $K$. Accordingly, each point $x \in H$ can be “decoded” to a unique vertex $v$ of $K$, a unique edge $(v,w)$ of $K$, or $\bot$. Don't forget that this classification of points of $H$ is made in advance of receiving any particular {\sc 2EoL}\xspace input. In the $\epsilon$-{\sc 2BFP}\xspace problem, because Alice and Bob both know the embedding in advance, they can decode points at will without any communication.\footnote{As suggested by Figure (ref), in the final construction it's important to use a more nuanced classification that “interpolates” between points in the three different categories. It will still be the case that Alice and Bob can classify any point $x \in H$ appropriately without any communication.}
Given the embedding above, we can now describe how to interpret a directed graph $G=(V,E)$ induced by an instance of {\sc EoL}\xspace as a continuous function on the hypercube, with approximate fixed points of the function corresponding only to sources and sinks of $G$. Write a function $f:H \rightarrow H$ as $f(x) = x + g(x)$ for the “displacement function” $g:H \rightarrow [-1,1]^d$. (The final construction will take care to define $g$ so that $x+g(x) \in H$ for every $x \in H$.) An $\epsilon$-approximate fixed point is a point $x$ with $ {\| {g(x)} \|} < \epsilon$, so it's crucial for our reduction that our definition of $g$ satisfies $ {\| {g(x)} \|} \ge \epsilon$ whenever $x$ is not close to the image of a source or sink of $G$.
Consider for simplicity a directed graph $G=(V,E)$ of an {\sc EoL}\xspace instance that has no 2-cycles and no isolated vertices.\footnote{Recall from Corollary (ref) that the {\sc 2EoL}\xspace problem is already hard in the special case where the encoded graph $G$ is guaranteed to be a Hamiltonian path.} For a (directed) edge $(u,v) \in E$, define \[ \gamma_{uv} = \frac{\sigma(v)-\sigma(u)}{ {\| {\sigma(v)-\sigma(u)} \|} } \] as the unit vector with the same direction as the embedding of the corresponding undirected edge of $K$, oriented from $u$ toward $v$. A rough description of the displacement function $g(x)$ corresponding to $G$ is as follows, where $\delta > 0$ is a parameter (cf., Figure (ref)):
For points $x$ “in between” the three cases (e.g., almost but not quite close enough to the image $\sigma(v)$ of a vertex $v \in V$), $g(x)$ is defined by interpolation (e.g., a weighted average of the displacement vector associated with $v$ in case 2 and $\delta$ times the default direction, with the weights determined by $x$'s proximity to $\sigma(v)$).
The default direction can be implemented by doubling the number of dimensions to $2d$, and defining the displacement direction as the vector $(0,0,\ldots,0,1,1,\ldots,1)$. Special handling (not detailed here) is then required at points $x$ with value close to 1 in one of these extra coordinates, to ensure that $x+g(x)$ remains in $H$ while also not introducing any unwanted approximate fixed points. Similarly, special handling is required for the source vertex $0^n$, to prevent $\sigma(0^n)$ from being a fixed point. Roughly, this can be implemented by mapping the vertex $0^n$ to one corner of the hypercube and defining $g$ to point in the opposite direction. The parameter $\delta$ is a constant, bigger than $\epsilon$ by a constant factor. ( For example, one can assume that $\epsilon \le 10^{-12}$ and take $\delta \approx 10^{-6}$.) This ensures that whenever the normalized $\ell_2$ norm of a direction vector $y$ is at least a sufficiently large constant, $\delta \cdot y$ has norm larger than $\epsilon$. This completes our sketch of how to interpret an instance of {\sc EoL}\xspace as a continuous function on the hypercube.
Properly implemented, the construction in Sections (ref) and (ref) has the following properties:
Sections (ref) and (ref), together with Figure (ref), provide a plausibility argument that a construction with these two properties is possible along the proposed lines. Readers interested in further details should start with the carefully written two-dimensional construction in HPV89---where many of these ideas originate---before proceeding to the general case in HPV89 for the $\ell_{\infty}$ norm and finally BR17 for the version tailored to the normalized $\ell_2$ norm (which is needed here).
We can now formally define the two-party version of the {\sc $\epsilon$-BFP}\xspace problem that we consider, denoted $\epsilon$-{\sc 2BFP}\xspace. The problem is parameterized by a positive integer $n$ and a constant $\epsilon > 0$.
The first property in Section (ref) implies a communication complexity lower bound for the $\epsilon$-{\sc 2BFP}\xspace problem, which implements step 3 of the road map in Section (ref). (The second property is important for implementing step 4 of the road map in the next section.)
There is one more important property of the functions $f$ constructed in Sections (ref) and (ref): they are {\em locally decodable} in a certain sense. Suppose Alice and Bob want to compute the value of $f(x)$ at some commonly known point $x \in H$. If $x$ decodes to $\bot$ (i.e., is not close to the image of any vertex or edge of the complete graph $K$ on vertex set $V$), then Alice and Bob know the value of $f(x)$ without any communication whatsoever: $f(x)$ is $x$ plus $\delta$ times the default direction (or a known customized displacement if $x$ is too close to certain boundaries of $H$). If $x$ decodes to the edge $e=(u,v)$ of the complete graph $K$, then Alice and Bob can compute $f(x)$ as soon as they know whether or not edge $e$ belongs to the directed graph $G$ induced by their inputs, along with its orientation. This requires Alice and Bob to exchange predecessor-successor information about only two vertices ($u$ and $v$). Analogously, if $x$ decodes to the vertex $v$ of $K$, then Alice and Bob can compute $f(x)$ after exchanging information about at most three vertices ($v$, $pred(v)$, and $succ(v)$).
This section completes the proof of Theorem (ref) by reducing the $\epsilon$-{\sc 2BFP}\xspace problem to the $\epsilon\text{-}\mathsf{NE}$ problem, where $\epsilon$ is a sufficiently small constant.
The starting point for our reduction is a purely analytic reduction of MT06, which reduces the existence of (exact) Brouwer fixed points to the existence of (exact) Nash equilibria.\footnote{This reduction was popularized in a Leisure of the Theory Class blog post by Eran Shmaya (https://theoryclass.wordpress.com/2012/01/05/brouwer-implies-nash-implies-brouwer/), who heard about the result from Rida Laraki.} Subsequent sections explain the additional ideas needed to implement this reduction for approximate fixed points and Nash equilibria in the two-party communication model.
An extension of the argument above shows that, for $\lambda$-Lipschitz functions $f$, an $\epsilon'$-approximate fixed point (in the normalized $\ell_2$ norm) can be extracted easily from any $\epsilon$-approximate Nash equilibrium, where $\epsilon'$ is a function of $\epsilon$ and $\lambda$ only.\footnote{It is not clear how to easily extract an approximate fixed point in the $\ell_{\infty}$ norm from an approximate Nash equilibrium without losing a super-constant factor in the parameters. The culprit is the “$\tfrac{1}{d}$” factor in (ref) and (ref)---needed to ensure that payoffs are bounded---which allows each player to behave in an arbitrarily crazy way in a few coordinates without violating the $\epsilon$-approximate Nash equilibrium conditions. (Recall $\epsilon > 0$ is constant while $d \rightarrow \infty$.) This is one of the primary reasons why R16 and BR17 needed to modify the construction in HPV89 to obtain their results.}
We now discuss how to translate the McLennan-Tourky analytic reduction to an analogous reduction in the two-party model. First, we need to discretize the hypercube. Define $H_{\epsilon}$ as the set of $\approx \left(\tfrac{1}{\epsilon}\right)^d$ points of $[0,1]^d$ for which all coordinates are multiples of $\epsilon$. Every $O(1)$-Lipschitz function $f$---including every function arising in a $\epsilon$-{\sc 2BFP}\xspace instance (Section (ref))---is guaranteed to have an $O(\epsilon)$-approximate fixed point at some point of this discretized hypercube (by rounding an exact fixed point to its nearest neighbor in $H_{\epsilon}$). This also means that the corresponding game (with payoffs defined as in (ref) and (ref)) has an $O(\epsilon)$-approximate Nash equilibrium in which each player deterministically chooses a point of $H_{\epsilon}$.
The obvious attempt at a two-party version of the McLennan-Tourky reduction is:
Just one problem: {\em this doesn't make sense}. The issue is that Bob needs to be able to compute $f(x)$ to evaluate his payoff function in (ref), and his $\epsilon$-{\sc 2BFP}\xspace input (a bunch of indices into Alice's blocks) does not provide sufficient information to do this. Thus, the proposed reduction does not produce a well-defined input to the $\epsilon\text{-}\mathsf{NE}$ problem.
The consolation prize is that Bob can compute the function $f$ at a point $x$ after a brief conversation with Alice. Recall from Section (ref) that computing $f$ at a point $x \in H$ requires information about at most three vertices of the {\sc 2EoL}\xspace input that underlies the $\epsilon$-{\sc 2BFP}\xspace input (in addition to $x$). Alice can send $x$ to Bob, who can then send the relevant indices to Alice (after decoding $x$ to some vertex or edge of $K$), and Alice can respond with the corresponding predecessor-successor pairs. This requires $O(\log N)$ bits of communication, where $N=2^n$ is the number of vertices in the underlying {\sc 2EoL}\xspace instance. (We are suppressing the dependence on the constant $\epsilon$ in the big-O notation.) Denote this communication protocol by $P$.
At this point, it's convenient to restrict the problem to the hard instances of {\sc 2EoL}\xspace used to prove Corollary (ref), where in particular, $succ(v) = w$ if and only if $v = pred(w)$. (I.e., cases (iii) and (iv) in the definition of the {\sc 2EoL}\xspace problem in Section (ref) never come up.) For this special case, $P$ can be implemented as a two-round protocol where Alice and Bob exchange information about one relevant vertex $v$ (if $x$ decodes to $v$) or two relevant vertices $u$ and $v$ (if $x$ decodes to the edge $(u,v)$).\footnote{If $x$ decodes to the edge $(u,v)$, then Alice and Bob exchange information about $u$ and $v$ in two rounds. If $x$ decodes to the vertex $v$, they exchange information about $v$ in two rounds. This reveals $v$'s opinion of its predecessor $u$ and successor $w$. In the general case, Alice and Bob would still need to exchange information about $u$ and $w$ using two more rounds of communication to confirm that $succ(u)=pred(w)=v$. (Recall our semantics: directed edge $(v,w)$ belongs to $G$ if and only if both $succ(v)=w$ and $pred(w)=v$.) In the special case of instances where $succ(v) = w$ if and only if $v = pred(w)$, these two extra rounds of communication are redundant.}
How can we exploit the local decodability of $\epsilon$-{\sc 2BFP}\xspace functions? The idea is to enlarge the strategy sets of Alice and Bob, beyond the discretized hypercube $H_{\epsilon}$, so that the players' strategies at equilibrium effectively simulate the protocol $P$. Alice's pure strategies are the pairs $(x,\alpha)$, where $x \in H_{\epsilon}$ is a point of the discretized hypercube and $\alpha$ is a possible transcript of Alice's communication in the protocol $P$. Thus $\alpha$ consists of at most two predecessor-successor pairs. Bob's pure strategies are the pairs $(z,\beta)$, where $z \in H_{\epsilon}$ and $\beta$ is a transcript that could be generated by Bob in $P$---a specification of at most two different vertices and his corresponding indices for them.\footnote{In the protocol $P$, Bob does not need to communicate the names of any vertices---Alice can decode $x$ privately. But it's convenient for the reduction to include the names of the vertices relevant for $x$ in the $\beta$ component of Bob's strategy.} Crucially, because the protocol $P$ has cost $O(\log N)$, there are only $N^{O(1)}$ possible $\alpha$'s and $\beta$'s. There are also only $N^{O(1)}$ possible choices of $x$ and $z$---since $\epsilon$ is a constant and $d=\Theta(n)$ in the $\epsilon$-{\sc 2BFP}\xspace problem, $|H_{\epsilon}|\approx \left(\tfrac{1}{\epsilon}\right)^d$ is polynomial in $N=2^n$. We conclude that the size of the resulting game is polynomial in the length of the given $\epsilon$-{\sc 2BFP}\xspace (or {\sc 2EoL}\xspace) inputs.
We still need to define the payoffs of the game. Let $A_1,\ldots,A_N$ and $y_1,\ldots,y_N$ denote Alice's and Bob's private inputs in the given $\epsilon$-{\sc 2BFP}\xspace (equivalently, {\sc 2EoL}\xspace) instance and $f$ the corresponding function. Call an outcome $(x,\alpha,z,\beta)$ consistent if $\alpha$ and $\beta$ are the transcripts generated by Alice and Bob when they honestly follow the protocol $P$ to compute $f(x)$. Precisely, a consistent outcome is one that meets the following two conditions:
Observe that Alice can privately check if condition (i) holds (using her private input $A_1,\ldots,A_N$ and the vertex names and indices in Bob's announced strategy $\beta$), and Bob can privately check condition (ii) (using his private input $y_1,\ldots,y_N$ and the point $x$ announced by Alice).
For an outcome $(x,\alpha,z,\beta)$, we define Alice's payoffs by
(Compare (ref) with (ref).) This definition makes sense because Alice can privately check whether or not (i) holds and hence can privately compute her payoff.\footnote{If you want to be a stickler and insist on payoffs in $[0,1]$, then shift and scale the payoffs in (ref) appropriately.}
For Bob's payoffs, we need a preliminary definition. Let $f_{\alpha}(x)$ denote the value that the induced function $f$ would take on if $\alpha$ was consistent with $x$ and with Alice's and Bob's private inputs. That is, to compute $f_{\alpha}(x)$:
To review, $f$ is the $\epsilon$-{\sc 2BFP}\xspace function that Alice and Bob want to find a fixed point of, and $f(x)$ generally depends on the private inputs $A_1,\ldots,A_N$ and $y_1,\ldots,y_N$ of both Alice and Bob. The function $f_{\alpha}$ is a speculative version of $f$, predicated on Alice's announced predecessor-successor pairs in her strategy $\alpha$. Crucially, the definition of $f_{\alpha}$ does not depend at all on Alice's private input, only on Alice's {\em announced strategy}. Thus given $\alpha$, Bob can privately execute the three steps above and evaluate $f_{\alpha}(x)$ for any $x \in H_{\epsilon}$. The other crucial property of $f_{\alpha}$ is that, if $\alpha$ happens to be the actual predecessor-successor pairs $\{ A_v[y_v] \}$ for the vertices relevant for $x$ (given Alice's and Bob's private inputs), then $f_{\alpha}(x)$ agrees with the value $f(x)$ of the true $\epsilon$-{\sc 2BFP}\xspace function.
We can now define Bob's payoffs as follows (compare with (ref)):
Because Bob can privately check condition (ii) and compute $f_{\alpha}(x)$ (given $x$ and $\alpha$), Bob can privately compute his payoff. This completes the description of the reduction from the $\epsilon$-{\sc 2BFP}\xspace problem to the $\epsilon\text{-}\mathsf{NE}$ problem.
Alice and Bob can carry out this reduction with no communication---by construction, their $\epsilon$-{\sc 2BFP}\xspace inputs fully determine their payoff matrices. As noted earlier, because $\epsilon$ is a constant, the sizes of the produced $\epsilon\text{-}\mathsf{NE}$ inputs are polynomial in those of the $\epsilon$-{\sc 2BFP}\xspace inputs.
Finally, we need to show that the reduction “works,” meaning that Alice and Bob can recover an approximate fixed point of the $\epsilon$-{\sc 2BFP}\xspace function $f$ from any approximate Nash equilibrium of the game produced by the reduction.
For intuition, let's think first about the case where Alice's and Bob's strategies are points of the hypercube $H$ (rather than the discretized hypercube $H_{\epsilon}$) and the case of exact fixed points and Nash equilibria. (Cf., Theorem (ref).) What could a Nash equilibrium of the game look like? Consider mixed strategies by Alice and Bob.
These four steps imply that every (exact) Nash equilibrium $(x,\alpha,z,\beta)$ of the game is pure, with $\alpha$ and $\beta$ consistent with $x$ and Alice's and Bob's private information about the corresponding relevant vertices, and with $x=z=f_{\alpha}(x) = f(x)$ a fixed point of $f$.
As with Theorem (ref), a more technical version of the same argument implies that an approximate fixed point---a point $x$ satisfying $ {\| {f(x)-x} \|} < \epsilon'$ with respect to the normalized $\ell_2$ norm---can be easily extracted by Alice and Bob from any $\epsilon$-approximate Nash equilibrium, where $\epsilon'$ depends only on $\epsilon$ (e.g., $\epsilon' = O(\epsilon^{1/4})$ suffices). For example, the first step of the proof becomes: in an $\epsilon$-approximate Nash equilibrium, Alice must choose a point $x \in H_{\epsilon}$ that is close to $\mathbf{E}\ifthenelse{\not\equal{}{}}{_{}}{}\!\left[z\right]$ except with small probability (otherwise she could increase her expected payoff by more than $\epsilon$ by switching to the point of $H_{\epsilon}$ closest to $\mathbf{E}\ifthenelse{\not\equal{}{}}{_{}}{}\!\left[z\right]$). And so on. Carrying out approximate versions of all four steps above, while keeping careful track of the epsilons, completes the proof of Theorem (ref).\footnote{The fact that $f$ is $O(1)$-Lipschitz is important for carrying out the last of these steps.}
We conclude that computing an approximate Nash equilibrium of a general bimatrix game requires a polynomial amount of communication, and in particular there are no uncoupled dynamics guaranteed to converge to such an equilibrium in a polylogarithmic number of iterations.
\chapter{$\mathsf{TFNP}$, $\mathsf{PPAD}$, & All That} \titlerule
Having resolved the communication complexity of computing an approximate Nash equilibrium of a bimatrix game, we turn our attention to the {\em computational} complexity of the problem. Here, the goal will be to prove a super-polynomial lower bound on the amount of computation required, under appropriate complexity assumptions. The techniques developed in the last two lectures for our communication complexity lower bound will again prove useful for this goal, but we will also need several additional ideas.
This lecture identifies the appropriate complexity class for characterizing the computational complexity of computing an exact or approximate Nash equilibrium of a bimatrix game, namely $\mathsf{PPAD}$. Solar Lecture 5 sketches some of the ideas in Rubinstein's recent proof R16 of a quasi-polynomial-time lower bound for the problem, assuming an analog of the Exponential Time Hypothesis for $\mathsf{PPAD}$.
Section (ref) explains why customized complexity classes are needed to reason about equilibrium computation and other total search problems. Section (ref) defines the class $\mathsf{TFNP}$ and some of its syntactic subclasses, including $\mathsf{PPAD}$.\footnote{Some of the discussion in these two sections is drawn from f13.} Section (ref) reviews a number of $\mathsf{PPAD}$-complete problems. Section (ref) discusses the existing evidence that $\mathsf{TFNP}$ and its important subclasses are hard, and proves that the class $\mathsf{TFNP}$ is hard on average assuming that $\mathsf{NP}$ is hard on average.
We consider two-player (bimatrix) games, where each player has (at most) $n$ strategies. The $n \times n$ payoff matrices for Alice and Bob $A$ and $B$ are described explicitly, with $A_{ij}$ and $B_{ij}$ indicating Alice's and Bob's payoffs when Alice plays her $i$th strategy and Bob his $j$th strategy. Recall from Definition (ref) that an $\epsilon$-$\mathsf{NE}$ is a pair $\hat{x},\hat{y}$ of mixed strategies such that neither player can increase their payoff with a unilateral deviation by more than $\epsilon$.
What do we know about the complexity of computing an $\epsilon$-$\mathsf{NE}$ of a bimatrix game? Let's start with the exact case ($\epsilon=0$), where no subexponential-time (let alone polynomial-time) algorithm is known for the problem. (This contrasts with the zero-sum case, see Corollary (ref).) It is tempting to speculate that no such algorithm exists. How would we amass evidence that the problem is intractable? As we're interested in super-polynomial lower bounds, communication complexity is of no direct help.
Could the problem be $\mathsf{NP}$-complete?\footnote{Technically, we're referring to the {\em search} version of $\mathsf{NP}$ (sometimes called $\mathsf{FNP}$, where the “F” stands for “functional”), where the goal is to either exhibit a witness or correctly deduce that no witness exists.} The following theorem by MP91 rules out this possibility (unless $\mathsf{NP} = \mathsf{co}\mbox{-}\mathsf{NP}$).
What's really going on in the proof of Theorem (ref) is a mismatch between the search version of an $\mathsf{NP}$-complete problem like SAT, where an instance may or may not have a witness, and a problem like computing a Nash equilibrium, where every instance has at least one witness. While the correct answer to a SAT instance might well be “no,” a correct answer to an instance of Nash equilibrium computation is always a Nash equilibrium. It seems that if the problem of computing a Nash equilibrium is going to be complete for some complexity class, it must be a class smaller than $\mathsf{NP}$.
The subset of $\mathsf{NP}$ (search) problems for which every instance has at least one witness is called $\mathsf{TFNP}$, for “total functional $\mathsf{NP}$.” The proof of Theorem (ref) shows more generally that if {\em any} $\mathsf{TFNP}$ problem is $\mathsf{NP}$-complete, then $\mathsf{NP} = \mathsf{co}\mbox{-}\mathsf{NP}$. Thus a fundamental barrier to $\mathsf{NP}$-completeness is the guaranteed existence of a witness.
Since computing a Nash equilibrium does not seem to be $\mathsf{NP}$-complete, the sensible refined goal is to prove that the problem is $\mathsf{TFNP}$-complete---as hard as any other $\mathsf{NP}$ problem with a guaranteed witness.
Unfortunately, $\mathsf{TFNP}$-completeness is also too ambitious a goal. The reason is that $\mathsf{TFNP}$ does not seem to have complete problems. Think about the complexity classes that {\em are} known to have complete problems---$\mathsf{NP}$ of course, and also classes like $\mathsf{P}$ and $\mathsf{PSPACE}$. What do these complexity classes have in common? They are “syntactic,” meaning that membership can be characterized via acceptance by some concrete computational model, such as polynomial-time or polynomial-space deterministic or nondeterministic Turing machines. In this sense, there is a generic reason for membership in these complexity classes.
Syntactically defined complexity classes always have a “generic” complete problem, where the input is a description of a problem in terms of the accepting machine and an instance of the problem, and the goal is to solve the given instance of the given problem. For example, the generic $\mathsf{NP}$-complete problem takes as input a description of a verifier, a polynomial time bound, and an encoding of an instance, and the goal is to decide whether or not there is a witness, meaning a string that causes the given verifier to accept the given instance in at most the given number of steps.
$\mathsf{TFNP}$ has no obvious generic reason for membership, and as such is called a “semantic” class.\footnote{There are many other interesting examples of classes that appear to be semantic in this sense, such as $\mathsf{RP}$ and $\mathsf{NP} \cap \mathsf{co}\mbox{-}\mathsf{NP}$.} For example, the problem of computing a Nash equilibrium of a bimatrix game belongs to $\mathsf{TFNP}$ because of the topological arguments that guarantee the existence of a Nash equilibrium (see Section (ref)). Another problem in $\mathsf{TFNP}$ is factoring: given a positive integer, output its factorization. Here, membership in $\mathsf{TFNP}$ has a number-theoretic explanation.\footnote{There are many other natural examples of $\mathsf{TFNP}$ problems, including computing a local minimum of a function, computing an approximate Brouwer fixed point, and inverting a one-way permutation.} Can the guaranteed existence of a Nash equilibrium of a game and of a factorization of an integer be regarded as separate instantiations of some “generic” $\mathsf{TFNP}$ argument? No one knows the answer.
Given that the problem of computing a Nash equilibrium appears too specific to be complete for $\mathsf{TFNP}$, we must refine our goal again, and try to prove that the problem is complete for a still smaller complexity class. P94 initiated the search for syntactic subclasses of $\mathsf{TFNP}$ that contain interesting problems not known to belong to $\mathsf{P}$. His proposal was to categorize $\mathsf{TFNP}$ problems according to the type of mathematical proof used to guaranteed the existence of a witness. Interesting subclasses include the following:
All of these complexity classes can be viewed as intermediate to $\mathsf{P}$ and $\mathsf{NP}$. The conjecture, supported by oracle separations B+98, is that all four of these classes are distinct (Figure (ref)).
Section (ref) outlined the argument that the guaranteed existence of Nash equilibria reduces to the guaranteed existence of Brouwer fixed points, and Section (ref) showed (via Sperner's lemma) that Brouwer's fixed-point theorem reduces to path-following in a directed graph with in- and out-degrees at most 1. Thus, $\mathsf{PPAD}$ would seem to be the subclass of $\mathsf{TFNP}$ with the best chance of capturing the complexity of computing a Nash equilibrium.
We can formally define the class $\mathsf{PPAD}$ by defining its generic problem. (A problem is then in $\mathsf{PPAD}$ if it reduces in polynomial time to the generic problem.) Just as the {\sc End-of-the-Line ({\sc EoL}\xspace)} problem served as the starting point of our communication complexity lower bound (see Section (ref)), a succinct version of the problem will be the basis for our computational hardness results.
Analogous to Section (ref), we can view the circuits $S$ and $P$ as defining a graph $G$ with in- and out-degrees at most 1 (with edge $(v,w)$ in $G$ if and only if $S(v) = w$ and $P(w) = v$), and with a given source vertex $0^n$. The {\sc EoL}\xspace problem then corresponds to identifying either a sink vertex of $G$ or a source vertex other than $0^n$.\footnote{The undirected version of the problem can be used to define the class $\mathsf{PPA}$. The version of the problem where only sink vertices count as witnesses seems to give rise to a different (larger) complexity class called $\mathsf{PPADS}$.} A solution is guaranteed to exist---if nothing else, the other end of the path of $G$ that originates with the vertex $0^n$. Thus {\sc EoL}\xspace does indeed belong to $\mathsf{TFNP}$, and $\mathsf{PPAD} \subseteq \mathsf{TFNP}$. Note also that the class is syntactic and by definition has a complete problem, namely the {\sc EoL}\xspace problem.
The class $\mathsf{PPAD}$ contains several natural problems (in addition to the {\sc EoL}\xspace problem). For example, it contains a computational version of Sperner's lemma---given a succinct description (e.g., polynomial-size circuits) of a legal coloring of an exponentially large triangulation of a simplex, find a sub-simplex such that its vertices showcase all possible colors. This problem can be regarded as a special case of the {\sc EoL}\xspace problem (see Section (ref)), and hence belongs to $\mathsf{PPAD}$.
Another example is the problem of computing an approximate fixed point. Here the input is a succinct description of a $\lambda$-Lipschitz function $f$ (on the hypercube in $d$ dimensions, say) and a parameter $\epsilon$, and the goal is to compute a point $x$ with $ {\| {f(x)-x} \|} < \epsilon$ (with respect to some norm). The description length of $x$ should be polynomial in that of the function $f$. Such a point is guaranteed to exist provided $\epsilon$ is not too small relative to $\lambda$. \footnote{For example, for the $\ell_{\infty}$ norm, existence of such a point is guaranteed with $\epsilon$ as small as $\tfrac{(\lambda+1)}{2^n}$, where $n$ is the description length of $f$. This follows from rounding each coordinate of an exact fixed point to its nearest multiple of $2^{-n}$.} The reduction from Brouwer's fixed-point theorem to Sperner's lemma (with colors corresponding to directions of movement, see Section (ref)) shows that computing an approximate fixed point can also be regarded as a special case of the {\sc EoL}\xspace problem, and hence belongs to $\mathsf{PPAD}$.
The problem of computing an exact or approximate Nash equilibrium of a bimatrix game also belongs to $\mathsf{PPAD}$. For the problem of computing an $\epsilon$-approximate Nash equilibrium (with $\epsilon$ no smaller than inverse exponential in $n$), this follows from the proof of Nash's theorem outlined in Section (ref). That proof shows that computing an $\epsilon\text{-}\mathsf{NE}$ is a special case of computing an approximate fixed point (of the regularized best-response function defined in (ref) and (ref)), and hence the problem belongs to $\mathsf{PPAD}$. The same argument shows that this is true more generally with any finite number of players (i.e., not only for bimatrix games).
The problem of computing an exact Nash equilibrium ($\epsilon=0$) also belongs to $\mathsf{PPAD}$ in the case of two-player (bimatrix) games.\footnote{EY07 proved that, with 3 or more players, the problem of computing an exact Nash equilibrium of a game appears to be strictly harder than any problem in $\mathsf{PPAD}$.} One way to prove this is via the Lemke-Howson algorithm LH64 (see also Section (ref)), which reduces the computation of an (exact) Nash equilibrium of a bimatrix game to a path-following problem, much in the way that the simplex method reduces computing an optimal solution of a linear program to following a path of improving edges along the boundary of the feasible region. The proof of the Lemke-Howson algorithm's inevitable convergence uses parity arguments akin to the one in the proof of Sperner's lemma, and shows that the problem of computing a Nash equilibrium of a bimatrix game belongs to $\mathsf{PPAD}$.
The {\sc EoL}\xspace problem is $\mathsf{PPAD}$-complete by construction. What about “more natural” problems? Papadimitriou P94 built evidence that $\mathsf{PPAD}$ is a fundamental complexity class by showing that fixed-point problems are complete for it.
To be precise, let {\sc Brouwer}$( {\| {\cdot} \|} , d, \mathcal{F}, \epsilon)$ denote the following problem: given a (succinct description of a) function $f \in \mathcal{F}$, with $f:[0,1]^d \rightarrow [0,1]^d$, compute a point $x \in [0,1]^d$ such that $ {\| {f(x)-x} \|} < \epsilon$. The original hardness result from P94 is the following.
The high-level idea of the proof is similar to the construction in Section (ref) that shows how to interpret {\sc EoL}\xspace instances as implicitly defined Lipschitz functions on the hypercube. Given descriptions of the circuits $S$ and $P$ in an instance of the generic {\sc EoL}\xspace problem, it is possible to define an (efficiently computable) function whose gradient “follows the line” of an embedding of the induced directed graph into the hypercube. Three dimensions are needed in the construction in P94 to ensure that the images of different edges do not intersect (except at a shared endpoint). Some time later, CD09 used a somewhat different approach to prove that Theorem (ref) holds even when $d=2$.\footnote{The one-dimensional case can be solved in polynomial time, essentially by binary search.}
Much more recently, with an eye toward hardness results for $\epsilon$-approximate Nash equilibria with constant $\epsilon$ (see Solar Lecture 5), R16 proved the following.\footnote{Theorem (ref) proves hardness in the regime where $d$ and $\epsilon$ are both small, Theorem (ref) when both are large. This is not an accident; if $d$ is small (i.e., constant) and $\epsilon$ is large (i.e., constant), the problem can be solved in polynomial time by exhaustively checking a constant number of evenly spaced grid points.}
The proof of Theorem (ref) is closely related to the third step of our communication complexity lower bound (Section (ref)), and in particular makes use of a similar embedding of graphs into the hypercube with the properties (P1) and (P2) described in Section (ref). \footnote{We have reversed the chronology; Theorem (ref) was proved after Theorem (ref) and used the construction in R16 more or less as a black box.} One major difference is that our proof of existence of the embedding in Section (ref) used the probabilistic method and hence is not constructive (which is not an issue in the two-party communication model), while the computational lower bound in Theorem (ref) requires an efficiently computable embedding. In particular, the reduction from {\sc EoL}\xspace to {\sc Brouwer}$( {\| {\cdot} \|} , d, \mathcal{F}, \epsilon)$ must efficiently produce a succinct description of the function $f$ induced by an instance of {\sc EoL}\xspace, and it should be possible to efficiently evaluate $f$, presumably while using the given {\sc EoL}\xspace circuits $S$ and $P$ only as black boxes. For example, it should be possible to efficiently decode points of the hypercube (to a vertex, edge, or $\bot$, see Section (ref)).
Conceptually, the fixes for these problems are relatively simple. First, rather than mapping the vertices randomly into the hypercube, the reduction in the proof of Theorem (ref) embeds the vertices using an error-correcting code (with constant rate and efficient encoding and decoding algorithms). This enforces property (P1) of Section (ref). Second, rather than using a straight-line embedding, the reduction is more proactive about making the images of different edges stay far apart (except for at shared endpoints). Specifically, an edge of the directed graph induced by the given {\sc EoL}\xspace instance is now mapped to 4 straight line segments, and along each line segment, two-thirds of the coordinates stay fixed. (This requires blowing up the number of dimensions by a constant factor.) For example, the directed edge $(u,v)$ can be mapped to the path \[ (\sigma(u),\sigma(u),\mathbf{\tfrac{1}{4}}) \mapsto (\sigma(u),\sigma(v),\mathbf{\tfrac{1}{4}}) \mapsto (\sigma(u),\sigma(v),\mathbf{\tfrac{3}{4}}) \mapsto (\sigma(v),\sigma(v),\mathbf{\tfrac{3}{4}}) \mapsto (\sigma(v),\sigma(v),\mathbf{\tfrac{1}{4}}), \] where $\sigma$ denotes the error-correcting code used to map the vertices to the hypercube and the boldface $\mathbf{\tfrac{1}{4}}$ and $\mathbf{\tfrac{3}{4}}$ indicate the value of the last third of the coordinates. This maneuver enforces property (P2) of Section (ref). It also ensures that it is easy to decode points of the hypercube that are close to the image of an edge of the graph---at least one of the edge's endpoints can be recovered from the values of the frozen coordinates, and the other endpoint can be recovered using the given predecessor and successor circuits.\footnote{This embedding is defined only for the directed edges that are present in the given {\sc EoL}\xspace instance, rather than for all possible edges (in contrast to the embedding in Sections (ref) and (ref)).}
P94 defined the class $\mathsf{PPAD}$ in large part to capture the complexity of computing a Nash equilibrium, conjecturing that the problem is in fact $\mathsf{PPAD}$-complete. Over a decade later, a flurry of papers confirmed this conjecture. First, Daskalakis, Goldberg, and Papadimitriou DGP06,GP06 proved that computing an $\epsilon\text{-}\mathsf{NE}$ of a four-player game, with $\epsilon$ inverse exponential in the size of the game, is $\mathsf{PPAD}$-complete. This approach was quickly refined CD05,DP05, culminating in the proof of Chen and Deng CD06 that computing a Nash equilibrium (or even an $\epsilon\text{-}\mathsf{NE}$ with exponentially small $\epsilon$) of a bimatrix game is $\mathsf{PPAD}$-complete. Thus the nice properties possessed by Nash equilibria of bimatrix games (see Section (ref)) are not enough to elude computational intractability. CDT06 strengthened this result to hold even for values of $\epsilon$ that are only inverse polynomial in the size of the game.\footnote{In particular, under standard complexity assumptions, this rules out an algorithm for computing an exact Nash equilibrium of a bimatrix game that has smoothed polynomial complexity in the sense of ST04. Thus the parallels between the simplex method and the Lemke-Howson algorithm (see Section (ref)) only go so far.} The papers by DGP09 and CDT09 give a full account of this breakthrough sequence of results.
The proof of Theorem (ref), which is a tour de force, is also outlined in the surveys by J07, P07, DGPcacm, and et. Fundamentally, the proof shows how to define a bimatrix game so that every Nash equilibrium effectively performs a gate-by-gate simulation of the circuits of a given {\sc EoL}\xspace instance.
Theorem (ref) left open the possibility that, for every constant $\epsilon > 0$, an $\epsilon\text{-}\mathsf{NE}$ of a bimatrix game can be computed in polynomial time. (Recall from Corollary (ref) that one can be computed in {\em quasi-polynomial} time.) A decade later, R16 ruled out this possibility (under suitable complexity assumptions) by proving a quasi-polynomial-time hardness result for the problem when $\epsilon$ is a sufficiently small constant. We will have much more to say about this result in Solar Lecture 5.
It's all fine and good to prove that a problem is as hard as any other problem in $\mathsf{PPAD}$, but what makes us so sure that $\mathsf{PPAD}$ problems (or even $\mathsf{TFNP}$ problems) can be computationally difficult?
The first evidence of hardness of problems in $\mathsf{TFNP}$ came in the form of exponential lower bounds for functions given as “black boxes,” or equivalently query complexity lower bounds, as in Proposition (ref) for the {\sc EoL}\xspace problem or HPV89 for the {\sc Brouwer} problem.
Can we relate the hardness of $\mathsf{TFNP}$ and its subclasses to other standard complexity assumptions? Theorem (ref) implies that we can't base hardness of $\mathsf{TFNP}$ on the assumption that $\mathsf{P} \neq \mathsf{NP}$, unless $\mathsf{NP} = \mathsf{co}\mbox{-}\mathsf{NP}$. What about cryptographic assumptions? After all, the problem of inverting a one-way permutation belongs to $\mathsf{TFNP}$ (and even the subclass $\mathsf{PPP}$). Thus, sufficiently strong cryptographic assumptions imply hardness of $\mathsf{TFNP}$.
Can we prove hardness also for all of the other interesting subclasses of $\mathsf{TFNP}$, or can we establish the hardness of $\mathsf{TFNP}$ under weaker assumptions (like the existence of one-way functions)? Along the former lines, a recent sequence of papers (not discussed here) show that sufficiently strong cryptographic assumptions imply that $\mathsf{PPAD}$ is hard BPR15,GPS16,RSS17,HY17,C+19. The rest of this lecture covers a recent result in the second direction by HNY17, who show that the average-case hardness of $\mathsf{TFNP}$ can be based on the average-case hardness of $\mathsf{NP}$. (Even though the worst-case hardness of $\mathsf{TFNP}$ {\em cannot} be based on that of $\mathsf{NP}$, unless $\mathsf{NP}=\mathsf{co}\mbox{-}\mathsf{NP}$!) Note that assuming that $\mathsf{NP}$ is hard on average is only weaker than assuming the existence of one-way functions.
There is some fine print in the precise statement of the result (see Remarks (ref) and (ref)), but the statement in Theorem (ref) is the gist of it.\footnote{The amount of fine print was reduced very recently by PV19.}
Let $L$ be a language in $\mathsf{NP}$ that is hard on average w.r.t.\ some family of distributions $D_n$ on input strings of length $n$. Average-case hardness of $(L, D_n)$ means that there is no polynomial-time algorithm with an advantage of $1/\mathrm{poly}(n)$ over random guessing when the input is sampled according to $D_n$ (for any polynomial). Each $D_n$ should be efficiently sampleable, so that hardness cannot be baked into the input distribution. Can we convert such a problem into one that is total while retaining its average-case hardness?
Here's an initial attempt:
For sufficiently large $l$, this problem is “almost total.” Because $(L,D_n)$ is hard-on-average, random instances are nearly equally likely to be “yes” or “no” instances (otherwise a constant response would beat random guessing). Thus, except with probability $\approx 2^{-l}$, at least one of the sampled instances $x_i$ is a “yes” instance and has a witness. Taking $l$ polynomial in $n$, we get a problem that is total except with exponentially small probability. How can we make it “totally total?”
The idea is to sample the $x_i$'s in a correlated way, using a random shifting trick reminiscent of Lautemann's proof that $\mathsf{BPP} \subseteq \Sigma_2 \cap \Pi_2$ L83. This will give a non-uniform version of Theorem (ref); Remark (ref) sketches the changes necessary to get a uniform version.
Fix $n$. Let $D_n(r)$ denote the output of the sampling algorithm for $D_n$, given the random seed $r \in \{0,1\}^n$. (By padding, we can assume that the input length and the random seed length both equal $n$.) Call a set containing the strings $s_1, s_2, \ldots, s_l \in \{0,1\}^n$ {\em good} if for every seed $r\in \{0,1\}^n$ there exists an index $i\in [l]$ such that $D(r\oplus s_i) \in L$. We can think of the $s_i$'s as masks; goodness then means that there is always a mask whose application yields a “yes” instance.
Consider now the following reduction, from the assumed hard-on-average $\mathsf{NP}$ problem $(L,D_n)$ to a hopefully hard-on-average $\mathsf{TFNP}$ problem.
By the definition of a good set of strings, there is always at least one witness of the desired form, and so the output of this reduction is a $\mathsf{TFNP}$ problem (or more accurately, a $\mathsf{TFNP}/\mathrm{poly}$ problem, with $s_1,\ldots,s_{2n}$ given as advice). Let $D'$ denote the distribution over instances of this problem induced by the uniform distribution over $\hat{r}$. It remains to show how a (non-uniform) algorithm that solves this $\mathsf{TFNP}/\mathrm{poly}$ problem (with respect to $D'$) can be used to beat random guessing (with inverse polynomial advantage) for $(L,D_n)$ in a comparable amount of time. Given an algorithm $A$ for the former problem (and the corresponding good set of strings), consider the following algorithm $B$ for $(L,D_n)$.
Consider a “yes” instance $D_n(\hat{r})$ of $L$. If algorithm $A$ happens to output a witness to the $i$th instance $D_n(r^\star\oplus s_i) = D_n(\hat{r})$, then algorithm $B$ correctly decides the problem. The worry is that the algorithm $A$ somehow conspires to always output a witness for an instance other than the “real” one.
Suppose algorithm $A$, when presented with the instances $D(r^\star\oplus s_1), D(r^\star\oplus s_2), \ldots, D(r^\star\oplus s_{2n})$, exhibits a witness for the $j$th instance $D(r^\star\oplus s_j)$. This collection of instances could have been produced by the reduction in exactly $2n$ different ways: with $i=1$ and $\hat{r}=r^{\star} \oplus s_1$, with $i=2$ and $\hat{r}=r^{\star} \oplus s_2$, and so on. Since $i$ and $\hat{r}$ were chosen independently and uniformly at random, each of these $2n$ outcomes is equally likely, and algorithm $A$ has no way of distinguishing between them. Thus whatever $j$ is, $A$'s witness has at least a $1/2n$ chance of being a witness for the true problem $D_n(\hat{r})$ (where the probability is over both $\hat{r}$ and $i$). We conclude that, for “yes” instances of $L$, algorithm $B$ has advantage $\tfrac{1}{2n}$ over random guessing. Since roughly 50% of the instances $D_n(\hat{r})$ are “yes” instances (since $(L,D_n)$ is average-case hard), algorithm $B$ has advantage roughly $\tfrac{1}{4n}$ over random guessing for $(L,D_n)$. This contradicts our assumption that $(L,D_n)$ is hard on average.
We have completed the proof of Theorem (ref), modulo two caveats.
An important open research direction is to extend Theorem (ref) to subclasses of $\mathsf{TFNP}$, such as $\mathsf{PPAD}$.
{\bf Open Problem:} Does an analogous average-case hardness result hold for $\mathsf{PPAD}$?
\chapter{The Computational Complexity of Computing an Approximate Nash Equilibrium} \titlerule
Last lecture we stated without proof the result by DGP09 and CDT09 that computing an $\epsilon$-approximate Nash equilibrium of a bimatrix game is $\mathsf{PPAD}$-complete, even when $\epsilon$ is an inverse polynomial function of the game size (Theorem (ref)). Thus, it would be surprising if there were a polynomial-time (or even subexponential-time) algorithm for this problem. Recall from Corollary (ref) in Solar Lecture 1 that the story is different for constant values of $\epsilon$, where an $\epsilon$-approximate Nash equilibrium can be computed in quasi-polynomial (i.e., $n^{O(\log n)}$) time.
The Pavlovian response of a theoretical computer scientist to a quasi-polynomial-time algorithm is to conjecture that a polynomial-time algorithm must also exist. (There are only a few known natural problems that appear to have inherently quasi-polynomial time complexity.) But recall that the algorithm in the proof of Corollary (ref) is just exhaustive search over all probability distributions that are uniform over a multi-set of logarithmically many strategies (which is good enough, by Theorem (ref)). Thus the algorithm reveals no structure of the problem other than the fact that the natural search space for it has quasi-polynomial size. It is easy to imagine that there are no “shortcuts” to searching this space, in which case a quasi-polynomial amount of time would indeed be necessary. How would we ever prove such a result? Presumably by a non-standard super-polynomial reduction from some $\mathsf{PPAD}$-complete problem like succinct {\sc EoL}\xspace (defined in Section (ref)). This might seem hard to come by, but in a recent breakthrough, R16 provided just such a reduction!
In other words, assuming an analog of the Exponential Time Hypothesis (ETH) IPZ01 for $\mathsf{PPAD}$, the quasi-polynomial-time algorithm in Corollary (ref) is essentially optimal!\footnote{To obtain a quantitative lower bound like the conclusion of Theorem (ref), it is necessary to make a quantitative complexity assumption (like an analog of ETH). This approach belongs to the tradition of “fine-grained” complexity theory.}\footnote{How plausible is the assumption that the ETH holds for $\mathsf{PPAD}$, even after assuming that the ETH holds for $\mathsf{NP}$ and that $\mathsf{PPAD}$ has no polynomial-time algorithms? The answer is far from clear, although there are exponential query lower bounds for $\mathsf{PPAD}$ problems (e.g. HPV89) and no known techniques that show promise for a subexponential-time algorithm for the succinct {\sc EoL}\xspace problem.}
Three previous papers that used an ETH assumption (for $\mathsf{NP}$) along with PCP machinery to prove quasi-polynomial-time lower bounds for $\mathsf{NP}$ problems are:
In all three cases, the hardness results apply when $\epsilon > 0$ is a sufficiently small constant. Quasi-polynomial-time algorithms are known for all three problems.
The main goal of this lecture is to convey some of the ideas in the proof of Theorem (ref). The proof is a tour de force and the paper R16 is 57 pages long, so our treatment will necessarily be impressionistic. We hope to explain the following:
The goal is to reduce length-$n$ instances of the succinct {\sc EoL}\xspace problem to length-$f(n)$ instances of the problem of computing an $\epsilon$-approximate Nash equilibrium with constant $\epsilon$, so that a sub-quasi-polynomial-time algorithm for the latter implies a subexponential-time algorithm for the former. Thus the mapping $n \mapsto f(n)$ should satisfy $2^n \approx f(n)^{\log f(n)}$ and hence $f(n) \approx 2^{\sqrt{n}}$. That is, we should be looking to encode a length-$n$ instance of succinct {\sc EoL}\xspace as a $2^{\sqrt{n}} \times 2^{\sqrt{n}}$ bimatrix game. The $\sqrt{n}$ will essentially come from the “birthday paradox,” with random subsets of $[n]$ of size $s$ likely to intersect once $s$ exceeds $\sqrt{n}$. The blow-up from $n$ to $2^{\sqrt{n}}$ will come from PCP-like machinery, as well as a game-theoretic gadget (“Alth\"ofer games,” see Section (ref)) that forces players to randomize nearly uniformly over size-$\sqrt{n}$ subsets of $[n]$ in every approximate Nash equilibrium.
The starting point of the reduction is the $\mathsf{PPAD}$-complete version of the {\sc $\epsilon$-BFP}\xspace problem in Theorem (ref). We restate that result here.
The proof is closely related to the reduction from {\sc 2EoL}\xspace to $\epsilon$-{\sc 2BFP}\xspace outlined in Section (ref), and Section (ref) describes the additional ideas needed to prove Theorem (ref). As long as the error-correcting code used to embed vertices into the hypercube (see Section (ref)) has linear-time encoding and decoding algorithms (as in S97, for example), the reduction can be implemented in linear time. In particular, our assumption that the succinct {\sc EoL}\xspace problem has no subexponential-time algorithms automatically carries over to this version of the {\sc $\epsilon$-BFP}\xspace problem. In addition to the properties of the functions in $\mathcal{F}$ that are listed in the statement of Theorem (ref), the proof of Theorem (ref) crucially uses the “locally decodable” properties of these functions (see Section (ref)).
One natural starting point for a reduction from {\sc $\epsilon$-BFP}\xspace to $\epsilon\text{-}\mathsf{NE}$ is the McLennan-Tourky analytic reduction in Section (ref). Given a description of an $O(1)$-Lipschitz function $f:[0,1]^d \rightarrow [0,1]^d$, with $d$ linear in the length $n$ of the function's description, the simplest reduction would proceed as follows. Alice and Bob each have a strategy set corresponding to the discretized hypercube $H_{\epsilon}$ (points of $[0,1]^d$ such that every coordinate is a multiple of $\epsilon$). Alice's and Bob's payoffs are defined as in the proof of Theorem (ref): for strategies $x,y \in H_{\epsilon}$, Alice's payoff is
and Bob's payoff is
(Here $ {\| {\cdot} \|} $ denotes the normalized $\ell_2$ norm.) Thus Alice wants to imitate Bob's strategy, while Bob wants to imitate the image of Alice's strategy under the function $f$.
This reduction is correct in that in every $\epsilon$-approximate Nash equilibrium of this game, Alice's and Bob's strategies are concentrated around an $O(\epsilon)$-approximate fixed point of the given function $f$ (in the normalized $\ell_2$ norm). See also the discussion in Section (ref).
The issue is that the reduction is not efficient enough. Alice and Bob each have $\Theta((1/\epsilon)^d)$ pure strategies; since $d = \Theta(n)$, this is exponential in the size $n$ of the given {\sc $\epsilon$-BFP}\xspace instance, rather than exponential in $\sqrt{n}$. This exponential blow-up in size means that this reduction has no implications for the problem of computing an approximate Nash equilibrium.
How can we achieve a blow-up exponential in $\sqrt{n}$ rather than in $n$? We might guess that the birthday paradox is somehow involved. To build up our intuition, we'll discuss at length a trivial special case of the {\sc $\epsilon$-BFP}\xspace problem. It turns out that the hard functions used in Theorem (ref) are in some sense surprisingly close to this trivial case.
For now, we consider only instances $f$ of {\sc $\epsilon$-BFP}\xspace where $f$ is {\em separable}. That is, $f$ has the form
for efficiently computable functions $f_1,\ldots,f_d : [0,1]\rightarrow [0,1]$. Separable functions enjoy the ultimate form of “local decodability”---to compute the $i$th coordinate of $f(x)$, you only need to know the $i$th coordinate of $x$. Finding a fixed point of a separable function is easy: the problem decomposes into $d$ one-dimensional fixed point problems (one per coordinate), and each of these can be solved efficiently by a form of binary search. The hard functions used in Theorem (ref) possess a less extreme form of “local decodability,” in that each coordinate of $f(x)$ can be computed using only a small amount of “advice” about $f$ and $x$ (cf., the $\epsilon$-{\sc 2BFP}\xspace $\le \epsilon\text{-}\mathsf{NE}$ reduction in Section (ref)).
Can we at least compute fixed points of separable functions via approximate Nash equilibria, using a reduction with only subexponential blow-up? The key idea is, instead of Alice and Bob each picking one of the (exponentially many) points of the discretized hypercube $H_{\epsilon}$, each will pick {\em only a single coordinate} of points $x$ and $y$. Thus a pure strategy of Alice comprises an index $i \in [d]$ and a number $x_i \in [0,1]$ that is a multiple of $\epsilon$, and similarly Bob chooses $j \in [d]$ and $y_j \in [0,1]$. Given choices $(i,x_i)$ and $(j,y_j)$, Alice's payoff is defined as \[
\] and Bob's payoff is \[
\] Thus Alice and Bob receive payoff 0 unless they “interact,” meaning choose the same coordinate to play in, in which case their payoffs are analogous to (ref) and (ref). Note that Bob's payoff is well defined only because we have assumed that $f$ is separable (Bob only knows the coordinate $x_i$ proposed by Alice, but this is enough to compute the $i$th coordinate of the output of $f$ and hence his payoff). Each player has only $\approx \tfrac{d}{\epsilon}$ strategies, so this is a polynomial-time reduction, with no blow-up.
The good news is that (approximate) fixed points give rise to (approximate) Nash equilibria of this game. Specifically, if $\hat{x}=\hat{y}=f(\hat{x})$ is a fixed point of $f$, then the following is a Nash equilibrium (as you should check): Alice and Bob pick their coordinates $i,j$ uniformly at random and set $x_i=\hat{x}_i$ and $y_j=\hat{y}_j$. The problem is that the game also has equilibria other than the intended ones, for example where Alice and Bob choose pure strategies with $i=j$ and $x_i=y_i=f_i(x_i)$.
Our second attempt failed because Alice and Bob were not forced to randomize their play over all $d$ coordinates. We can address this issue with a game-theoretic gadget called an {\em Alth\"ofer game} A94.\footnote{Similar ideas have been used previously, including in the proofs that computing an $\epsilon$-approximate Nash equilibrium with $\epsilon$ inverse polynomial in $n$ is a $\mathsf{PPAD}$-complete problem DGP09,CDT09.} For a positive and even integer $k$, this $k \times \binom{k}{k/2}$ game is defined as follows.
For example, here is the payoff matrix for the $k=4$ case (with only Alice's payoffs shown): \[ \left(
\right) \] Every Alth\"ofer game is a zero-sum game with value 0: for both players, choosing a uniformly random strategy guarantees expected payoff 0. The following claim proves a robust converse for Alice's play. Intuitively, if Alice deviates much from the uniform distribution, Bob is well-positioned to punish her.\footnote{The statement and proof here include a constant-factor improvement, due to Salil Vadhan, over those in R16.}
In Claim (ref), it's important that the loss in statistical distance (as a function of $\epsilon$) is independent of the size $k$ of the game. For example, straightforward generalizations of rock-paper-scissors fail to achieve the guarantee in Claim (ref).
\paragraph{Gluing Games.} We incorporate Alth\"ofer games into our coordinatewise play game as follows. Let
Consider the following game, where Alice and Bob effectively play all three games simultaneously:
The good news is that, in every exact Nash equilibrium of the combined game, Alice and Bob mix uniformly over their choices of $i$ and $j$. Intuitively, because deviating from the uniform strategy can be punished by the other player at a rate linear in the deviation (Claim (ref)), it is never worth doing (no matter what happens in $G_1$). Given this, \`a la the McLennan-Tourky reduction (Theorem (ref)), the $x_i$'s and $y_j$'s must correspond to a fixed point of $f$ (for each $i$, Alice must set $x_i$ to the center of mass of Bob's distribution over $y_i$'s, and then Bob must set $y_i = f_i(x_i)$).
The bad news is that this argument breaks down for $\epsilon$-approximate Nash equilibria with constant $\epsilon$. The reason is that, even when the distributions of $i$ and $j$ are perfectly uniform, the two players interact (i.e., choose $i=j$) only with probability $1/d$. This means that the contribution of the game $G_1$ to the expected payoffs is at most $1/d \ll \epsilon$, freeing the players to choose their $x_i$'s and $y_j$'s arbitrarily. Thus we need another idea to force Alice and Bob to interact more frequently.
A second problem is that the sizes of the Alth\"ofer games are too big---exponential in $d$ rather than in $\sqrt{d}$.
To solve both of the problems with the third attempt, we force Alice and Bob to play larger sets of coordinates at a time. Specifically, we view $[d]$ as a $\sqrt{d} \times \sqrt{d}$ grid, and any $x,y\in [0,1]^d$ as $\sqrt{d}\times \sqrt{d}$ matrices. Now Alice and Bob will play a row and column of their matrices, respectively, and their payoffs will be determined by the entry where the row and column intersect. That is, we replace the coordinatewise game of Section (ref) with the following {\em blockwise game}:
Now glue this game together with $k\times {k \choose k/2}$ and $\binom{k}{k/2} \times k$ Alth\"ofer games with $k=\sqrt{d}$, as in Section (ref). (For example, Alice's index $i \in \left[\sqrt{d}\right]$ is identified with a row in the first Alth\"ofer game, and now Alice also picks a subset $S \subseteq \left[\sqrt{d}\right]$ in the second Alth\"ofer game, in addition to $i$ and $x_{i*}$.) This construction yields exactly what we want: a game of size $\exp(\tilde{O}(k)) = \exp(\tilde{O}(\sqrt{d}))$ in which every $\epsilon$-approximate Nash equilibrium can be easily translated to a $\delta$-approximate fixed point of $f$ (in the normalized $\ell_2$ norm), where $\delta$ depends only on $\epsilon$.\footnote{The $\tilde{O}(\cdot)$ notation suppresses logarithmic factors.}\footnote{In more detail, in every $\epsilon$-approximate Nash equilibrium of the game, Alice and Bob both randomize nearly uniformly over $i$ and $j$; this is enforced by the Alth\"ofer games as in Section (ref). Now think of each player as choosing its strategy in two stages, first the index $i$ or $j$ and then the corresponding values $x_{i*}$ or $y_{*j}$ in the row or column. Whenever Alice plays $i$, her best response (conditioned on $i$) is to play $\mathbf{E}\ifthenelse{\not\equal{}{}}{_{}}{}\!\left[y_{ij}\right]$ in every column $j$, where the expectation is over the distribution of $y_{ij}$ conditioned on Bob choosing index $j$. In an $\epsilon$-approximate Nash equilibrium, in most coordinates, Alice must usually choose $x_{ij}$'s that are close to this best response. Similarly, for most indices $j \in \left[\sqrt{d}\right]$, whenever Bob chooses $j$, he must usually choose a value of $y_{ij}$ that is close to $\mathbf{E}\ifthenelse{\not\equal{}{}}{_{}}{}\!\left[f_{ij}(x_{ij})\right]$ (for each $i$). It can be shown that these facts imply that Alice's strategy corresponds to a $\delta$-approximate fixed point (in the normalized $\ell_2$ norm), where $\delta$ is a function of $\epsilon$ only.}
We now know how to use an $\epsilon$-approximate Nash equilibrium of a subexponential-size game (with constant $\epsilon$) to compute a $\delta$-approximate fixed point of a function that is separable in the sense of (ref). This is not immediately interesting, because a fixed point of a separable function is easy to find by doing binary search independently in each coordinate. The hard Brouwer functions identified in Theorem (ref) have lots of nice properties, but they certainly aren't separable.
Conceptually, the rest of the proof of Theorem (ref) involves pushing in two directions: first, identifying hard Brouwer functions that are even “closer to separable” than the functions in Theorem (ref); and second, extending the reduction in Section (ref) to accommodate “close-to-separable” functions. We already have an intuitive feel for what the second step looks like, from Step 4 of our communication complexity lower bound (Section (ref) in Solar Lecture 3), where we enlarged the strategy sets of the players so that they could smuggle “advice” about how to decode a hard Brouwer function $f$ at a given point. We conclude the lecture with one key idea for the further simplification of the hard Brouwer functions in Theorem (ref).
Recall the hard Brouwer functions constructed in our communication complexity lower bound (see Section (ref)), which “follow the line” of an embedding of an {\sc EoL}\xspace instance, as well as the additional tweaks needed to prove Theorem (ref) (see Section (ref)). We are interested in the “local decodability” properties of these functions. That is, if Bob needs to compute the $j$th coordinate of $f(x)$ (to evaluate the $j$th term in his payoff in (ref)), how much does he need to know about $x$? For a separable function $f=(f_1,\ldots,f_d)$, he only needs to know $x_j$. For the hard Brouwer functions in Theorem (ref), Bob needs to know whether or not $x$ is close to an edge (of the embedding of the succinct {\sc EoL}\xspace instance into the hypercube) and, if so, which edge (or pair of edges, if $x$ is close to a vertex). Ultimately, this requires evaluating the successor circuit $S$ and predecessor circuit $P$ of the succinct {\sc EoL}\xspace instance that defines the hard Brouwer function. It is therefore in our interest to force $S$ and $P$ to be as simple as possible, subject to the succinct {\sc EoL}\xspace problem remaining $\mathsf{PPAD}$-complete. In a perfect world, minimal advice (say, $O(1)$ bits) would be enough to compute $S(v)$ and $P(v)$ from $v$.\footnote{It is also important that minimal advice suffices to translate between points $x$ of the hypercube and vertices $v$ of the underlying succinct {\sc EoL}\xspace instance (as $f$ is defined on the former, while $S$ and $P$ operate on the latter). This can be achieved by using a state-of-the-art locally decodable error-correcting code (with query complexity $d^{o(1)}$, similar to that in KMRS17) to embed the vertices into the hypercube (as described in Section (ref)). Incorporating the advice that corresponds to local decoding into the game produced by the reduction results in a further blow-up of $2^{d^{o(1)}}$. This is effectively absorbed by the $2^{\sqrt{d}}$ blow-up that is already present in the reduction in Section (ref).} The following lemma implements this idea. It shows that a variant of the succinct {\sc EoL}\xspace problem, called {\sc Local {\sc EoL}\xspace}, remains $\mathsf{PPAD}$-complete even when $S$ and $P$ are guaranteed to change only $O(1)$ bits of the input, and when $S$ and $P$ are $\mathrm{NC}^0$ circuits (and hence each output bit depends on only $O(1)$ input bits).
The proof idea is to start from the original circuits $S$ and $P$ of a succinct {\sc EoL}\xspace instance and form circuits $S'$ and $P'$ that operate on partial computation transcripts, carrying out the computations performed by the circuits $S$ or $P$ one gate/line at a time (with $O(1)$ bits changing in each step of the computation). The vertex set $V$ then corresponds to the set of valid partial computation transcripts. The full proof is not overly difficult; see R16 for the details. This reduction from succinct {\sc EoL}\xspace to {\sc Local {\sc EoL}\xspace} can be implemented in linear time, so our assumption that the former problem admits no subexponential-time algorithm carries over to the latter problem.
In the standard succinct {\sc EoL}\xspace problem, every $n$-bit string $v \in \{0,1\}^n$ is a legitimate vertex. In the {\sc Local {\sc EoL}\xspace} problem, only elements of $\{0,1\}^n$ that satisfy the given $\mathrm{AC}^0$ circuit are legitimate vertices. In our reduction, we need to produce a game that also incorporates checking membership in $V$, also with only a $d^{o(1)}$ blow-up in how much of $x$ we need to access. This is the reason why R16 needs to develop customized PCP machinery in his proof of Theorem (ref). These PCP proofs can then be incorporated into the blockwise play game (Section (ref)), analogous to how we incorporated a low-cost interactive protocol into the game in our reduction from {\sc 2EoL}\xspace to $\epsilon\text{-}\mathsf{NE}$ in Section (ref).
\part{Lunar Lectures}
\titleformat{\chapter}[display] {\normalfont\filcenter} {\titlerule[1pt] \titlerule {Lunar Lecture} \thechapter} {.5ex} {\normalfont\slshape}
\setcounter{chapter}{0}
\chapter{How Computer Science Has Influenced Real-World Auction Design.\\ Case Study: The 2016--2017 FCC Incentive Auction} \titlerule
Computer science is changing the way auctions are designed and implemented. For over 20 years, the US and other countries have used {\em spectrum auctions} to sell licenses for wireless spectrum to the highest bidder. What's different this decade, and what necessitated a new auction design, is that in the US the juiciest parts of the spectrum for next-generation wireless applications are already accounted for, owned by over-the-air television broadcasters. This led Congress to authorize the FCC in the fall of 2012 to design a novel auction (the {\em FCC Incentive Auction}) that would repurpose spectrum---procuring licenses from television broadcasters (a relatively low-value activity) and selling them to parties that would put them to better use (e.g., telecommunication companies who want to roll out the next generation of wireless broadband services). Thus the FCC Incentive Auction is really a {\em double auction}, comprising two stages: a reverse auction, where the government buys back licenses for spectrum from their current owners; and then a forward auction, where the government sells the procured licenses to the highest bidder. Computer science techniques played a crucial role in the design of the new reverse auction. The main aspects of the forward auction have been around a long time; here, theoretical computer science has contributed on the analysis side, and to understanding when and why such forward auctions work well. Sections (ref) and (ref) give more details on the reverse and forward parts of the auction, respectively.
The FCC Incentive Auction finished around the end of March 2017, and so the numbers are in. The government spent roughly 10 billion USD in the reverse part of the auction buying back licenses from television broadcasters, and earned roughly 20 billion USD of revenue in the forward auction. Most of the 10 billion USD profit was used to reduce the US debt!\footnote{This was the plan all along, which is probably one of the reasons the bill didn't have trouble passing a notoriously partisan Congress. Another reason might be the veto-proof title of the bill: “The Middle Class Tax Relief and Job Creation Act.”}
The reverse auction is the part of the FCC Incentive Auction that was totally new, and where computer science techniques played a crucial role in the design. The auction format, proposed by Milgrom and Segal MS20, is what's called a {\it descending clock auction}. By design, the auction is very simple from the perspective of any one participant. The auction is iterative, and operates in rounds. In each round of the auction, each remaining broadcaster is asked a question of the form: “Would you or would you not be willing to sell your license for (say) 1 million dollars?” The broadcaster is allowed to say “no,” with the consequence of getting kicked out of the auction forevermore (the station will keep its license and remain on the air, and will receive no compensation from the government). The broadcaster is also allowed to say “yes” and accept the buyout offer. In the latter case, the government will not necessarily buy the license for 1 million dollars---in the next round, the broadcaster might get asked the same question, with a lower buyout price (e.g., 950,000 USD). If a broadcaster is still in the auction when it ends (more on how it ends in a second), then the government does indeed buy their license, at the most recent (and hence lowest) buyout offer. Thus all a broadcaster has to do is answer a sequence of “yes/no” questions for some decreasing sequence of buyout offers. The obvious strategy for a broadcaster is to formulate the lowest acceptable offer for their license, and to drop out of the auction once the buyout price drops below this threshold.
The auction begins with very high buyout offers, so that every broadcaster would be ecstatic to sell their license at the initial price. Intuitively, the auction then tries to reduce the buyout prices as much as possible, subject to clearing a target amount of spectrum. Spectrum is divided into channels which are blocks of 6 MHz each. For example, one could target broadcasters assigned to channels 38--51, and insist on clearing 10 out of these 14 channels (60 MHz overall).\footnote{The FCC Incentive Auction wound up clearing 84 MHz of spectrum (14 channels).} By “clearing a channel,” we mean clearing it {\em nationwide}. Of course, in the descending clock auction, bidders will drop out in an uncoordinated way---perhaps the first station to drop out is channel 51 in Arizona, then channel 41 in western Massachusetts, and so on. To clear several channels nationwide without buying out essentially everybody, it was essential for the government to use its power to {\em reassign} the channels of the stations that remain on the air. Thus while a station that drops out of the auction is guaranteed to retain its license, it is not guaranteed to retain its channel---a station broadcasting on channel 51 before the auction might be forced to broadcast on channel 41 after the auction.
The upshot is that the auction maintains the invariant that the stations that have dropped out of the auction (and hence remain on the air) can be assigned channels so that at most a target number of channels are used (in our example, 4 channels). This is called the {\em repacking problem}. Naturally, two stations with overlapping broadcasting regions cannot be assigned the same channel (otherwise they would interfere with each other). See Figure (ref).
Any properly trained computer scientist will recognize the repacking problem as the $\mathsf{NP}$-complete graph coloring problem in disguise.\footnote{The actual repacking problem was more complicated---overlapping stations cannot even be assigned adjacent channels, and there are idiosyncratic constraints at the borders with Canada and Mexico. See LMS17 for more details. But the essence of the repacking problem really is graph coloring.} For the proposed auction format to be practically viable, it must quickly solve the repacking problem. Actually, make that thousands of repacking problems every round of the auction!\footnote{Before the auction makes a lower offer to some remaining broadcaster in the auction, it needs to check that it would be OK for the broadcaster to decline and drop out of the auction. If a station's dropping out would render the repacking problem infeasible, then that station's buyout price remains frozen until the end of the auction.}
The responsibility of quickly solving repacking problems fell to a team led by Kevin Leyton-Brown (see FNL17,LMS17). The FCC gave the team a budget of one minute per repacking problem, ideally with most instances solved within one second. The team's approach was to build on state-of-the-art solvers for the satisfiability (SAT) problem. As you can imagine, it's straightforward to translate an instance of the repacking problem into a SAT formula (even with the idiosyncratic constraints).\footnote{A typical representative instance would have thousands of variables and tens of thousands of constraints.} Off-the-shelf SAT solvers did pretty well, but still timed out on too many representative instances.\footnote{Every time the repacking algorithm fails to find a repacking when one exists, money is left on the table---the auction has to conservatively leave the current station's buyout offer frozen, even though it could have safely lowered it.} Leyton-Brown's team added several new innovations, including taking advantage of problem structure specific to the application and implementing a number of caching techniques (reusing work done solving previous instances to quickly solve closely related new instances). In the end, they were able to solve more than 99% of the relevant repacking problems in under a minute.
Hopefully the high-level point is clear:
One final twist: the novel reverse auction format motivates some basic algorithmic questions (and thus ideas flow from computer science to auction theory and back). We can think of the auction as an algorithm, a heuristic that tries to maximize the value of the stations that remain on the air, subject to clearing the target amount of spectrum. Milgrom and Segal MS20 prove that, ranging over all ways of implementing the auction (i.e., of choosing the sequences of descending prices), the corresponding algorithms are exactly the {\em reverse greedy algorithms}.\footnote{For example, Kruskal's algorithm for the minimum spanning tree problem (start with the empty set, go through the edges of the graph from cheapest to most expensive, adding an edge as long as it doesn't create a cycle) is a standard (forward) greedy algorithm. The reverse version is: start with the entire edge set, go through the edges in reverse sorted order, and remove an edge whenever it doesn't disconnect the graph. For the minimum spanning tree problem (and more generally for finding the minimum-weight basis of a matroid), the reverse greedy algorithm is just as optimal as the forward one. In general (and even for e.g. bipartite matching), the reverse version of a good forward greedy algorithm can be bad DGR14.} This result gives the first extrinsic reason to study the power and limitations of reverse greedy algorithms, a research direction explored by DGR14 and GMR17.
Computer science did not have an opportunity to influence the design of the forward auction used in the FCC Incentive Auction, which resembles the formats used over the past 20+ years. Still, the theoretical computer science toolbox turns out to be ideally suited for explaining when and why these auctions work well.\footnote{Much of the discussion in Sections (ref)--(ref) is from f13, which in turn takes inspiration from Milgrom:2004jx.}
Spectrum auction design is stressful, because small mistakes can be extremely costly. One cautionary tale is provided by an auction run by the New Zealand government in 1990 (before governments had much experience with auctions). For sale were 10 essentially identical national licenses for television broadcasting. For some reason, lost to the sands of time, the government decided to sell these licenses by running 10 second-price auctions in parallel. A {\em second-price} or {\em Vickrey} auction for a single good is a sealed-bid auction that awards the item to the highest bidder and charges her the highest bid by someone else (the second-highest bid overall). When selling a single item, the Vickrey auction is often a good solution. In particular, each bidder has a dominant strategy (always at least as good as all alternatives), which is to bid her true maximum willingness-to-pay.\footnote{Intuitively, a second-price auction shades your bid optimally after the fact, so there's no reason to try to game it.}\footnote{For a more formal treatment of single-item auctions, see Section (ref) in Lunar Lecture 4.}
The nice properties of a second-price auction evaporate if many of them are run simultaneously. A bidder can now submit up to one bid in each auction, with each license awarded to the highest bidder (on that license) at a price equal to the second-highest bid (on that license). With multiple simultaneous auctions, it is no longer clear how a bidder should bid. For example, imagine you want one of the licenses, but only one. How should you bid? One legitimate strategy is to pick one of the licenses---at random, say---and go for it. Another strategy is to bid less aggressively on multiple licenses, hoping that you get one at a bargain price, and that you don't inadvertently win extra licenses that you don't want. The difficulty is trading off the risk of winning too many licenses with the risk of winning too few.
The challenge of bidding intelligently in simultaneous sealed-bid auctions makes the auction format prone to poor outcomes. The revenue in the 1990 New Zealand auction was only \$36 million, a paltry fraction of the projected \$250 million. On one license, the high bid was \$100,000 while the second-highest bid (and selling price) was \$6! On another, the high bid was \$7 million and the second-highest was \$5,000. To add insult to injury, the winning bids were made available to the public, who could then see just how much money was left on the table!
Modern spectrum auctions are based on {\em simultaneous ascending auctions (SAAs)}, following 1993 proposals by McAfee and by Milgrom and Wilson. You've seen---in the movies, at least---the call-and-response format of an ascending single-item auction, where an auctioneer asks for takers at successively higher prices. Such an auction ends when there's only one person left accepting the currently proposed price (who then wins, at this price). Conceptually, SAAs are like a bunch of single-item English auctions being run in parallel in the same room, with one auctioneer per item.
The primary reason that SAAs work better than sequential or sealed-bid auctions is {\em price discovery}. As a bidder acquires better information about the likely selling prices of licenses, she can implement mid-course corrections---abandoning licenses for which competition is fiercer than anticipated, snapping up unexpected bargains, and rethinking which packages of licenses to assemble. The format typically resolves the miscoordination problems that plague simultaneous sealed-bid auctions.
SAAs have two big vulnerabilities. The first problem is {\em demand reduction}, and this is relevant even when items are substitutes.\footnote{Items are substitutes if they provide diminishing returns---having one item only makes others less valuable. For two items $A$ and $B$, for example, the substitutes condition means that a bidder's value for the bundle of $A$ and $B$ is at most the sum of her values for $A$ and $B$ individually. In a spectrum auction context, two licenses for the same area with equal-sized frequency ranges are usually substitute items.} Demand reduction occurs when a bidder asks for fewer items than she really wants, to lower competition and therefore the prices paid for the items that it gets.
To illustrate, suppose there are two identical items and two bidders. By the {\em valuation} of a bidder for a given bundle of items, we mean her maximum willingness to pay for that bundle. Suppose the first bidder has valuation 10 for one of the items and valuation 20 for both. The second bidder has valuation 8 for one of the items and does not want both (i.e., her valuation remains 8 for both). The socially optimal outcome is to give both licenses to the first bidder. Now consider how things play out in an SAA. The second bidder would be happy to have either item at any price less than 8. Thus, the second bidder drops out only when the prices of both items exceed 8. If the first bidder stubbornly insists on winning both items, her utility is $20-16=4$. An alternative strategy for the first bidder is to simply concede the second item and never bid on it. The second bidder takes the second item and (because she only wants one license) withdraws interest in the first, leaving it for the first bidder. Both bidders get their item essentially for free, and the utility of the first bidder has jumped to 10.
The second big problem with SAAs is relevant when items can be complements, and is called the {\em exposure problem}.\footnote{Items are complements if there are synergies between them, so that possessing one makes others more valuable. With two items $A$ and $B$, this translates to a bidder's valuation for the bundle of $A$ and $B$ exceeding the sum of her valuations for $A$ and $B$ individually. Complements arise naturally in wireless spectrum auctions, as some bidders want a collection of licenses that are adjacent, either in their geographic areas or in their frequency ranges.} As an example, consider two bidders and two nonidentical items. The first bidder only wants both items---they are complementary items for the bidder---and her valuation is 100 for them (and 0 for anything else). The second bidder is willing to pay 75 for either item but only wants one item. The socially optimal outcome is to give both items to the first bidder. But in an SAA, the second bidder will not drop out until the price of both items reaches 75. The first bidder is in a no-win situation: to get both items she would have to pay 150, more than her value. The scenario of winning only one item for a nontrivial price could be even worse. Thus the exposure problem leads to economically inefficient allocations for two reasons. First, an overly aggressive bidder might acquire unwanted items. Second, an overly tentative bidder might fail to acquire items for which she has the highest valuation.
If you ask experts who design or consult for bidders in real-world SAAs, a rough consensus emerges about when they are likely to work well.
There are a number of beautiful and useful theoretical results about spectrum auctions in the economics literature, but none map cleanly to these two folklore beliefs. A possible explanation: translating these beliefs into theorems seems to fundamentally involve approximate optimality guarantees, a topic that is largely avoided by economists but right in the wheelhouse of theoretical computer science.
In the standard model of {\em combinatorial auctions}, there are $n$ bidders (e.g., telecoms) and $m$ items (e.g., licenses).\footnote{This model is treated more thoroughly in the next lecture (see Section (ref)).} Bidder $i$ has a nonnegative valuation $v_i(S)$ for each subset $S$ of items she might receive. Note that, in general, describing a bidder's valuation function requires $2^m$ parameters. Each bidder wants to maximize her utility, which is the value of the items received minus the total price paid for them. From a social perspective, we'd like to award bundles of items $T_1,\ldots,T_n$ to the bidders to maximize the {\em social welfare} $\sum_{i=1}^n v_i(T_i)$.
To make the first folklore belief precise, we need to commit to a definition of “without strong complements” and to a specific auction format. We'll focus on simultaneous first-price auctions (S1As), where each bidder submits a separate bid for each item, for each item the winner is the highest bidder (on that item), and winning bidders pay their bid on each item won.\footnote{Similar results hold for other auction formats, like simultaneous second-price auctions. Directly analyzing what happens in iterative auctions like SAAs when there are multiple items appears difficult.} One relatively permissive definition of “complement-free” is to restrict bidders to have {\em subadditive valuations}. This means what it sounds like: if $A$ and $B$ are two bundles of items, then bidder $i$'s valuation $v_i(A \cup B)$ for their union should be at most the sum $v_i(A)+v_i(B)$ of her valuations for each bundle separately. Observe that subadditivity is violated in the exposure problem example in Section (ref).
We also need to define what we mean by “the outcome of an auction” like S1As. Remember that bidders are strategic, and will bid to maximize their utility (value of items won minus the price paid). Thus we should prove approximation guarantees for the {\em equilibria} of auctions. Happily, computer scientists have been working hard since 1999 to prove approximation guarantees for game-theoretic equilibria, also known as bounds on {\em the price of anarchy} KP99,book,RT00.\footnote{See Section (ref) of the next lecture for a formal definition.} In the early days, price-of-anarchy bounds appeared somewhat ad hoc and problem-specific. Fast forwarding to the present, we now have a powerful and user-friendly theory for proving price-of-anarchy bounds, which combine “extension theorems” and “composition theorems” to build up bounds for complex settings (including S1As) from bounds for simple settings.\footnote{We will say more about this theory in Lunar Lecture 5. See also RST17 for a recent survey.} In particular, FFGL13 proved the following translation of Folklore Belief \#1.\footnote{To better appreciate this result, we note that multi-item auctions like S1As are so strategically complex that they have historically been seen as unanalyzable. For example, we have no idea what their equilibria look like in general. Nevertheless, we can prove good approximation guarantees for them!}
One version of Theorem (ref) concerns (mixed) Nash equilibria in the full-information model (in which bidders' valuations are common knowledge), as studied in the Solar Lectures. Even here, the bound in Theorem (ref) is tight in the worst case CKST16. The approximation guarantee in Theorem (ref) holds more generally for {\em Bayes-Nash equilibria}, the standard equilibrium notion for games of incomplete information.\footnote{In more detail, in this model there is a commonly known prior distribution over bidders' valuations. In a Bayes-Nash equilibrium, every bidder bids to maximize her expected utility given her information at the time: her own valuation, her posterior belief about other bidders' valuations, and the bidding strategies (mapping valuations to bids) used by the other bidders. Theorem (ref) continues to hold for every Bayes-Nash equilibrium of an S1A, as long as bidders' valuations are independently (and not necessarily identically) distributed.}
Moving on to the second folklore belief, let's now drop the subadditivity restriction. S1As no longer work well.
Thus for S1As, the perspective of worst-case approximation confirms the dichotomy between the cases of substitutes and complements. But the lower bound in Theorem (ref) applies only to one specific auction format. Could we do better with a different natural auction format? Folklore Belief \#2 asserts the stronger statement that {\em no} “simple” auction works well with general valuations. This stronger statement can also be translated into a theorem (using nondeterministic communication complexity), and this will be the main subject of Lunar Lecture 2.
The definition of “simple” used in Theorem (ref) is quite generous: it requires only that the number of strategies available to each player is {\em sub-doubly-exponential} in the number of items $m$. For example, running separate single-item auctions provides each player with only an exponential (in $m$) number of strategies (assuming a bounded number of possible bid values for each item). Thus Theorem (ref) makes use of the theoretical computer science toolbox to provide solid footing for Folklore Belief \#2.
\chapter{Communication Barriers to Near-Optimal Equilibria} \titlerule
This lecture is about the communication complexity of the welfare-maximization problem in combinatorial auctions and its implications for the price of anarchy of simple auctions. Section (ref) defines the model, Section (ref) proves lower bounds for nondeterministic communication protocols, and Section (ref) gives a black-box translation of these lower bounds to equilibria of simple auctions. In particular, Section (ref) provides the proof of Theorem (ref) from last lecture. Section (ref) concludes with a juicy open problem on the topic.\footnote{Much of this lecture is drawn from w15.}
Recall from Section (ref) the basic setup in the study of combinatorial auctions.
Note that we may have more than two players---more than just Alice and Bob. (For example, you might want to think of $k$ as $\approx m^{1/3}$.) Also note that the description length of a player's valuation is exponential in the number of items $m$.
In the {\em welfare-maximization problem}, the goal is to partition the items $M$ into sets $T_1,\ldots,T_k$ to maximize, at least approximately, the social welfare
using communication polynomial in $k$ and $m$. Note this amount of communication is logarithmic in the sizes of the private inputs. Maximizing social welfare (ref) is the most commonly studied objective in combinatorial auctions, and it is the one we will focus on in this lecture.
This section studies the communication complexity of computing an approximately welfare-maximizing allocation in a combinatorial auction. For reasons that will become clear in Section (ref), we are particularly interested in the problem's nondeterministic communication complexity.\footnote{For basic background on nondeterministic multi-party communication protocols, see KN96 or w15.}
We begin with a result of Nisan Nis02 showing that, alas, computing even a very weak approximation of the welfare-maximizing allocation requires exponential communication. To make this precise, it is convenient to turn the optimization problem of welfare maximization into a decision problem. In the Welfare-Maximization($k$) problem, the goal is to correctly identify inputs that fall into one of the following two cases:
Arbitrary behavior is permitted on inputs that fail to satisfy either (1) or (0). Clearly, communication lower bounds for Welfare-Maximization($k$) apply to the more general problem of obtaining a better-than-$k$-approximation of the maximum welfare.\footnote{Achieving a $k$-approximation is trivial: every player communicates her value $v_i(M)$ for the whole set of items, and the entire set of items is awarded to the bidder with the highest value for them.}
This lower bound is exponential in $m$, provided that $m = \Omega(k^{2+\epsilon})$ for some $\epsilon > 0$. Since communication complexity lower bounds apply even to players who cooperate perfectly, this impossibility result holds even when all of the (tricky) incentive issues are ignored.
The plan for the proof of Theorem (ref) is to reduce a multi-party version of the {\sc Disjointness}\xspace problem to the Welfare-Maximization($k$) problem. There is some ambiguity about how to define a version of {\sc Disjointness}\xspace for three or more players. For example, suppose there are three players, and among the three possible pairings of them, two have disjoint sets while the third have intersecting sets. Should this count as a “yes” or “no” instance? We'll skirt this issue by worrying only about unambiguous inputs, that are either “totally disjoint” or “totally intersecting.”
Formally, in the Multi-Disjointness\xspace problem, each of the $k$ players $i$ holds an input $\mathbf{x}_i \in \{0,1\}^n$. (Equivalently, a set $S_i \subseteq \{1,2,\ldots,n\}$.) The task is to correctly identify inputs that fall into one of the following two cases:
When $k=2$, this is the standard {\sc Disjointness}\xspace problem. When $k > 2$, there are inputs that are neither 1-inputs nor 0-inputs. We let protocols off the hook on such ambiguous inputs---they can answer “1” or “0” with impunity.
The following communication complexity lower bound for Multi-Disjointness\xspace is credited to Jaikumar Radhakrishnan and Venkatesh Srinivasan in Nis02. (The proof is elementary, and for completeness is given in Section (ref).)
This nondeterministic lower bound is for verifying a 1-input. (It is easy to verify a 0-input---the prover just suggests the index of an element $r$ in $\cap_{i=1}^k S_i$.) \footnote{In proving Theorem (ref), we'll be interested in the case where $k$ is much smaller than $n$, such as $k = \Theta(\log n)$. Intuition might suggest that the lower bound should be $\Omega(n)$ rather than $\Omega(n/k)$, but this is incorrect---a slightly non-trivial argument shows that Theorem (ref) is tight for nondeterministic protocols (for all small enough $k$, like $k = O(\sqrt{n})$). This factor-$k$ difference won't matter for our applications, however.}
The proof of Theorem (ref) relies on Theorem (ref) and a combinatorial gadget. We construct this gadget using the probabilistic method. Consider $t$ random partitions $P^1,\ldots,P^t$ of $M$, where $t$ is a parameter to be defined later. By a random partition $P^j = (P^j_1,\ldots,P^j_k)$, we mean that each of the $m$ items is assigned to exactly one of the $k$ players, independently and uniformly at random.
We are interested in the probability that two classes of different partitions intersect: for all $i \neq i'$ and $j \neq \ell$, because the probability that a given item is assigned to $i$ in $P^j$ and also to $i'$ in $P^{\ell}$ is $\tfrac{1}{k^2}$, we have \[ \mathbf{Pr}\ifthenelse{\not\equal{}{}}{_{}}{}\!\left[P^j_i \cap P^{\ell}_{i'} = \emptyset\right] = \left( 1 - \frac{1}{k^2} \right)^m \le e^{-m/k^2}. \] Taking a Union Bound over the $k$ choices for $i$ and $i'$ and the $t$ choices for $j$ and $\ell$, we have
Call $P^1,\ldots,P^t$ an {\em intersecting family} if $P^j_i \cap P^{\ell}_{i'} \neq \emptyset$ whenever $i \neq i'$, $j \neq \ell$. By (ref), the probability that our random experiment fails to produce an intersecting family is less than 1 provided $t < \tfrac{1}{k}e^{m/2k^2}$. The following lemma is immediate.
A simple combination of Theorem (ref) and Lemma (ref) now proves Theorem (ref).
To an algorithms person, Theorem (ref) is depressing, as it rules out any non-trivial positive results. A natural idea is to seek positive results by imposing additional structure on players' valuations. Many such restrictions have been studied. We consider here the case of {\em subadditive} valuations (see also Section (ref) of the preceding lecture), where each $v_i$ satisfies $v_i(S \cup T) \le v_i(S) + v_i(T)$ for every pair $S,T \subseteq M$.
Our reduction in Theorem (ref) easily implies a weaker inapproximability result for welfare maximization with subadditive valuations. Formally, define the Welfare-Maximization($2$) problem as that of identifying inputs that fall into one of the following two cases:
Communication lower bounds for Welfare-Maximization($2$) apply also to the more general problem of obtaining a better-than-$2$-approximation of the maximum social welfare.
This theorem follows from a modification of the proof of Theorem (ref). The 0-1 valuations used in that proof are not subadditive, but they can be made subadditive by adding 1 to each bidder's valuation $v_i(T)$ of each non-empty set $T$. The social welfare obtained in inputs corresponding to 1- and 0-inputs of Multi-Disjointness\xspace become $k+1$ and $2k$, respectively, and this completes the proof of Theorem (ref).
There is also a quite non-trivial deterministic and polynomial-communication protocol that guarantees a 2-approximation of the social welfare when bidders have subadditive valuations F06.
The lower bounds of the previous section show that every protocol for the welfare-maximization problem that interacts with the players and then explicitly computes an allocation has either a bad approximation ratio or high communication cost. Over the past decade, many researchers have considered shifting the work from the protocol to the players, by analyzing the equilibria of simple auctions. Can such equilibria bypass the communication complexity lower bounds proved in Section (ref)? The answer is not obvious, because equilibria are defined non-constructively, and not through a low-cost communication protocol.
What do we mean by a “simple” auction? For example, recall the {\em simultaneous first-price auctions (S1As)} introduced in Section (ref) of the preceding lecture. Each player $i$ chooses a strategy $b_{i1},\ldots,b_{im}$, with one bid per item.\footnote{To keep the game finite, let's agree that each bid has to be an integer between 0 and some known upper bound $B$.} Each item is sold separately in parallel using a “first-price auction”---the item is awarded to the highest bidder on that item, with the selling price equal to that bidder's bid.\footnote{In the preceding lecture we mentioned the {\em Vickrey} or {\em second-price} auction, where the winner does not pay their own bid, but rather the highest bid by someone else (the second-highest overall). We'll stick with S1As for simplicity, but similar results are known for simultaneous second-price auctions, as well.} The payoff of a player $i$ in a given outcome (i.e., given a choice of strategy for each player) is then her utility: \[ \underbrace{v_i(T_i)}_{\text{value of items won}} - \underbrace{\sum_{j \in T_i} b_{ij}}_{\text{price paid for them}}, \] where $T_i$ denotes the items on which $i$ is the highest bidder (given the bids of the others).
Bidders strategize already in a first-price auction for a single item---a bidder certainly doesn't want to bid her actual valuation (this would guarantee utility 0), and instead will “shade” her bid down to a lower value. (How much to shade is a tricky question, and depends on what the other bidders are doing.) Thus it makes sense to assess the performance of an auction by its equilibria. As usual, a Nash equilibrium comprises a (randomized) strategy for each player, so that no player can unilaterally increase her expected payoff through a unilateral deviation to some other strategy (given how the other players are bidding).
So how good are the equilibria of various auction games, such as S1As? To answer this question, we use an analog of the approximation ratio, adapted for equilibria. Given a game $G$ (like an S1A) and a nonnegative maximization objective function $f$ on the outcomes (like the social welfare), KP99 defined the {\em price of anarchy (POA)} of $G$ as the ratio between the objective function value of an optimal solution, and that of the worst equilibrium: \[ \mathsf{PoA}(G):= \frac{f(OPT(G))}{\min_{\text{$\rho$ is an equilibrium of $G$}} f(\rho)}, \] where $OPT(G)$ denotes the optimal outcome of $G$ (with respect to $f$).\footnote{If $\rho$ is a probability distribution over outcomes, as in a mixed Nash equilibrium, then $f(\rho)$ denotes the expected value of $f$ w.r.t. $\rho$.} Thus the price of anarchy of a game quantifies the inefficiency of selfish behavior.\footnote{Games generally have multiple equilibria. Ideally, we'd like an approximation guarantee that applies to {\em all} equilibria, so that we don't need to worry about which one is reached---this is the point of the POA.} The POA of a game and a maximization objective function is always at least 1. We can identify “good performance” of a system with strategic participants as having a POA close to 1.\footnote{One caveat is that it's not always clear that a system will reach an equilibrium in a reasonable amount of time. A natural way to resolve this issue is to relax the notion of equilibrium enough so that it become relatively easy to reach an equilibrium. See Lunar Lecture 5 for more on this point.}
The POA depends on the choice of equilibrium concept. For example, the POA with respect to approximate Nash equilibria can only be worse (i.e., bigger) than for exact Nash equilibria (since there are only more of the former).
As we saw in Theorem (ref) of the preceding lecture, the equilibria of simple auctions like S1As can be surprisingly good.\footnote{The first result of this type, for simultaneous second-price auctions and bidders with submodular valuations, is due to CKS16.} We restate that result here.\footnote{For a proof, see the original paper FFGL13 or course notes by the author w14.}
This result is particularly impressive because achieving an approximation factor of 2 for the welfare-maximization problem with subadditive bidder valuations by any means (other than brute-force search) is not easy (see F06).
As mentioned last lecture, a recent result shows that the analysis of FFGL13 is tight.
The proof of Theorem (ref) is an ingenious explicit construction---the authors exhibit a choice of subadditive bidder valuations and a Nash equilibrium of the corresponding S1A so that the welfare of this equilibrium is only half of the maximum possible. One reason that proving results like Theorem (ref) is challenging is that it can be difficult to solve for a (bad) equilibrium of a complex game like a S1A.
Theorem (ref) motivates an obvious question: can we do better? Theorem (ref) implies that the analysis in FFGL13 cannot be improved, but can we reduce the POA by considering a different auction? Ideally, the auction would still be “reasonably simple” in some sense. Alternatively, perhaps no “simple” auction could be better than S1As? If this is the case, it's not clear how to prove it directly---proving lower bounds via explicit constructions auction-by-auction does not seem feasible.
Perhaps it's a clue that the POA upper bound of 2 for S1As (Theorem (ref)) gets stuck at the same threshold for which there is a lower bound for protocols that use polynomial communication (Theorem (ref)). It's not clear, however, that a lower bound for low-communication protocols has anything to do with equilibria. Can we extract a low-communication protocol from an equilibrium?
Theorem (ref) says that lower bounds for nondeterministic protocols carry over to all “sufficiently simple” auctions, where “simplicity” is measured by the number of strategies available to each player. These POA lower bounds follow automatically from communication complexity lower bounds, and do not require any new explicit constructions.
To get a feel for the simplicity constraint, note that S1As with integral bids between 0 and $B$ have $(B+1)^m$ strategies per player---singly exponential in $m$. On the other hand, in a “direct-revelation” auction, where each bidder is allowed to submit a bid on each bundle $S \subseteq M$ of items, each player has a doubly-exponential (in $m$) number of strategies.\footnote{Equilibria can achieve the optimal welfare in a direct-revelation auction, so some bound on the number of strategies is necessary in Theorem (ref).}
The POA lower bound promised by Theorem (ref) is only for approximate Nash equilibria; since the POA is a worst-case measure and the set of $\epsilon\text{-}\mathsf{NE}$ is nondecreasing with $\epsilon$, this is weaker than a lower bound for exact Nash equilibria. It is an open question whether or not Theorem (ref) holds also for the POA of exact Nash equilibria.\footnote{Arguably, Theorem (ref) is good enough for all practical purposes---a POA upper bound that holds for exact Nash equilibria and does not hold (at least approximately) for approximate Nash equilibria with very small $\epsilon$ is too brittle to be meaningful.}
Theorem (ref) has a number of interesting corollaries. First, consider the case where $\mathcal{V}$ is the set of subadditive valuations. Since S1As have only a singly-exponential (in $m$) number of strategies per player, Theorem (ref) applies to them. Thus, combining it with Theorem (ref) recovers the POA lower bound of Theorem (ref)---modulo the exact vs.\ approximate Nash equilibria issue---and shows the optimality of the upper bound in Theorem (ref) without an explicit construction. Even more interestingly, this POA lower bound of 2 applies not only to S1As, but more generally to all auctions in which each player has a sub-doubly-exponential number of strategies. Thus, S1As are in fact {\em optimal} among the class of all such auctions when bidders have subadditive valuations (w.r.t.\ the worst-case POA of $\epsilon$-approximate Nash equilibria).
We can also take $\mathcal{V}$ to be the set of all (monotone) valuations, and then combine Theorem (ref) with Theorem (ref) to deduce that no “simple” auction gives a non-trivial (i.e., better-than-$k$) approximation for general bidder valuations. We conclude that with general valuations, complexity is essential to any auction format that offers good equilibrium guarantees. This completes the proof of Theorem (ref) from the preceding lecture and formalizes the second folklore belief in Section (ref); we restate that result here.
Presumably, the proof of Theorem (ref) extracts a low-communication protocol from a good POA bound. The hypothesis of Theorem (ref) offers the clue that we should be looking to construct a nondeterministic protocol. So what could we use an all-powerful prover for? We'll see that a good role for the prover is to suggest a Nash equilibrium to the players.
Unfortunately, it can be too expensive for the prover to write down the description of a Nash equilibrium, even in S1As. Recall that a mixed strategy is a distribution over pure strategies, and that each player has an exponential (in $m$) number of pure strategies available in a S1A. Specifying a Nash equilibrium thus requires an exponential number of probabilities. To circumvent this issue, we resort to approximate Nash equilibria, which are guaranteed to exist even if we restrict ourselves to distributions with small descriptions. We proved this for two-player games in Solar Lecture 1 (Theorem (ref)); the same argument works for games with any number of players.
In particular, every game with a sub-doubly-exponential number of strategies admits an approximate Nash equilibrium with subexponential description length.
We now proceed to the proof of Theorem (ref).
Conceptually, the proof of Theorem (ref) argues that, when the POA of $\epsilon$-approximate Nash equilibria is small, every $\epsilon$-approximate Nash equilibrium provides a privately verifiable proof of a good upper bound on the maximum-possible welfare. When such upper bounds require large communication, the equilibrium description length (and hence the number of available strategies) must be large.
While Theorems (ref), (ref), and (ref) pin down the best-possible POA achievable by simple auctions with subadditive bidder valuations, open questions remain for other valuation classes. For example, a valuation $v_i$ is {\em submodular} if it satisfies \[ v_i(T \cup \{j\}) - v_i(T) \le v_i(S \cup \{j\}) - v_i(S) \] for every $S \subseteq T \subset M$ and $j \notin T$. This is a “diminishing returns” condition for set functions. Every monotone submodular function is also subadditive, so welfare-maximization with the former valuations is only easier than with the latter.
The worst-case POA of S1As is exactly $\tfrac{e}{e-1} \approx 1.58$ when bidders have submodular valuations. The upper bound was proved by ST13, the lower bound by CKST16. It is an open question whether or not there is a simple auction with a smaller worst-case POA. The best lower bound known---for nondeterministic protocols and hence, by Theorem (ref), for the POA of $\epsilon$-approximate Nash equilibria of simple auctions---is $\tfrac{2e}{2e-1} \approx 1.23$ DV13. Intriguingly, there is an upper bound (very slightly) better than $\tfrac{e}{e-1}$ for polynomial-communication protocols FV06---can this better upper bound also be realized as the POA of a simple auction? What is the best-possible approximation guarantee, either for polynomial-communication protocols or for the POA of simple auctions? Resolving this question would require either a novel auction format (better than S1As), a novel lower bound technique (better than Theorem (ref)), or both.