In computer science, PPAD 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. 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.
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: 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 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. In particular, given s, we can find such a t at the other end of the string starting at s.
PPAD is contained in PPA which is contained in TFNP. PPAD is also contained in PPP, another subclass of TFNP. It contains . 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. However, PPAD and NP are closely related. While the questionwhether 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. It could still be the case that PPAD is the same class as FP, and still have that P ≠ NP, though it seems unlikely. Examples of PPAD-complete problems include finding Nash equilibria, computing fixed points in Brouwer functions, finding Arrow-Debreu equilibria in markets.
