In computer science, PPAD ("Polynomial Parity Arguments on Directed graphs") is a complexity class introduced by Christos Papadimitriou in 1994.
[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.
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: Such a t must exist if an s does, because the structure of G means that vertices with only one neighbour come in pairs.
[8] Fearnley, Goldberg, Hollender and Savani[9] proved that a complexity class called CLS is equal to the intersection of PPAD and PLS.