PPAD (complexity)

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 every vertex having at most one predecessor and at most 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.)

Proving membership in PPAD

In many cases, when a problem is said to "be in PPAD", it often means that finding an approximate solution to the problem is in PPAD. This is often necessary, as in many cases, the solutions might involve irrational numbers, and thus cannot be output in finite time. ^[5]

However, there are cases in which solutions with rational numbers are guaranteed to exist. For such cases, Filos-Ratsikas, Hansen, Høgh and Hollender ^[5] present a general method for proving that computing an exact solution belongs to PPAD.

Relations 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. ^[6]

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. ^[7] 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. ^[8] Examples of PPAD-complete problems include finding Nash equilibria, computing fixed points in Brouwer functions, and finding Arrow-Debreu equilibria in markets. ^[9]

Fearnley, Goldberg, Hollender and Savani ^[10] proved that a complexity class called CLS is equal to the intersection of PPAD and PLS.

Etessami and Yannakakis (who invented the related class FIXP) ^[11] write that "The piecewise-linear fragment of FIXP equals PPAD". In other words, ^[12] the problems in PPAD are the problems in FIXP in which the input function is piecewise-linear.

Further reading

• Equilibria, fixed points, and complexity classes: a survey. ^[13]

Other notable complete problems

Main article: List of PPAD-complete problems

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

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

References

1. 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.
2. Fortnow, Lance (2005). "What is PPAD?" . Retrieved 2007-01-29.
3. • 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..
4. 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. CiteSeerX   10.1.1.152.7003 . doi:10.1137/070699652. ISSN   0097-5397.
5. Filos-Ratsikas, Aris; Hansen, Kristoffer Arnsfelt; Høgh, Kasper; Hollender, Alexandros (2023-12-02), PPAD-membership for Problems with Exact Rational Solutions: A General Approach via Convex Optimization, arXiv, doi:10.48550/arXiv.2312.01237, arXiv:2312.01237, retrieved 2025-08-16
6. 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. S2CID   2056144.
7. Scott Aaronson (2011). "Why philosophers should care about computational complexity". arXiv: 1108.1791 [cs.CC].
8. Christos Papadimitriou (2011). "Lecture: Complexity of Finding a Nash Equilibrium" (PDF).
9. 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.
10. Fearnley, John; Goldberg, Paul; Hollender, Alexandros; Savani, Rahul (2022-12-19). "The Complexity of Gradient Descent: CLS = PPAD ∩ PLS". Journal of the ACM. 70 (1): 7:1–7:74. arXiv: 2011.01929 . doi:10.1145/3568163. ISSN   0004-5411. S2CID   263706261.
11. Etessami, Kousha; Yannakakis, Mihalis (January 2010). "On the Complexity of Nash Equilibria and Other Fixed Points". SIAM Journal on Computing. 39 (6): 2531–2597. doi:10.1137/080720826. ISSN   0097-5397.
12. Fearnley, John; Goldberg, Paul; Hollender, Alexandros; Savani, Rahul (2022-12-19). "The Complexity of Gradient Descent: CLS = PPAD ∩ PLS". Journal of the ACM. 70 (1): 7:1–7:74. arXiv: 2011.01929 . doi:10.1145/3568163. ISSN   0004-5411. S2CID   263706261.
13. Yannakakis, Mihalis (2009-05-01). "Equilibria, fixed points, and complexity classes". Computer Science Review. 3 (2): 71–85. arXiv: 0802.2831 . doi:10.1016/j.cosrev.2009.03.004. ISSN   1574-0137.
14. 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.
15. 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. S2CID   4430655.