In computer science, **PPAD** ("Polynomial Parity Arguments on Directed graphs") is a complexity class introduced by Christos Papadimitriou in 1994. PPAD is a subclass of TFNP based on functions that can be shown to be total by a parity argument.^{[1]}^{[2]} The class attracted significant attention in the field of algorithmic game theory because it contains the problem of computing a Nash equilibrium: this problem was shown to be complete for PPAD by Daskalakis, Goldberg and Papadimitriou with at least 3 players and later extended by Chen and Deng to 2 players.^{[3]}^{[4]}

## Definition

PPAD is a subset of the class TFNP, the class of function problems in FNP that are guaranteed to be total. The TFNP formal definition is given as follows:

- A binary relation P(
*x*,*y*) is in TFNP if and only if there is a deterministic polynomial time algorithm that can determine whether P(*x*,*y*) holds given both*x*and*y*, and for every*x*, there exists a*y*such that P(*x*,*y*) holds.

Subclasses of TFNP are defined based on the type of mathematical proof used to prove that a solution always exists. Informally, PPAD is the subclass of TFNP where the guarantee that there exists a *y* such that P(*x*,*y*) holds is based on a parity argument on a directed graph. The class is formally defined by specifying one of its complete problems, known as *End-Of-The-Line*:

- G is a (possibly exponentially large) directed graph with no isolated vertices, and with every vertex having at most one predecessor and one successor. G is specified by giving a polynomial-time computable function f(
*v*) (polynomial in the size of*v*) that returns the predecessor and successor (if they exist) of the vertex*v*. Given a vertex*s*in G with no predecessor, find a vertex*t≠s*with no predecessor or no successor. (The input to the problem is the source vertex*s*and the function f(*v*)). In other words, we want any source or sink of the directed graph other than*s*.

Such a *t* must exist if an *s* does, because the structure of G means that vertices with only one neighbour come in pairs. In particular, given *s*, we can find such a *t* at the other end of the string starting at *s*. (Note that this may take exponential time if we just evaluate f repeatedly.)

## Relationship to other complexity classes

PPAD is contained in (but not known to be equal to) PPA (the corresponding class of parity arguments for *undirected* graphs) which is contained in TFNP. PPAD is also contained in (but not known to be equal to) PPP, another subclass of TFNP. It contains CLS.^{[5]}

PPAD is a class of problems that are believed to be hard, but obtaining PPAD-completeness is a weaker evidence of intractability than that of obtaining NP-completeness. PPAD problems cannot be NP-complete, for the technical reason that NP is a class of decision problems, but the answer of PPAD problems is always yes, as a solution is known to exist, even though it might be hard to find that solution.^{[6]} However, PPAD and NP are closely related. While the question whether a Nash equilibrium exists for a given game cannot be NP-hard because the answer is always yes, the question whether a *second* equilibrium exists is NP complete.^{[7]} It could still be the case that PPAD is the same class as FP, and still have that P ≠ NP, though it seems unlikely.^{[citation needed]} Examples of PPAD-complete problems include finding Nash equilibria, computing fixed points in Brouwer functions, and finding Arrow-Debreu equilibria in markets.^{[8]}

## Other notable complete problems

- Finding the Nash equilibrium on a 2-player game
^{[3]}or the Epsilon-equilibrium on a game with any number of players.^{[8]}

- Finding a three-colored point in Sperner's Lemma.
^{[9]} - Finding an envy-free cake-cutting when the utility functions are given by polynomial-time algorithms.
^{[10]}

## References

**^**Christos Papadimitriou (1994). "On the complexity of the parity argument and other inefficient proofs of existence" (PDF).*Journal of Computer and System Sciences*.**48**(3): 498–532. doi:10.1016/S0022-0000(05)80063-7. Archived from the original (PDF) on 2016-03-04. Retrieved 2008-03-08.**^**Fortnow, Lance (2005). "What is PPAD?". Retrieved 2007-01-29.- ^
^{a}^{b}*Chen, Xi; Deng, Xiaotie (2006).*Settling the complexity of two-player Nash equilibrium*. Proc. 47th Symp. Foundations of Computer Science. pp. 261–271. doi:10.1109/FOCS.2006.69. ECCC TR05-140.. **^**Daskalakis, Constantinos.; Goldberg, Paul W.; Papadimitriou, Christos H. (2009-01-01). "The Complexity of Computing a Nash Equilibrium".*SIAM Journal on Computing*.**39**(1): 195–259. doi:10.1137/070699652. ISSN 0097-5397.**^**Daskalakis, C.; Papadimitriou, C. (2011-01-23).*Continuous Local Search*. Proceedings. Society for Industrial and Applied Mathematics. pp. 790–804. CiteSeerX 10.1.1.362.9554. doi:10.1137/1.9781611973082.62. ISBN 9780898719932.**^**Scott Aaronson (2011). "Why philosophers should care about computational complexity". arXiv:1108.1791 [cs.CC].**^**Christos Papadimitriou (2011). "Lecture: Complexity of Finding a Nash Equilibrium" (PDF).- ^
^{a}^{b}C. Daskalakis, P.W. Goldberg and C.H. Papadimitriou (2009). "The Complexity of Computing a Nash Equilibrium".*SIAM Journal on Computing*.**39**(3): 195–259. CiteSeerX 10.1.1.152.7003. doi:10.1137/070699652. **^**Xi Chen and Xiaotie Deng (2006). "On the Complexity of 2D Discrete Fixed Point Problem".*International Colloquium on Automata, Languages and Programming*. pp. 489–500. ECCC TR06-037.**^**Deng, X.; Qi, Q.; Saberi, A. (2012). "Algorithmic Solutions for Envy-Free Cake Cutting".*Operations Research*.**60**(6): 1461. doi:10.1287/opre.1120.1116.