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

References

• Papadimitriou, Christos (1994). "On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence". Journal of Computer and System Sciences. 48 (3): 498–532. doi:10.1016/S0022-0000(05)80063-7. Paper available online at Papadimitriou's Homepage.

• 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 10.1.1.68.6111. doi:10.1137/070699652.

• Xi Chen and Xiaotie Deng (2006). Settling the complexity of two-player Nash equilibrium. pp. 261–272. {{cite book}}: Unknown parameter |booktitle= ignored (help)