Equilibrio perfecto en subjuegos

En teoría de juegos , un equilibrio perfecto en subjuegos ( EPS ) o equilibrio de Nash perfecto en subjuegos ( ENSP ) es un refinamiento del concepto de equilibrio de Nash , diseñado específicamente para juegos dinámicos donde los jugadores toman decisiones secuenciales. Un perfil de estrategia es un EPS si representa un equilibrio de Nash en cada subjuego posible del juego original. En términos sencillos, esto significa que, en cualquier momento del juego, el comportamiento de los jugadores a partir de ese momento debería representar un equilibrio de Nash del juego de continuación (es decir, del subjuego), independientemente de lo que haya ocurrido antes. Esto garantiza que las estrategias sean creíbles y racionales durante todo el juego, eliminando las amenazas no creíbles.

Todo juego finito extensivo con información completa (todos los jugadores conocen el estado completo del juego) y recuerdo perfecto (cada jugador recuerda todas sus acciones y conocimientos previos a lo largo del juego) tiene un equilibrio perfecto en subjuegos. ^{[ 1 ]} Un método común para encontrar SPE en juegos finitos es la inducción hacia atrás , donde se comienza analizando las últimas acciones que el último jugador debería realizar para maximizar su utilidad y se trabaja hacia atrás. Si bien la inducción hacia atrás es un método común para encontrar SPE en juegos finitos, no siempre es aplicable a juegos con horizontes infinitos, o aquellos con información imperfecta o incompleta. En juegos de horizonte infinito, a menudo se utilizan otras técnicas, como el principio de desviación de una sola vez , para verificar SPE.

El equilibrio perfecto en subjuegos satisface necesariamente el principio de desviación de una sola vez y siempre es un subconjunto de los equilibrios de Nash para un juego dado. El juego del ultimátum es un ejemplo clásico de un juego con menos equilibrios perfectos en subjuegos que equilibrios de Nash.

La determinación del equilibrio perfecto en subjuegos mediante inducción hacia atrás se muestra en la Figura 1. Las estrategias del Jugador 1 son {Up, Uq, Dp, Dq}, mientras que las del Jugador 2 son {TL, TR, BL, BR}. En este ejemplo hay 4 subjuegos, de los cuales 3 son subjuegos propios.

Utilizando la inducción hacia atrás, los jugadores realizarán las siguientes acciones para cada subjuego:

• Subjuego para las acciones p y q: el jugador 1 tomará la acción p con recompensa (3, 3) para maximizar la recompensa del jugador 1, por lo que la recompensa para la acción L se convierte en (3,3).
• Subjuego para las acciones L y R: El jugador 2 tomará la acción L para 3 > 2, por lo que la recompensa para la acción D se convierte en (3, 3).
• Subjuego para las acciones T y B: El jugador 2 tomará la acción T para maximizar la recompensa del jugador 2, por lo que la recompensa para la acción U se convierte en (1, 4).
• Subjuego para las acciones U y D: El jugador 1 realizará la acción D para maximizar su recompensa.

Por lo tanto, el equilibrio perfecto en subjuegos es {Dp, TL} con la recompensa (3, 3).

A continuación, en la Figura 2, se presenta un juego en forma extensiva con información incompleta. Nótese que el nodo correspondiente al Jugador 1, con las acciones A y B, y todas las acciones subsiguientes, constituye un subjuego. Los nodos del Jugador 2 no forman un subjuego, ya que pertenecen al mismo conjunto de información.

El primer juego en forma normal es la representación en forma normal de todo el juego en forma extensiva. Con base en la información proporcionada, (UA, X), (DA, Y) y (DB, Y) son todos equilibrios de Nash para todo el juego.

El segundo juego en forma normal es la representación en forma normal del subjuego que comienza en el segundo nodo del Jugador 1 con las acciones A y B. Para el segundo juego en forma normal, el equilibrio de Nash del subjuego es (A, X).

Para todo el juego, los equilibrios de Nash (DA, Y) y (DB, Y) no son equilibrios perfectos en subjuegos porque el movimiento del Jugador 2 no constituye un equilibrio de Nash. El equilibrio de Nash (UA, X) es perfecto en subjuegos porque incorpora el equilibrio de Nash en subjuegos (A, X) como parte de su estrategia. ^{[ 2 ]}

Para resolver este juego, primero encuentre los equilibrios de Nash mediante la mejor respuesta mutua del subjuego 1. Luego use la inducción hacia atrás y sustituya (A,X) → (3,4) de modo que (3,4) se convierta en las recompensas para el subjuego 2. ^{[ 2 ]}

La línea discontinua indica que el jugador 2 no sabe si el jugador 1 jugará A o B en una partida simultánea.

El jugador 1 elige U en lugar de D porque 3 > 2 para la ganancia del jugador 1. El equilibrio resultante es (A, X) → (3,4).

