Lecture 19

PPAD-hardness of Nash equilibrium

We continue the discussion from Lecture 18, “Total search and TFNP” by giving a glimpse of how the PPAD-hardness of finding \(\epsilon\)-approximate Nash equilibria was shown by Daskalakis, Goldberg and Papadimitriou [DGP09[DGP09] Daskalakis, C., Goldberg, P. W., & Papadimitriou, C. H. (2009). The Complexity of Computing a Nash Equilibrium. SIAM Journal on Computing, 39(1), 195–259. link].

The proof can be broken down into two main steps:

• Reduction from End-of-Line (Section L18.3) to (approximate) Brouwer.
• Reduction from (approximate) Brouwer to (approximate) Nash equilibria.

The first step requires a carefully encoded path and interpolation construction; we will not cover it here. The second step is more involved and requires a careful construction of a reduction from Brouwer to Nash equilibria. This is the part we will focus on in this lecture.

The key idea is the following: in the reduction from End-of-the-line to Brouwer, we define a continuous function \(f\) for which we need to find an approximate fixed point. We now need to construct a game such that every sufficiently accurate approximate Nash equilibrium can be decoded into an approximate fixed point of \(f\). The issue is that it is not clear how we can have games “compute” functions. Can we construct games in such a way that their behavior at Nash equilibria can be seen as “computing something”? The answer is positive, as we see next.

L19.1 Generalized circuits and approximation

We show that given a function represented as an arithmetic circuit, it is possible to construct a game whose Nash equilibria correspond to computing a fixed point of the function. This is the key idea behind the reduction from Brouwer to Nash equilibria.

In particular, we will restrict our attention to functions constructed through circuits that are composed of the following:

• Variable nodes \(v_{1}, \dots , v_{n}\);
• Gate nodes \(g_{1}, \dots , g_{m}\) of six possible types:

  Gate	Symbol	Input-output relationship
  Assignment		\(y = x_{1}\)
  Constant		\(y=a\)
  Addition		\(y=\operatorname*{min}\{1, x_{1}+x_{2}\}\)
  Subtraction		\(y=\operatorname*{max}\{0, x_{1}-x_{2}\}\)
  Scaling		\(y=\operatorname*{max}\{0,\operatorname*{min}\{1, a ⋅ x_{1}\}\}\)
  Comparison		\(y=\begin{cases}1, \quad \quad & \text{if } x_{1} > x_{2} \\ 0, & \text{if } x_{1}<x_{2} \\ \text{any}, & \text{if } x_{1} = x_{2}.\end{cases}\) When the inputs are equal, this gate does not restrict the output.

• Each constant \(a\) is rational and lies in \([0,1]\). Scaling multiplies by this constant; multiplication of two variable inputs is not one of the permitted gates.
• Directed edges connecting variables to gates and gates to variables (loops are allowed);
• Variable nodes have in-degree 1; gates have 0, 1, or 2 inputs depending on type as above; gates & nodes have arbitrary fanout.

The table gives ideal gate relations. To state a finite search problem appropriate for approximate Nash, fix a rational tolerance \(\delta \in (0,\frac{1}{4})\).

The restriction to rational-constant scaling matters. Allowing arbitrary variable multiplication changes the exact fixed-point problem to an algebraic one; exact multiplayer Nash is associated with FIXP [EY10[EY10] Etessami, K., & Yannakakis, M. (2010). On the Complexity of Nash Equilibria and Other Fixed Points. SIAM Journal on Computing, 39(6), 2531–2597. link]. The statement above explicitly concerns approximate solutions.

L19.2 From gates to games

It is possible to convert an approximate generalized-circuit instance into an approximate Nash equilibrium computation problem in a multiplayer game. (The game can also be converted into a two-player [CDT09] or three-player game [DGP09], but we do not show how in this lecture).

The idea is to use gadgets: constructions that simulate the behavior of the gates in the circuit. We first prove their exact equilibrium behavior to expose the mechanism. A full approximation reduction must also bound the error of each gadget, normalize payoffs, and choose the Nash tolerance as a function of the circuit tolerance.

L19.2.1 Addition gate

Consider any game that contains the following interaction between four players \(x, y, z, w\), each of which has two actions, denoted \(\{0,1\}\). With a slight abuse of notation, we will call \(x,y,z,w\) the probability of playing action \(1\); hence, \(x, y, z, w \in [0,1].\)

L19.2.2 Comparison gate

For input players with action-\(1\) probabilities \(x,y\), give an output player \(z\) payoff equal to the input action of \(x\) when she plays \(1\), and equal to the input action of \(y\) when she plays \(0\). Her expected payoff difference between the two actions is \(x-y\). Therefore, in an exact equilibrium, \(z=1\) if \(x>y\), \(z=0\) if \(x<y\), and any mixture is allowed at a tie.

This also illustrates why approximate comparisons need a gap. In an \(\epsilon\)-Nash equilibrium, if \(x-y>\delta\), then playing action \(0\) with probability \(1-z\) incurs deviation gain \((1-z)(x-y)\), so \(1-z \le \frac{\epsilon}{\delta}\). Taking \(\epsilon \le \delta^{2}\) enforces \(z \ge 1-\delta\). The case \(y-x>\delta\) is symmetric.

These local arguments explain the gate simulation. They do not by themselves prove the full hardness theorem: composing all gadgets while preserving their incentives, controlling approximation errors, and converting the graphical construction to a fixed number of players require the remaining reductions in the cited papers.