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 $\varepsilon$-approximate 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 (implicitly represented) graph, $[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 what the “implicitly represented” means. Essentially, the challenge is

  • Start at the first node,
  • Query two circuits to find the predecessor and successor nodes, respectively.
  • Move to one or the other node.

This basically only gives us very local information about the graph at each step. In the worst case, we have to go through all possible nodes.

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 by querying the circuits at each node.

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 have to search an exponentially large space.

Approximability and PPAD

In fact, let’s take a close look at the search problem for 2-player general-sum games. Take the exact version of the Bimatrix problem:

  • Input: Two $n \times n$ matrices $B_1, B_2$.
  • Output: A Nash Equilibrium of this game.

[1] shows that this problem is PPAD-complete. Since we believe taht PPAD $\neq$ P, this means that there is no polynomial time algorithm that outputs an exact Nash Equilibrium of a Bimatrix game in polynomial time. [1] also considers the approximation version of this problem, namely:

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

[1] shows that (among other things) that Poly-Bimatrix is PPAD-Complete as well! In other words, there’s is no polynomial-time algorithm that outputs an $n^{-c}$-NE of a Bimatrix game, for any choice of $c$.

Well, the interesting part of this post is that

  • The PPAD-Hardness of Bimatrix shows the difficulty of finding exact Nash Equilibria in Bimatrix games.
  • The PPAD-Hardness of Poly-Bimatrix shows the difficulty of finding approximate Nash Equilibria in Bimatrix games.

In particular, the latter hardnesss result rules out the existence of Fully Polynomial Time Approximation Schemes (FPTASes) for Bimatrix games.

An FPTAS 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$.

Conclusions

Most of this being theory, I only recently realised the connection between Poly-Bimatrix, PPAD and FPTAS. Complexity theory gets wild from here on out, so let’s save that for later.

  • [EDIT, 14 March 2026] [1] explicitly state that their results rule out the existence of an FPTAS for Poly-BIMATRIX, and in particular, for any PPAD-Complete problem.
  • [EDIT, 25 April 2026] [7] also prove that this inapproximability is preserved when searching for $\varepsilon$-NE, even for a (sufficiently small) constant $\varepsilon$. Technically, this rules out the existence of a Polynomial Time Approximation Scheme (PTAS) for approximate NE. The short version is that a PTAS produces an $\varepsilon$ solution in $\mathcal{O}(poly(\Gamma))$ time - note the missing dependence on $\frac{1}{\varepsilon}$.
  • [EDIT, 12 May 2026] Corrected a huge misunderstanding of the results. PPAD is not inherently an inapproximable class; the hardness of the approximation problem, Poly-Bimatrix, is the key here!

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.
  7. Rubinstein, Aviad. “Settling the complexity of computing approximate two-player Nash equilibria.” ACM SIGecom Exchanges 15.2 (2017): 45-49.