Por lo tanto, el equilibrio perfecto de subjuegos a través de la inducción hacia atrás es (UA, X) con la recompensa (3, 4).

Para juegos repetidos un número finito de veces, si un juego de etapa tiene un único equilibrio de Nash, el equilibrio perfecto del subjuego consiste en jugar sin considerar las acciones pasadas, tratando el subjuego actual como un juego de una sola ronda. Un ejemplo de esto es el dilema del prisionero repetido un número finito de veces . El dilema del prisionero recibe su nombre de una situación que involucra a dos culpables. Al ser interrogados, tienen la opción de guardar silencio o delatar. Si ambos culpables guardan silencio, ambos cumplen una condena corta. Si ambos delatan, ambos cumplen una condena moderada. Si eligen opciones opuestas, el culpable que delata queda libre y el culpable que guarda silencio cumple una condena larga. En última instancia, mediante inducción hacia atrás, el último subjuego en un dilema del prisionero repetido un número finito de veces requiere que los jugadores jueguen el único equilibrio de Nash (ambos jugadores delatan). Debido a esto, todos los juegos anteriores al último subjuego también jugarán el equilibrio de Nash para maximizar sus ganancias de un solo período. ^{[ 3 ]} Si un juego de etapa en un juego repetido finitamente tiene múltiples equilibrios de Nash, se pueden construir equilibrios perfectos de subjuego para jugar acciones de equilibrio de Nash que no pertenecen al juego de etapa, a través de una estructura de "zanahoria y palo". Un jugador puede usar el equilibrio de Nash del juego de etapa para incentivar el juego de la acción que no pertenece al equilibrio de Nash, mientras que usa un equilibrio de Nash del juego de etapa con una recompensa menor para el otro jugador si decide desertar. ^{[ 4 ]}

Reinhard Selten demostró que cualquier juego que pueda dividirse en "subjuegos" que contengan un subconjunto de todas las opciones disponibles en el juego principal tendrá una estrategia de equilibrio de Nash perfecta en subjuegos (posiblemente como una estrategia mixta que dé lugar a decisiones no deterministas en los subjuegos). La perfección en subjuegos solo se utiliza con juegos de información completa . La perfección en subjuegos puede utilizarse con juegos de forma extensiva de información completa pero imperfecta .

El equilibrio de Nash perfecto en subjuegos se deduce normalmente mediante " inducción hacia atrás " a partir de los distintos resultados finales del juego, eliminando las ramas que implicarían que algún jugador realizara un movimiento que no es creíble (porque no es óptimo) desde ese nodo . Un juego en el que la solución de inducción hacia atrás es bien conocida es el tres en raya , pero en teoría incluso el Go tiene una estrategia óptima para todos los jugadores. El problema de la relación entre la perfección en subjuegos y la inducción hacia atrás fue resuelto por Kaminski (2019), quien demostró que un procedimiento generalizado de inducción hacia atrás produce todos los equilibrios perfectos en subjuegos en juegos que pueden tener longitud infinita, acciones infinitas como cada conjunto de información e información imperfecta si se cumple una condición de soporte final.

Lo interesante de la palabra "creíble" en el párrafo anterior es que, en su conjunto (sin tener en cuenta la irreversibilidad de alcanzar subjuegos), existen estrategias superiores a las estrategias perfectas en subjuegos, pero que no son creíbles en el sentido de que la amenaza de llevarlas a cabo perjudicará al jugador que la formula e impedirá esa combinación de estrategias. Por ejemplo, en el juego de " la gallina ", si un jugador tiene la opción de arrancar el volante de su coche, siempre debería hacerlo, ya que esto conduce a un "subjuego" en el que su oponente racional no puede hacer lo mismo (y matarlos a ambos). El que arranca el volante siempre ganará (haciendo que su oponente se desvíe), y la amenaza del oponente de seguir su ejemplo de forma suicida no es creíble.

• Juego del ciempiés
• inconsistencia dinámica
• Glosario de teoría de juegos
• Teorema minimax
• Análisis retrógrado
• Concepto de solución
• Principio de optimalidad de Bellman

• Selten, R. (1965). Spieltheoretische behandlung eines oligopolmodells mit nachfrageträgheit. Zeitschrift für die gesamte Staatswissenschaft/Journal of Institutional and Theoretical Economics , (H. 2), 301–324, 667–689. [en alemán - parte 1 , parte 2 ]
• Ejemplo de juegos en forma extensiva con información imperfecta
• Applet de Java para encontrar una solución de equilibrio de Nash perfecta en subjuegos para un juego en forma extensiva de gametheory.net.
• Applet de Java para encontrar una solución de equilibrio de Nash perfecta en subjuegos para un juego en forma extensiva de gametheory.net.
• Kaminski, MM Inducción hacia atrás generalizada: justificación de un algoritmo popular . Games 2019, 10, 34.