Equilibrio de Nash
- Propuesto por
- John Nash
- Año
- 1950
- Tipo
- algorithm
- Familia
- Game-theoretic
Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés
¿Qué hace?
El Equilibrio de Nash es un concepto de solución en teoría de juegos donde ningún jugador puede desviarse unilateralmente para mejorar su pago.
Formalizado por John Nash en 1950, el algoritmo de Lemke-Howson encuentra computacionalmente equilibrios en juegos bimatriciales identificando pares de vértices completamente etiquetados en los politopos de estrategia.
La intuición detrás del método
En un Equilibrio de Nash, la estrategia de cada jugador es la mejor respuesta a la estrategia de todos los demás jugadores. Imagine una situación en la que ambos jugadores conocen la estrategia del otro: ninguno querría cambiar, ya que hacerlo solo les perjudicaría. El algoritmo de Lemke-Howson explota la geometría de los poliedros del juego, rastreando etiquetas (restricciones insatisfechas) y pivotando a través de vértices hasta encontrar un par completamente etiquetado, una configuración donde ambos jugadores no tienen desviaciones rentables.
Historia
John Nash demostró en su disertación de 1950 que todo juego finito posee al menos un Equilibrio de Nash de estrategia mixta. En 1964, Lemke y Howson publicaron el primer algoritmo constructivo para encontrar estos equilibrios, transformando la prueba de existencia de Nash en un método computacional práctico. Su trabajo se convirtió en la base de la teoría de juegos computacional y la economía algorítmica.
Cuándo usarlo
Utilice el análisis de Equilibrio de Nash al estudiar juegos con dos jugadores y espacios de estrategia discretos, o al buscar equilibrios completamente mixtos. Adecuado para modelar problemas de competencia, negociación y coordinación donde la interacción estratégica es primordial. El método de Lemke-Howson funciona mejor para juegos bimatriciales no degenerados; los casos degenerados pueden requerir computación simbólica o perturbación.
Limitaciones y consideraciones
- Limitado a juegos bimatriciales (de dos jugadores); la extensión a juegos de n jugadores es NP-difícil
- Falla o se vuelve ineficiente en juegos degenerados donde son posibles múltiples pivotes de entrada
- Puede encontrar solo un equilibrio; a menudo existen múltiples equilibrios en juegos de suma no nula
- No maneja directamente juegos dinámicos o de forma extensiva sin reformulación
Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.
Fortalezas
- Computacionalmente eficiente para encontrar equilibrios de Nash en juegos bimatriciales finitos
- Garantiza la convergencia a un par de vértices completamente etiquetados para juegos no degenerados
- Proporciona una base teórica que conecta la geometría combinatoria con la teoría de juegos
- Aplicable a equilibrios de estrategias mixtas, que a menudo son más realistas que los resultados de estrategias puras
Aplicaciones
- Economía: modelado de la competencia oligopolística y el comportamiento de fijación de precios en los mercados
- Subastas y diseño de mecanismos: análisis de estrategias de licitación en subastas de primer precio y sobre cerrado
- Ciberseguridad: predicción de equilibrios entre atacantes y defensores en juegos de seguridad de red
- Biología de la vida silvestre: análisis de estrategias evolutivamente estables en interacciones depredador-presa
Cómo funciona
Cómo funciona
Convertir el juego bimatricial en dos problemas de complementariedad lineal (LCP), uno para cada jugador, que representan sus condiciones de mejor respuesta.
Asignar etiquetas a los bordes y vértices de los politopos de estrategia basándose en qué restricciones de incentivo del jugador se violan.
Comenzando desde el vértice de todos unos (completamente etiquetado), realizar pivotes similares al simplex para navegar por el politopo, eliminando y añadiendo etiquetas hasta descubrir un par completamente etiquetado.
Confirmar que las estrategias de ambos jugadores forman respuestas mutuas óptimas comprobando que ninguno puede mejorar su pago dada la estrategia del otro.
Errores comunes
- Asumiendo que existe un equilibrio único; muchos juegos tienen múltiples equilibrios de Nash con diferentes implicaciones de pago
- Confundir equilibrios de estrategias mixtas (juego probabilístico) con equilibrios de estrategias puras, lo que lleva a una mala interpretación del comportamiento de los agentes
- Pasar por alto la distinción entre condiciones necesarias y suficientes para el equilibrio; un par completamente etiquetado satisface la optimalidad pero puede no ser realizado si los jugadores no pueden coordinarse
Preguntas frecuentes
¿Puede un juego no tener Equilibrio de Nash?
Los Equilibrios de Nash de estrategia pura pueden no existir (p. ej., Piedra-Papel-Tijera), pero todo juego finito tiene al menos un equilibrio de estrategia mixta donde los jugadores aleatorizan sobre las acciones con probabilidades específicas.
¿En qué se diferencia un equilibrio de estrategia mixta de un equilibrio de estrategia pura?
En un equilibrio de estrategia pura, cada jugador se compromete a una acción específica con certeza. En un equilibrio de estrategia mixta, cada jugador utiliza una distribución de probabilidad sobre las acciones. Los equilibrios mixtos son a menudo más generales y existen cuando los puros no lo hacen.
¿Por qué se prefiere el algoritmo de Lemke-Howson sobre la búsqueda exhaustiva?
El algoritmo explota la estructura de politopo de los espacios de estrategia, reduciendo el espacio de búsqueda exponencialmente y logrando la convergencia en tiempo polinomial para juegos no degenerados, mientras que la enumeración exhaustiva se vuelve inviable a medida que crece el espacio de estrategia.
Métodos relacionados
Fuentes
Nash, J. F. (1950). Equilibrium points in N-person games. Proceedings of the National Academy of Sciences, 36(1), 48-49.
Abrir referencia DOICopiado.Lemke, C. E., & Howson Jr, J. T. (1964). Equilibrium points of bimatrix games. Journal of the Society for Industrial and Applied Mathematics, 12(2), 413-423.
Abrir referencia DOICopiado.