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.
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
