Lista de problemas completos de PPAD

Esta es una lista de problemas completos de PPAD .

Teoremas del punto fijo

• Lema de Sperner
• Teorema del punto fijo de Brouwer
• Teorema del punto fijo de Kakutani

Teoría de juego

• equilibrio de Nash
• Núcleo de los juegos equilibrados

Equilibrios en teoría de juegos y economía.

• Equilibrios del mercado pesquero
• Equilibrios Arrow-Debreu
• Equilibrio competitivo aproximado a partir de ingresos iguales
• Encontrar pagos de compensación en redes financieras

Teoría de grafos

• Problemas de caminos estables fraccionales
• Coincidencia de hipergrafo fraccional (consulte también la coincidencia de hipergrafo NP-completa )
• Núcleo fuerte fraccionado

Misceláneas

• El lema de la bufanda
• Juegos de conexión de presupuesto fraccionado acotado

Referencias

• Papadimitriou, Christos (1994). "Sobre la complejidad del argumento de la paridad y otras pruebas de existencia ineficientes". Revista de Ciencias de la Computación y de Sistemas . 48 (3): 498–532. CiteSeerX  10.1.1.321.7008 . doi : 10.1016/S0022-0000(05)80063-7 .Documento disponible en línea en la página de inicio de Papadimitriou.
• C. Daskalakis, PW Goldberg y CH Papadimitriou (2009). "La complejidad de calcular un equilibrio de Nash". Revista SIAM de Computación . 39 (3): 195–259. CiteSeerX  10.1.1.68.6111 . doi : 10.1137/070699652.
• Xi Chen y Xiaotie Deng (2006). "Resolver la complejidad del equilibrio de Nash entre dos jugadores". En Proc. 47º FOCS . págs. 261–272.