List of PPAD-complete problems
This is a list of PPAD-complete problems.
Fixed Point Theorems
Game Theory and Nash Equilibrium
- 3-Graphical Nash
- 4-Nash
- 3-Nash
- 2-Nash
- 2-Player win-lose games
Economics and Market Equilibria
- Exchange Economy
- Leontief exchange economy
- Arrow-Debreu Equilibria
Scarf's Lemma and Fractional Stability
- Scarf's Lemma
- Core of Balanced Games
- Fractional Stable Paths Problems
- Hypergraph matching
- Strong Fractional Kernel
- Preference Games
Miscellaneous
- Personalized Equilibria
- 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. doi:10.1137/070699652.
- Xi Chen and Xiaotie Deng (2006). Settling the complexity of two-player Nash equilibrium. pp. 261–272.
External links
This article is issued from Wikipedia - version of the 9/22/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.