En teoría de juegos , un equilibrio perfecto en subjuegos (o equilibrio de Nash perfecto en subjuegos ) es un refinamiento de un equilibrio de Nash utilizado en juegos dinámicos . Un perfil de estrategia es un equilibrio perfecto en subjuegos si representa un equilibrio de Nash de cada subjuego del juego original. De manera informal, esto significa que en cualquier punto del juego, el comportamiento de los jugadores a partir de ese punto en adelante debería representar un equilibrio de Nash del juego de continuación (es decir, del subjuego), sin importar lo que haya sucedido antes. Todo juego extensivo finito con recuerdo perfecto tiene un equilibrio perfecto en subjuegos. [1] Recuerdo perfecto es un término introducido por Harold W. Kuhn en 1953 y "equivalente a la afirmación de que las reglas del juego permiten a cada jugador recordar todo lo que sabía en movimientos anteriores y todas sus elecciones en esos movimientos" . [2]
Un método común para determinar los equilibrios perfectos en subjuegos en el caso de un juego finito es la inducción hacia atrás . En este caso, primero se consideran las últimas acciones del juego y se determinan las acciones que el último actor debe realizar en cada circunstancia posible para maximizar su utilidad . Luego, se supone que el último actor realizará estas acciones y se consideran las segundas acciones anteriores, eligiendo nuevamente aquellas que maximizan la utilidad de ese actor. Este proceso continúa hasta que se llega al primer movimiento del juego. Las estrategias que quedan son el conjunto de todos los equilibrios perfectos en subjuegos para juegos extensivos de horizonte finito de información perfecta. [1] Sin embargo, la inducción hacia atrás no se puede aplicar a juegos de información imperfecta o incompleta porque esto implica atravesar conjuntos de información que no son singleton .
Un equilibrio perfecto en subjuegos satisface necesariamente el principio de desviación única .
El conjunto de equilibrios perfectos en subjuegos de un juego determinado es siempre un subconjunto del conjunto de equilibrios de Nash de ese juego. En algunos casos, los conjuntos pueden ser idénticos.
El juego del ultimátum proporciona un ejemplo intuitivo de un juego con menos equilibrios perfectos en subjuegos que equilibrios de Nash.
En la Figura 1 se muestra la determinación del equilibrio perfecto en subjuegos mediante inducción hacia atrás. Las estrategias para el Jugador 1 están dadas por {Up, Uq, Dp, Dq}, mientras que las estrategias del Jugador 2 están entre {TL, TR, BL, BR}. Hay 4 subjuegos en este ejemplo, con 3 subjuegos propios.
Utilizando la inducción hacia atrás, los jugadores realizarán las siguientes acciones para cada subjuego:
Por lo tanto, el equilibrio perfecto en subjuegos es {Dp, TL} con el pago (3, 3).
En la Figura 2 se presenta a continuación un juego en forma extensiva con información incompleta. Nótese que el nodo del Jugador 1 con las acciones A y B, y todas las acciones posteriores, es un subjuego. Los nodos del Jugador 2 no son un subjuego, ya que son parte del 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. Según 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. [3]
Para resolver este juego, primero encuentre los Equilibrios de Nash por 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 conviertan en los pagos del Subjuego 2. [3]
La línea discontinua indica que el jugador 2 no sabe si el jugador 1 jugará A o B en un juego simultáneo.
El jugador 1 elige U en lugar de D porque 3 > 2 como pago para el jugador 1. El equilibrio resultante es (A, X) → (3,4).
Por lo tanto, el equilibrio perfecto en subjuegos mediante inducción hacia atrás es (UA, X) con el pago (3, 4).
En el caso de juegos repetidos finitamente, si un juego de etapa tiene un único equilibrio de Nash, el equilibrio perfecto en subjuegos consiste en jugar sin considerar las acciones pasadas, tratando el subjuego actual como un juego de una sola partida. Un ejemplo de esto es un juego de dilema del prisionero repetido finitamente . El dilema del prisionero recibe su nombre de una situación en la que hay dos culpables. Cuando son interrogados, tienen la opción de permanecer callados o desertar. Si ambos culpables permanecen callados, ambos cumplen una sentencia corta. Si ambos desertan, ambos cumplen una sentencia moderada. Si eligen opciones opuestas, entonces el culpable que deserta queda libre y el culpable que permanece callado cumple una sentencia larga. En última instancia, utilizando la inducción hacia atrás, el último subjuego en un dilema del prisionero repetido finitamente requiere que los jugadores jueguen el único equilibrio de Nash (ambos jugadores desertan). Debido a esto, todos los juegos anteriores al último subjuego también jugarán el equilibrio de Nash para maximizar sus pagos de un solo período. [4] Si un juego de etapa en un juego de repetición finita tiene múltiples equilibrios de Nash, se pueden construir equilibrios perfectos en subjuegos para realizar acciones de equilibrio de Nash que no sean de juego de etapa, a través de una estructura de "palo y zanahoria". Un jugador puede usar el equilibrio de Nash de un juego de etapa para incentivar la realización de la acción que no sea de equilibrio de Nash, mientras que usa un equilibrio de Nash de juego de etapa con una recompensa menor para el otro jugador si decide desertar. [5]
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é decisiones de subjuegos no deterministas). La perfección de subjuegos solo se utiliza con juegos de información completa . La perfección de subjuegos se puede utilizar con juegos de forma extensiva de información completa pero imperfecta .
El equilibrio de Nash perfecto en subjuegos normalmente se deduce por " inducción hacia atrás " a partir de los diversos resultados finales del juego, eliminando las ramas que implicarían que cualquier jugador haga un movimiento que no sea creíble (porque no es óptimo) a partir de 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 de este tipo 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 una longitud infinita, acciones infinitas como cada conjunto de información e información imperfecta si se satisface una condición de apoyo final.
El aspecto interesante de la palabra "creíble" en el párrafo precedente es que, tomadas en su conjunto (sin tener en cuenta la irreversibilidad de alcanzar subjuegos), existen estrategias que son superiores a las estrategias perfectas en subjuegos, pero que no son creíbles en el sentido de que una amenaza de llevarlas a cabo dañaría al jugador que la realiza y evitaría 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 porque 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á el juego (haciendo que su oponente se desvíe), y la amenaza del oponente de seguir el ejemplo suicidamente no es creíble.
{{cite book}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace ){{cite book}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace )