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. Informalmente, esto significa que en cualquier punto del juego, el comportamiento de los jugadores a partir de ese punto 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 recuperación perfecta tiene un equilibrio perfecto en subjuegos. [1] Recuerdo perfecto es un término introducido por Harold W. Kuhn en 1953 y "equivale 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 equilibrios perfectos en subjuegos en el caso de un juego finito es la inducción hacia atrás . Aquí primero se consideran las últimas acciones del juego y se determina qué acciones debe realizar el jugador final en cada circunstancia posible para maximizar su utilidad . Entonces se supone que el último actor realizará estas acciones, y se consideran las penúltimas acciones, 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 información perfecta de horizonte finito. [1] Sin embargo, la inducción hacia atrás no se puede aplicar a juegos de información imperfecta o incompleta porque esto implica cortar conjuntos de información que no son únicos .
Un equilibrio perfecto en subjuegos satisface necesariamente el principio de desviación única .
El conjunto de equilibrios perfectos en subjuegos para un juego dado es siempre un subconjunto del conjunto de equilibrios de Nash para 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 los equilibrios de Nash.
La determinación del equilibrio perfecto en subjuegos mediante el uso de inducción hacia atrás se muestra a continuación en la Figura 1. Las estrategias para el jugador 1 están dadas por {Up, Uq, Dp, Dq}, mientras que el jugador 2 tiene las estrategias 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 tanto, el equilibrio perfecto en subjuegos es {Dp, TL} con el pago (3, 3).
A continuación, en la Figura 2, se presenta un juego de forma extensiva con información incompleta. Tenga en cuenta que el nodo para el 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 forman 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 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 mediante la mejor respuesta mutua del Subjuego 1. Luego use la inducción hacia atrás y sustituya (A,X) → (3,4) para que (3,4) se convierta 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 para el pago del jugador 1. El equilibrio resultante es (A, X) → (3,4).
Por tanto, el equilibrio perfecto en subjuegos mediante inducción hacia atrás es (UA, X) con el pago (3, 4).
Para juegos finitamente repetidos, si un juego de etapa tiene solo un equilibrio de Nash único, el equilibrio perfecto en subjuegos es jugar sin considerar acciones pasadas, tratando el subjuego actual como un juego de una sola vez. Un ejemplo de esto es el juego del dilema del prisionero que se repite de forma finita . El dilema del prisionero recibe su nombre de una situación que contiene dos culpables. Cuando son interrogados, tienen la opción de quedarse callados o desertar. Si ambos culpables guardan silencio, ambos cumplirán una breve condena. Si ambos desertan, ambos cumplen una pena moderada. Si eligen opciones opuestas, entonces el culpable que falla queda libre y el culpable que se queda callado cumple una larga condena. En última instancia, utilizando la inducción hacia atrás, el último subjuego de un dilema del prisionero finitamente repetido requiere que los jugadores jueguen el equilibrio único 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 en un solo período. [4] Si un juego de escenario en un juego finitamente repetido tiene múltiples equilibrios de Nash, se pueden construir equilibrios perfectos en subjuegos para jugar acciones de equilibrio de Nash que no son de juegos de escenario, 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 es de equilibrio de Nash, mientras usa un equilibrio de Nash de juego de etapa con menor pago 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 perfecto en subjuegos (posiblemente como una estrategia mixta que proporcione subjuegos no deterministas). decisiones de juego). La perfección de subjuegos sólo se utiliza con juegos de información completa . La perfección en subjuegos se puede utilizar con juegos de forma extensiva con información completa pero imperfecta .
El equilibrio de Nash perfecto en subjuegos normalmente se deduce mediante " inducción hacia atrás " de los diversos resultados finales del juego, eliminando ramas que implicarían que cualquier jugador hiciera un movimiento que no es creíble (porque no es óptimo) 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 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 duración infinita, acciones infinitas como cada conjunto de información e imperfectos. información si se cumple una condición de apoyo final.
El aspecto interesante de la palabra "creíble" en el párrafo anterior 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 llevarlas a cabo dañará al jugador que hace la amenaza e impedirá esa combinación de estrategias. Por ejemplo, en el juego del " pollo ", si un jugador tiene la opción de arrancar el volante de su coche, siempre debe hacerlo porque conduce a un "subjuego" en el que su oponente racional no puede hacer lo mismo ( y matándolos a ambos). El desgarrador siempre ganará el juego (haciendo que su oponente se desvíe), y la amenaza del oponente de seguir suicidamente no es creíble.
{{cite book}}: Mantenimiento CS1: falta el editor de la ubicación ( enlace ){{cite book}}: Mantenimiento CS1: falta el editor de la ubicación ( enlace )