Hay una relación muy cercana. Los algoritmos de aprendizaje en línea como el algoritmo de mayoría ponderada aleatorizada (y, en general, cualquier algoritmo para resolver problemas de optimización convexa en línea como el descenso de gradiente en línea o Perceptron) son versiones constructivas del teorema Minimax de Von Neumann. Esto significa, en particular, que si usa un algoritmo de este tipo para jugar un juego contra un oponente (al identificar a los expertos del algoritmo de mayoría ponderada con las acciones en el juego, no importa qué estrategia tome su oponente contra usted, terminará haciendo lo mismo). así como si hubieras jugado la mejor acción fija en retrospectiva, que siempre logra al menos tu valor minimax en el juego. De hecho, la existencia de tales algoritmos de aprendizaje en línea conduce a una prueba muy simple del teorema minmax en sí mismo, mucho más simple que La prueba original de von Neumann.
En particular, si dos jugadores usan un algoritmo de este tipo jugando uno contra el otro en un juego de suma cero, ambos alcanzan su valor mínimo, lo que significa que el historial de juego converge a un equilibrio de Nash del juego.
Si los jugadores juegan un algoritmo de aprendizaje en línea más sofisticado que logra lo que se conoce como no arrepentimiento de intercambio , entonces, en cualquier juego, su juego convergerá a un equilibrio correlacionado. Esto muestra en particular que los equilibrios correlacionados son un concepto de solución manejable en cualquier juego conciso, lo que no es cierto para el equilibrio de Nash, que puede ser difícil de encontrar.
- ¿Crees que un asistente personal de inteligencia artificial puede resolver problemas fundamentales de productividad?
- ¿Las computadoras son buenas para resolver rompecabezas?
- ¿Por qué tanta gente asocia la IA con la robótica?
- ¿Sientes que los humanos son más evidentes; seres mecánicos computarizados robóticos altamente avanzados?
- ¿Qué tan grande es el mercado de procesadores específicamente diseñados o adaptados para la inteligencia artificial?
Para más información sobre esto, recomiendo revisar el Capítulo 4 del libro de texto Algorithmic Game Theory (Página en cmu.edu), o Lectures 6-11 de mi clase de pregrado: Algorithmic Game Theory
