En teoría de juegos , un juego en forma extensiva es una especificación de un juego que permite (como sugiere el nombre) la representación explícita de una serie de aspectos clave, como la secuencia de los posibles movimientos de los jugadores, sus elecciones en cada punto de decisión , la información (posiblemente imperfecta ) que cada jugador tiene sobre los movimientos del otro jugador cuando toma una decisión y sus pagos para todos los resultados posibles del juego. Los juegos en forma extensiva también permiten la representación de información incompleta en forma de eventos aleatorios modelados como " movimientos por naturaleza ". Las representaciones en forma extensiva se diferencian de la forma normal en que proporcionan una descripción más completa del juego en cuestión, mientras que la forma normal simplemente reduce el juego a una matriz de pagos.
Algunos autores, en particular en los libros de texto introductorios, definen inicialmente el juego en forma extensiva como un simple árbol de juego con pagos (sin información imperfecta o incompleta), y añaden los demás elementos en capítulos posteriores como refinamientos. Mientras que el resto de este artículo sigue este enfoque suave con ejemplos motivadores, presentamos de entrada los juegos finitos en forma extensiva tal como se construyen (en última instancia) aquí. Esta definición general fue introducida por Harold W. Kuhn en 1953, quien amplió una definición anterior de von Neumann de 1928. Siguiendo la presentación de Hart (1992), un juego en forma extensiva de n jugadores consta de lo siguiente:
Una jugada es, por tanto, un camino a través del árbol desde la raíz hasta un nodo terminal. En cualquier nodo no terminal que pertenezca a Chance, se elige una rama saliente según la distribución de probabilidad. En el nodo de cualquier jugador racional, el jugador debe elegir una de las clases de equivalencia para las aristas, lo que determina precisamente una arista saliente excepto que (en general) el jugador no sabe cuál está siendo seguida. (Un observador externo que conozca las elecciones de todos los demás jugadores hasta ese punto, y la realización de los movimientos de la Naturaleza, puede determinar la arista con precisión). Una estrategia pura para un jugador consiste, por tanto, en una selección : elegir precisamente una clase de aristas salientes para cada conjunto de información (suyo). En un juego de información perfecta, los conjuntos de información son singletons . Es menos evidente cómo deben interpretarse los pagos en juegos con nodos de Chance. Se supone que cada jugador tiene una función de utilidad de von Neumann-Morgenstern definida para cada resultado del juego; esta suposición implica que cada jugador racional evaluará un resultado aleatorio a priori por su utilidad esperada .
La presentación anterior, si bien define con precisión la estructura matemática sobre la que se desarrolla el juego, elude sin embargo la discusión más técnica de la formalización de enunciados sobre cómo se desarrolla el juego, como "un jugador no puede distinguir entre nodos en el mismo conjunto de información al tomar una decisión". Estos pueden precisarse utilizando la lógica modal epistémica ; véase Shoham y Leyton-Brown (2009, cap. 13) para más detalles.
Un juego de información perfecta para dos jugadores sobre un árbol de juegos (tal como se define en la teoría de juegos combinatorios y la inteligencia artificial ) se puede representar como un juego en forma extensiva con resultados (es decir, ganar, perder o empatar ). Ejemplos de tales juegos incluyen tres en raya , ajedrez y ajedrez infinito . [1] [2] Un juego sobre un árbol expectminimax , como el del backgammon , no tiene información imperfecta (todos los conjuntos de información son singletons) pero tiene movimientos de azar. Por ejemplo, el póquer tiene tanto movimientos de azar (las cartas que se reparten) como información imperfecta (las cartas que otros jugadores guardan en secreto). (Binmore 2007, cap. 2)
Una representación completa en forma extensiva especifica:
El juego de la derecha tiene dos jugadores: 1 y 2. Los números que aparecen junto a cada nodo no terminal indican a qué jugador pertenece ese nodo de decisión. Los números que aparecen junto a cada nodo terminal representan los pagos a los jugadores (por ejemplo, 2,1 representa un pago de 2 para el jugador 1 y un pago de 1 para el jugador 2). Las etiquetas junto a cada borde del gráfico son el nombre de la acción que representa ese borde.
El nodo inicial pertenece al jugador 1, lo que indica que el jugador 1 mueve primero. El juego según el árbol es el siguiente: el jugador 1 elige entre U y D ; el jugador 2 observa la elección del jugador 1 y luego elige entre U' y D' . Los pagos son los especificados en el árbol. Hay cuatro resultados representados por los cuatro nodos terminales del árbol: (U, U'), (U, D'), (D, U') y (D, D'). Los pagos asociados con cada resultado respectivamente son los siguientes (0,0), (2,1), (1,2) y (3,1).
Si el jugador 1 juega D , el jugador 2 jugará U' para maximizar su pago y, por lo tanto, el jugador 1 solo recibirá 1. Sin embargo, si el jugador 1 juega U , el jugador 2 maximiza su pago jugando D' y el jugador 1 recibe 2. El jugador 1 prefiere 2 a 1 y, por lo tanto, jugará U y el jugador 2 jugará D' . Este es el equilibrio perfecto en subjuegos .
Una ventaja de representar el juego de esta manera es que queda claro cuál es el orden de juego. El árbol muestra claramente que el jugador 1 mueve primero y el jugador 2 observa este movimiento. Sin embargo, en algunos juegos el juego no se desarrolla de esta manera. Un jugador no siempre observa la elección de otro (por ejemplo, los movimientos pueden ser simultáneos o un movimiento puede estar oculto). Un conjunto de información es un conjunto de nodos de decisión tales que:
En forma extensiva, un conjunto de información se indica mediante una línea de puntos que conecta todos los nodos de ese conjunto o, a veces, mediante un bucle dibujado alrededor de todos los nodos de ese conjunto.
Si un juego tiene un conjunto de información con más de un miembro, se dice que ese juego tiene información imperfecta . Un juego con información perfecta es tal que, en cualquier etapa del juego, cada jugador sabe exactamente lo que ha sucedido anteriormente en el juego; es decir, cada conjunto de información es un conjunto singleton . [1] [2] Cualquier juego sin información perfecta tiene información imperfecta.
El juego de la derecha es igual al juego anterior, salvo que el jugador 2 no sabe lo que hace el jugador 1 cuando sale a jugar. El primer juego descrito tiene información perfecta; el juego de la derecha no. Si ambos jugadores son racionales y ambos saben que ambos jugadores son racionales y todo lo que es conocido por cualquier jugador es conocido por cada jugador (es decir, el jugador 1 sabe que el jugador 2 sabe que el jugador 1 es racional y el jugador 2 sabe esto, etc. ad infinitum ), el juego en el primer juego será como sigue: el jugador 1 sabe que si juega U , el jugador 2 jugará D' (porque para el jugador 2 un pago de 1 es preferible a un pago de 0) y por lo tanto el jugador 1 recibirá 2. Sin embargo, si el jugador 1 juega D , el jugador 2 jugará U' (porque para el jugador 2 un pago de 2 es mejor que un pago de 1) y el jugador 1 recibirá 1. Por lo tanto, en el primer juego, el equilibrio será ( U , D' ) porque el jugador 1 prefiere recibir 2 a 1 y por lo tanto jugará U y por lo tanto el jugador 2 jugará D' .
En el segundo juego, la situación es menos clara: el jugador 2 no puede observar el movimiento del jugador 1. El jugador 1 quiere engañar al jugador 2 para que piense que ha jugado U cuando en realidad ha jugado D, de modo que el jugador 2 juegue D' y el jugador 1 reciba 3. De hecho, en el segundo juego hay un equilibrio bayesiano perfecto en el que el jugador 1 juega D y el jugador 2 juega U' y el jugador 2 cree que el jugador 1 definitivamente jugará D. En este equilibrio, cada estrategia es racional dadas las creencias que se tienen y cada creencia es coherente con las estrategias jugadas. Observe cómo la imperfección de la información cambia el resultado del juego.
Para resolver más fácilmente este juego para el equilibrio de Nash , [3] se puede convertir a la forma normal . [4] Dado que este es un juego simultáneo / secuencial , el jugador uno y el jugador dos tienen cada uno dos estrategias . [5]
Tendremos una matriz de dos por dos con un pago único para cada combinación de movimientos. Utilizando el juego en forma normal, ahora es posible resolver el juego e identificar estrategias dominantes para ambos jugadores.
Estas preferencias se pueden marcar dentro de la matriz, y cualquier casilla en la que ambos jugadores tengan una preferencia proporciona un equilibrio de Nash. Este juego en particular tiene una única solución de (D, U') con un pago de (1, 2).
En los juegos con espacios de acción infinitos e información imperfecta, los conjuntos de información que no son singleton se representan, si es necesario, insertando una línea de puntos que conecta los puntos finales (no nodales) detrás del arco descrito anteriormente o trazando una línea discontinua sobre el arco mismo. En la competición de Stackelberg descrita anteriormente, si el segundo jugador no hubiera observado el movimiento del primero, el juego ya no se ajustaría al modelo de Stackelberg; sería una competición de Cournot .
Puede darse el caso de que un jugador no sepa exactamente cuáles son los pagos del juego o de qué tipo son sus oponentes. Este tipo de juego tiene información incompleta . En forma extensiva se representa como un juego con información completa pero imperfecta utilizando la llamada transformación de Harsanyi . Esta transformación introduce en el juego la noción de elección de la naturaleza o elección de Dios . Consideremos un juego que consiste en un empleador considerando si contratar a un solicitante de empleo. La habilidad del solicitante de empleo puede ser una de dos cosas: alta o baja. Su nivel de habilidad es aleatorio; o tiene una habilidad baja con una probabilidad de 1/3 o una habilidad alta con una probabilidad de 2/3. En este caso, es conveniente modelar a la naturaleza como otro tipo de jugador que elige la habilidad del solicitante de acuerdo con esas probabilidades. Sin embargo, la naturaleza no tiene ningún pago. La elección de la naturaleza está representada en el árbol del juego por un nodo no lleno. Las aristas que provienen de un nodo de elección de la naturaleza están etiquetadas con la probabilidad de que ocurra el evento que representa.
El juego de la izquierda es uno de información completa (todos los jugadores y los pagos son conocidos por todos) pero de información imperfecta (el empleador no sabe cuál fue la jugada de la naturaleza). El nodo inicial está en el centro y no está lleno, por lo que la naturaleza mueve primero. La naturaleza selecciona con la misma probabilidad el tipo de jugador 1 (lo que en este juego equivale a seleccionar los pagos en el subjuego jugado), ya sea t1 o t2. El jugador 1 tiene conjuntos de información distintos para estos; es decir, el jugador 1 sabe de qué tipo son (este no tiene por qué ser el caso). Sin embargo, el jugador 2 no observa la elección de la naturaleza. No conoce el tipo de jugador 1; sin embargo, en este juego sí observa las acciones del jugador 1; es decir, hay información perfecta. De hecho, ahora es apropiado alterar la definición anterior de información completa: en cada etapa del juego, cada jugador sabe qué han jugado los otros jugadores . En el caso de la información privada, cada jugador sabe qué ha jugado la naturaleza. Los conjuntos de información se representan como antes mediante líneas discontinuas.
En este juego, si la naturaleza selecciona a t1 como el tipo del jugador 1, el juego será como el primer juego descrito, excepto que el jugador 2 no lo sabe (y el hecho mismo de que esto trascienda sus conjuntos de información lo descalifica para el estado de subjuego ). Hay un equilibrio bayesiano perfecto que separa a los distintos tipos de jugadores, es decir, un equilibrio en el que los distintos tipos hacen cosas diferentes.
Si ambos tipos juegan la misma acción (agrupación), no se puede mantener un equilibrio. Si ambos juegan D , el jugador 2 solo puede formarse la creencia de que están en cualquiera de los nodos del conjunto de información con una probabilidad de 1/2 (porque esta es la probabilidad de ver a cualquiera de los tipos). El jugador 2 maximiza su recompensa jugando D' . Sin embargo, si juegan D' , el tipo 2 preferiría jugar U . Esto no puede ser un equilibrio. Si ambos tipos juegan U , el jugador 2 vuelve a formarse la creencia de que están en cualquiera de los nodos con una probabilidad de 1/2. En este caso, el jugador 2 juega D' , pero entonces el tipo 1 prefiere jugar D .
Si el tipo 1 juega U y el tipo 2 juega D , el jugador 2 jugará D' sea cual sea la acción que observe, pero entonces el tipo 1 prefiere D. El único equilibrio, por lo tanto, es que el tipo 1 juegue D , el tipo 2 juegue U y el jugador 2 juegue U' si observa D y aleatorice si observa U. A través de sus acciones, el jugador 1 ha señalado su tipo al jugador 2.
Formalmente, un juego finito en forma extensiva es una estructura donde:
, la restricción de en es una biyección, con el conjunto de nodos sucesores de .
Puede ser que un jugador tenga un número infinito de posibles acciones para elegir en un nodo de decisión en particular. El dispositivo utilizado para representar esto es un arco que une dos bordes que sobresalen del nodo de decisión en cuestión. Si el espacio de acción es un continuo entre dos números, los números delimitadores inferior y superior se colocan en la parte inferior y superior del arco respectivamente, generalmente con una variable que se utiliza para expresar los pagos. El número infinito de nodos de decisión que podrían resultar se representa mediante un solo nodo colocado en el centro del arco. Un dispositivo similar se utiliza para representar espacios de acción que, aunque no son infinitos, son lo suficientemente grandes como para resultar poco prácticos para representarlos con un borde para cada acción.
El árbol de la izquierda representa un juego de este tipo, ya sea con espacios de acción infinitos (cualquier número real entre 0 y 5000) o con espacios de acción muy grandes (quizás cualquier entero entre 0 y 5000). Esto se especificaría en otra parte. Aquí, se supondrá que es el primero y, para ser más concretos, se supondrá que representa a dos empresas que participan en una competencia de Stackelberg . Los pagos para las empresas se representan a la izquierda, con y como la estrategia que adoptan y y como algunas constantes (aquí los costos marginales para cada empresa). Los equilibrios de Nash perfectos en subjuegos de este juego se pueden encontrar tomando la primera derivada parcial [ cita requerida ] de cada función de pago con respecto a la variable de estrategia del seguidor (empresa 2) ( ) y encontrando su mejor función de respuesta, . El mismo proceso se puede realizar para el líder excepto que al calcular su beneficio, sabe que la empresa 2 jugará la respuesta anterior y, por lo tanto, esto se puede sustituir en su problema de maximización. Luego puede resolver para tomando la primera derivada, obteniendo . Al introducir esto en la función de mejor respuesta de la empresa 2, y es el equilibrio de Nash perfecto en subjuegos.
Documentos históricos