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

Topology

• Tucker's Lemma
• Borsuk–Ulam theorem

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

Approximate Versions

No FPTAS exists for the following problems unless PPAD is in FP.

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.

• Papadimitriou, Christos (2009). "The Complexity of Computing a Nash Equilibrium". SIAM J. Comput. 39 (3): 195–532. doi:10.1137/070699652. 

• Xi Chen and Xiaotie Deng (2006). Settling the complexity of two-player Nash equilibrium. pp. 261--272. 

External links

• Compendium of PPAD-complete Problems