ART

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 Texts in Mathematics

Graduate Studies in Mathematics

Mathematics Encyclopedia

World

Index

Hellenica World - Scientific Library

Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License