Scarf's lemma is one of the fundamental results in combinatorics, originally introduced to study the core of an N-person game. Over the last four decades, the usefulness of Scarf's lemma has been demonstrated in several important combinatorial problems seeking "stable" solutions. However, the complexity of the computational version of Scarf's lemma (SCARF) remained open. In this paper, we prove that SCARF is complete for the complexity class PPAD. This proves that SCARF is as hard as the computational versions of Brouwer's fixed point theorem and Sperner's lemma. Hence, there is no polynomial-time algorithm for SCARF unless PPAD P. We also show that fractional stable paths problem and finding strong fractional kernels in digraphs are PPAD-hard.
@cite_18: We prove that computing a Nash equilibrium in a 3-player game is PPAD-complete, solving a problem left open in (2).
@cite_4: We advance significantly beyond the recent progress on the algorithmic complexity of Nash equilibria by solving two major open problems in the approximation of Nash equilibria and in the smoothed analysis of algorithms. --We show that no algorithm with complexity poly(n, 1 ) can compute an -approximate Nash equilibrium in a two-player game, in which each player has n pure strategies, unless PPAD P. In other words, the problem of computing a Nash equilibrium in a twoplayer game does not have a fully polynomial-time approximation scheme unless PPAD P. --We prove that no algorithm for computing a Nash equilibrium in a two-player game can have smoothed complexity poly(n, 1 ) under input perturbation of magnitude s, unless PPAD RP. In particular, the smoothed complexity of the classic Lemke-Howson algorithm is not polynomial unless PPAD RP. Instrumental to our proof, we introduce a new discrete fixed-point problem on a high-dimensional hypergrid with constant side-length, and show that it can host the embedding of the proof structure of any PPAD problem. We prove a key geometric lemma for finding a discrete fixed-point, a new concept defined on n + 1 vertices of a unit hypercube. This lemma enables us to overcome the curse of dimensionality in reasoning about fixed-points in high dimensions.
@cite_22: Abstract Nondeterministic multivalued functions with values that are polynomially verifiable and guaranteed to exist form an interesting complexity class between P and NP. We show that this class, which we call TFNP, contains a host of important problems, whose membership in P is currently not known. These include, besides factoring, local optimization, Brouwer's fixed points, a computational version of Sperner's Lemma, bimatrix equilibria in games, and linear complementarity for P -matrices.
@cite_6: We resolve the question of the complexity of Nash equilibrium by showing that the problem of computing a Nash equilibrium in a game with 4 or more players is complete for the complexity class PPAD. Our proof uses ideas from the recently-established equivalence between polynomial time solvability of normal form games and graphical games, establishing that these kinds of games can simulate a PPAD-complete class of Brouwer functions.
@cite_3: 
@cite_19: Even though many people thought the problem of finding Nash equilibria is hard in general, and it has been proven so for games among three or more players recently, it's not clear whether the two-player case can be shown in the same class of PPAD-complete problems. We prove that the problem of finding a Nash equilibrium in a two-player game is PPAD-complete
@cite_2: 
Daskalakis, Goldberg and Papadimitriou @cite_6 proved that 3-Dimensional Brouwer is PPAD-complete. They reduced 3-dimensional Brouwer to 3-Graphical Nash to prove that 3-Graphical Nash is PPAD-complete. These results together with the reductions of Goldberg and Papadimitriou @cite_2 imply that computing Nash equilibrium in games with 4 players ( 4-Nash ) is PPAD-complete. Chen and Deng @cite_22 , Daskalakis and Papadimitriou @cite_18 independently proved that 3-Nash is PPAD-complete. Chen and Deng @cite_19 proved that 2-Nash is also PPAD-complete. Chen, Deng and Teng @cite_4 showed that approximating Nash equilibrium is also hard. For a list results on the complexity of finding equilibria we refer the reader to a recent book on algorithmic game theory @cite_3 .