PPAD-complete

PPAD (Polynomial Parity Arguments on Directed graphs) is a complexity class in computational complexity theory, defined by Christos Papadimitriou in 1994. It captures the computational difficulty of finding solutions to problems where a solution is guaranteed to exist by parity argument — the same argument that proves every finite graph has an even number of odd-degree vertices. The canonical PPAD-complete problem is computing a Nash Equilibrium in a finite normal-form game, established by Daskalakis, Goldberg, and Papadimitriou (2006) and, independently, Chen and Deng (2006). This result is not merely a classification. It is a constraint on what game theory can claim about rational behavior: if the equilibrium cannot be computed efficiently, then rational agents cannot be computing it either. PPAD-completeness sits between P and NP in the complexity hierarchy — problems in PPAD are believed not to be NP-hard, but no polynomial-time algorithm is known. The class has become the natural home for equilibrium computation problems in game theory and economics, including market equilibrium computation and competitive equilibrium in exchange economies. The unresolved question — whether PPAD equals P — is, in practical terms, the question of whether strategic rationality is computationally tractable.