It’s been a while coming, but this is my first post related to my thesis, and it’s on the famous PPAD complexity class. It’s a curious complexity class, and it characterises the hardness of finding Nash Equilibria in games. In fact, you can say many statements of the form:

Finding an $\epsilon$-Nash Equilibrium in a “game” is PPAD-Complete, where “game” can be:

  1. a 2-player, general-sum normal form game [1].
  2. a general-sum stochastic game [2], played over an infinite horizon.

where $\epsilon$ is some parameter that can depend on polynomial factors of the game, like the number of actions, players etc.

Just to be on the same page, an Nash Equilibrium is defined as follows.

Given an (finite) normal-form game $ \Gamma = \langle N, A, (r_i){i \in N} \rangle $, a joint strategy $x = (x_i}{i \in N}$ is called a $\epsilon$-Nash Equilibrium when

\[\begin{align} \max_{x'_i} r_i(x'_i, x_{-i}) - r(x) \leq \epsilon \end{align}\]

i.e. no player can improve (by unilaterally deviating) his/her utility more than $\epsilon$.

A reasonable, dare I say, rational thing to do in some situtations - if everyone is doing something, and you can’t improve your lot more than it’s worth, why bother changing ? Here’s the kicker:

A Nash Equilibrium (in mixed strategies) is guaranteed to exist

  1. for finite games i.e. for normal-form games with finite action spaces (think actions $1,2,\ldots,n$ for a finite number of players)[4]
  2. for finite-action stochastic games, in stationary strategies for the infinite horizon game [5]
  3. and in non-stationary strategies for the finite horizon stachastic game (See Farina).

Why PPAD ?

Why can’t we be happy with classical NP-hardness/completeness ? Why invent a completely new acronym ? Well, firstly, it’s easy to verify that a given strategy $x$ is an $\epsilon$-NE: it’s just solving (for example, for the $i^{th}$ player),

\[\begin{align} \max_{x'_i} r_i(x'_i,x_{-i}) - r_i(x) \leq \epsilon \iff \max_{a_i} r_i(a_i,x_{-i}) - r_i(x) \leq \epsilon \end{align}\]

In other words, we can iterate over the payoffs over the pure actions since the mixed strategy utility is just a convex combination of the best pure payoffs. This clearly has linear complexity in the action space $\mathcal{O}(\sum_i | A_i |)$, making this an easy-to-verify problem i.e. it is in NP. Hardness, however, is a different thing entirely. In particular, since we know an NE always exists, the decision problem “Does there exist an NE” is trivially satisified all the time. However, finding said equilibrium is the problem. Clearly, NP as a class isn’t capturing the difficulty of the search problem !

To use some techical jargon, we say that the search problem is “total” and so PPAD falls under the TFNP complexity class, since the solution is guaranteed to exist (although don’t quiz me too much on this).

So what is PPAD ?

PPAD is a complexity class whose original “Complete” problem is called End-of-the-Line. Roughly speaking (Refer [3]), End-of-the-Line can be given as the following search problem:

  • Input: an exponentially large set of nodes, $[2^n]$, each with in-degree and out-degree at most 1. The first node is guaranteed to be a source i.e. in-degree = 0.
  • Output: Find a sink of this graph i.e. a node with out-degree=0, or any other source.

Sounds easy, doesn’t it ? That’s until you realise that in the worst case, we have to go through all possible nodes. There is no nice edge structure, in the general case, that allows us to simplify the search. Otherwise stated, the edges of this exponentially large graph can be randomly ordered. For example, take the path graph $1 \rightarrow 2 \rightarrow \cdots \rightarrow 2^n$. Unless you already know this is the path graph, we have to go through each one.

The analogy with a game is that in games, in the worst case, we have to search through all possible combinations of actions to find an Equilibrium. (Technically, EoL captures the difficulty the Lemke-Howson algorithm has in finding NE, so the analogy isn’t perfect, but let’s not go there today).

PPAD is supposedly difficult

We think PPAD is a difficult class to solve, since (See [6])

  • finding a second Nash equilibrium in a game is NP-Complete, even in 2-player games
  • finding an NE that maximises social welfare is NP-Hard.
  • finding an NE that guarantees a minimum payoff for each player is also NP-hard.

and so on. The analogy is that in all of these cases, NE + (second property) removes the existence guarantee of Nash, which only guarantees the first NE (in mixed strategies). Once that’s out of the way, it becomes more clear that we can only search an exponentially large space.

Approximability

In fact, let’s take a close look at the search problem for 2-player general-sum games.

  • Input: Two $n \times n$ matrices $B_1, B_2$, and some constant $c$.
  • Output: An $n^{-c}$-Nash Equilibrium of this game.

Well, the interesting part of this post is that this problem rules out the existence of Fully Polynomial Time Approximation Schemes (FPTASes) for PPAD-Complete problems (modulo a miracle). An FPTAS for a problem is an algorithm that

  • takes an instance $\Gamma$ and a precision $\epsilon$,
  • returns an $\epsilon$-approximate solution
  • and its runtime is polynomial in the instance parameters $\mathrm{poly}(\Gamma)$ and in $1\epsilon$.

So for example, an FPTAS might have $\mathcal{O}(1/\epsilon^4)$ runtime in the precision. So, suppose that you do in fact have an FPTAS for a PPAD-complete problem, say Poly-Bimatrix. Then, I can choose for all instances of Poly-Bimatrix some $\epsilon < n^{-c}$, and solve it, in polynomial time. So, for any constant $\varepsilon$ that you can choose, I can produce a polytime algorithm to solve the associated search problem.

Since Poly-Bimatrix is PPAD-Complete, we’ve just shown that all PPAD-Complete/Hard problems can be solved in polynomial time. This is widely believed not to be possible, since we think that PPAD is a “difficult” class.

Isn’t that neat ?

Conclusions

Most of this being theory, I only recently realised the connection between Poly-Bimatrix, PPAD and FPTAS. For example, subclasses of PPAD like CLS can have an FPTAS, but PPAD itself cannot. Complexity theory gets wild from here on out, so let’s save that for later.

References

  1. Chen, Xi, and Xiaotie Deng. “Settling the Complexity of Two-Player Nash Equilibrium.” FOCS. Vol. 6. 2006.
  2. Deng, Xiaotie, et al. “On the complexity of computing markov perfect equilibrium in general-sum stochastic games.” National Science Review 10.1 (2023): nwac256.
  3. Fearnley, John, et al. “The complexity of gradient descent: CLS= PPAD∩ PLS.” Journal of the ACM 70.1 (2022): 1-74.
  4. Nash Jr, John F. “Equilibrium points in n-person games.” Proceedings of the national academy of sciences 36.1 (1950): 48-49.
  5. Fink, Arlington M. “Equilibrium in a stochastic $ n $-person game.” Journal of science of the hiroshima university, series ai (mathematics) 28.1 (1964): 89-93.
  6. Conitzer, Vincent, and Tuomas Sandholm. “New complexity results about Nash equilibria.” Games and Economic Behavior 63.2 (2008): 621-641.