In this paper, Chen and Deng proved that, given payoff matrix, finding 2-player Nash Equilibrium is PPAD-Complete. So what is PPAD?

Let’s first start on TFNP (Total Functions in NP) . A polynomial time predicate function is that for every , there exists at least one that makes latex true. A TFNP is the problem that given an input , find a making true.

One subproblem class of TFNP is PPA where it ensures the existence of a . Formally, there is a lemma PPA (Polynomial Parity Argument) says that all graphs of maximum degree 2 have even number of leaves. Then given a leaf, you want to search another leaf.

PPAD is the problem defined on directed graphs where vertex has at most one incoming edge and and one outcoming edge. Formally, given an exponential-sized graph, where for each vertex , a polynomial-time computable function can give its successor (outcoming edge) and predecessor (incoming edge); and there exists a vertex in this graph that only has successor. The problem here is to find a s.t. vertex has no successor or predecessor.