List of PPAD-complete problems

This is a list of PPAD-complete problems.

Fixed-point theorems

• Sperner's lemma
• Brouwer fixed-point theorem
• Kakutani fixed-point theorem

Game theory

• Nash equilibrium
• Core of Balanced Games

Equilibria in game theory and economics

• Fisher market equilibria
• Arrow-Debreu equilibria
• Approximate Competitive Equilibrium from Equal Incomes
• Finding clearing payments in financial networks

Graph theory

• Fractional stable paths problems
• Fractional hypergraph matching (see also the NP-complete Hypergraph matching)
• Fractional strong kernel

Miscellaneous

• Scarf's lemma
• Fractional bounded budget connection games

• Papadimitriou, Christos (1994). . Journal of Computer and System Sciences. 48 (3): 498–532. CiteSeerX . doi:. Paper available online at .
• 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 . doi:.
• Xi Chen; Xiaotie Deng (2006). "Settling the complexity of two-player Nash equilibrium". Proc. 47th FOCS. pp. 261–272.