Diferencia entre Minimax y teorema de Nash existencia de Equilibrio

Question

Von Neumann teorema Minimax (tomado de Wikipedia):

Por cada dos personas, juego de suma cero con finito de estrategias, existe un valor de V y una estrategia mixta para cada jugador, de tal manera que (un) jugador 2 de la estrategia, la mejor rentabilidad posible para el jugador 1 es V, y (b) el jugador 1 de la estrategia, la mejor rentabilidad posible para el jugador 2 es −V.

Nash del teorema:

Cada finito juego tiene una estrategia mixta de equilibrio.

Ahora, para mí, parece que el teorema Minimax es simplemente una instancia específica del teorema de Nash, para dos jugadores juego de suma cero (en el momento establecido el equilibrio, los resultados sobre el valor de la partida siga inmediatamente).

Pero en mi Juego la Teoría del curso, hemos estudiado estos dos teoremas, con completamente diferentes pruebas. Algunos exámenes incluso había probar ambos teoremas como dos de las preguntas del examen - haciendo parecer una afirmación de que "Minimax se sigue inmediatamente a partir del teorema de Nash" sería sospechoso.

Estoy malentendido alguna diferencia fundamental entre estos dos teoremas? O ¿simplemente aprender dos pruebas diferentes de la misma cosa?

Answer 1

Wikipedia está de acuerdo, diciendo: "En juegos de suma cero, el minimax solución es la misma que el equilibrio de Nash" (segunda declaración de contenido de los artículo acerca de Minimax). De modo que la existencia del equilibrio de Nash es una generalización del teorema Minimax.

Presumiblemente, la prueba del teorema minimax es mucho más simple que la prueba del teorema general. Otra diferencia fundamental es que la prueba del teorema minimax es constructiva (que equivale a la programación lineal), mientras que la búsqueda de un equilibrio de Nash es PPAD-completo, incluso para dos juegos de jugador. Incluso es difícil encontrar un aproximado de equilibrio de Nash.

Answer 2

Si un juego tiene un valor, no es necesario tener una estrategia mixta equilibrio de Nash. En la de Von Neumann teorema Minimax se indicó anteriormente, se supone que, para cada jugador, el juego de estrategia mixta mejores respuestas es no vacío, dado que el otro jugador de la estrategia mixta. Sin embargo, esta suposición no es necesario para que un juego tenga un valor.