Juego en formato extensivo

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:

• Un conjunto finito de n jugadores (racionales)
• Un árbol enraizado , llamado árbol del juego.
• Cada nodo terminal (hoja) del árbol de juego tiene una n -tupla de pagos , lo que significa que hay un pago para cada jugador al final de cada jugada posible.
• Una partición de los nodos no terminales del árbol de juego en n +1 subconjuntos, uno para cada jugador (racional), y con un subconjunto especial para un jugador ficticio llamado Azar (o Naturaleza). El subconjunto de nodos de cada jugador se denomina "nodos del jugador". (Un juego con información completa tiene, por lo tanto, un conjunto vacío de nodos de Azar).
• Cada nodo del jugador Chance tiene una distribución de probabilidad sobre sus bordes salientes.
• Cada conjunto de nodos de un jugador racional se divide a su vez en conjuntos de información , que hacen que ciertas elecciones sean indistinguibles para el jugador al realizar un movimiento, en el sentido de que:
  • existe una correspondencia uno a uno entre los bordes salientes de dos nodos cualesquiera del mismo conjunto de información—por lo tanto, el conjunto de todos los bordes salientes de un conjunto de información se divide en clases de equivalencia , cada clase representando una posible elección para el movimiento de un jugador en algún punto—, y
  • Cada ruta (dirigida) en el árbol desde la raíz hasta un nodo terminal puede cruzar cada conjunto de información como máximo una vez
• La descripción completa del juego especificada por los parámetros anteriores es de conocimiento común entre los jugadores.

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 momento, 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:

1. Los jugadores de un juego
2. Para cada jugador, cada oportunidad que tienen de moverse.
3. Lo que cada jugador puede hacer en cada uno de sus movimientos
4. Lo que cada jugador sabe para cada movimiento
5. los pagos recibidos por cada jugador por cada combinación posible de movimientos

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:

1. Cada nodo del conjunto pertenece a un jugador.
2. Cuando el juego llega al conjunto de información, el jugador que está a punto de mover no puede diferenciar entre los nodos dentro del conjunto de información; es decir, si el conjunto de información contiene más de un nodo, el jugador al que pertenece ese conjunto no sabe a qué nodo del conjunto se ha llegado.

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 qué 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]

• Estrategias del jugador 1: {U, D}
• Estrategias del jugador 2: {U', D'}

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.

• Si el jugador 1 juega Arriba (U), el jugador 2 prefiere jugar Abajo (D') (Pago 1>0)
• Si el jugador 1 juega Abajo (D), el jugador 2 prefiere jugar Arriba (U') (Pago 2>1)
• Si el jugador 2 juega Arriba (U'), el jugador 1 prefiere jugar Abajo (D) (Pago 1>0)
• Si el jugador 2 juega Abajo (D'), el jugador 1 prefiere jugar Abajo (D) (3>2)

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: ${\displaystyle \Gamma =\langle {\mathcal {K}},\mathbf {H} ,[(\mathbf {H} _{i})_{i\in {\mathcal {I}}}],\ {A(H)\}_{H\in \mathbf {H} },a,\rho ,u\rangle }$

• ${\displaystyle {\mathcal {K}}=\langle V,v^{0},T,p\rangle }$es un árbol finito con un conjunto de nodos , un nodo inicial único , un conjunto de nodos terminales ( sea un conjunto de nodos de decisión) y una función predecesora inmediata en la que se representan las reglas del juego,${\estilo de visualización V}$${\displaystyle v^{0}\en V}$${\displaystyle T\subconjunto V}$${\displaystyle D=V\setmenos T}$${\displaystyle p:V\rightarrow D}$
• ${\displaystyle \mathbf {H}}$es una partición llamada partición de información,${\estilo de visualización D}$
• ${\displaystyle A(H)}$es un conjunto de acciones disponibles para cada conjunto de información que forma una partición en el conjunto de todas las acciones .${\displaystyle H\in \mathbf {H}}$${\displaystyle {\mathcal {A}}}$
• ${\displaystyle a:V\setminus \{v^{0}\}\rightarrow {\mathcal {A}}}$es una partición de acción que asocia cada nodo a una única acción , cumpliendo:${\displaystyle v}$${\displaystyle a(v)}$

${\displaystyle \forall H\in \mathbf {H} ,\forall v\in H}$, la restricción de en es una biyección, con el conjunto de nodos sucesores de . ${\displaystyle a_{v}:s(v)\rightarrow A(H)}$${\displaystyle a}$${\displaystyle s(v)}$${\displaystyle s(v)}$${\displaystyle v}$

• ${\displaystyle {\mathcal {I}}=\{1,...,I\}}$es un conjunto finito de jugadores, es (un jugador especial llamado) naturaleza, y es una partición de jugadores del conjunto de información . Sea un único jugador que realiza un movimiento en el nodo .${\displaystyle 0}$${\displaystyle (\mathbf {H} _{i})_{i\in {\mathcal {I}}\cup \{0\}}}$${\displaystyle \mathbf {H} }$${\displaystyle \iota (v)=\iota (H)}$${\displaystyle v\in H}$
• ${\displaystyle \rho =\{\rho _{H}:A(H)\rightarrow [0,1]|H\in \mathbf {H} _{0}\}}$es una familia de probabilidades de las acciones de la naturaleza, y
• ${\displaystyle u=(u_{i})_{i\in {\mathcal {I}}}:T\rightarrow \mathbb {R} ^{\mathcal {I}}}$es una función de perfil de pago.

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 ⁠ ⁠${\displaystyle q_{1}}$ y ⁠ ⁠${\displaystyle q_{2}}$ como la estrategia que adoptan y ⁠ ⁠${\displaystyle c_{1}}$ y ⁠ ⁠${\displaystyle c_{2}}$ 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) ( ⁠ ⁠${\displaystyle q_{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, lo que da como resultado . Al introducir esto en la función de mejor respuesta de la empresa 2, y es el equilibrio de Nash perfecto en subjuegos. ${\displaystyle q_{2}(q_{1})={\tfrac {5000-q_{1}-c_{2}}{2}}}$${\displaystyle q_{1}}$${\displaystyle q_{1}^{*}={\tfrac {5000+c_{2}-2c_{1}}{2}}}$${\displaystyle q_{2}^{*}={\tfrac {5000+2c_{1}-3c_{2}}{4}}}$${\displaystyle (q_{1}^{*},q_{2}^{*})}$

• Axioma de determinación
• Información perfecta
• Teoría de juegos combinatorios
• Equilibrio autoconfirmante
• Juego secuencial
• Señalización
• Concepto de solución

• Hart, Sergiu (1992). "Juegos en formas extensivas y estratégicas". En Aumann, Robert ; Hart, Sergiu (eds.). Manual de teoría de juegos con aplicaciones económicas . Vol. 1. Elsevier. ISBN 978-0-444-88098-7.
• Binmore, Kenneth (2007). Jugar de verdad: un texto sobre teoría de juegos . Oxford University Press US. ISBN 978-0-19-530057-4.
• Dresher M. (1961). Las matemáticas de los juegos de estrategia: teoría y aplicaciones (Capítulo 4: Juegos en forma extensa, págs. 74-78). Rand Corp. ISBN 0-486-64216-X 
• Fudenberg D y Tirole J. (1991) Teoría de juegos (Capítulo 3 Juegos en forma extensiva, págs. 67-106). MIT Press. ISBN 0-262-06141-4 
• Leyton-Brown, Kevin; Shoham, Yoav (2008), Fundamentos de la teoría de juegos: una introducción concisa y multidisciplinaria, San Rafael, CA: Morgan & Claypool Publishers, ISBN 978-1-59829-593-1. Una introducción matemática de 88 páginas; consulte los capítulos 4 y 5. Gratis en línea Archivado el 15 de agosto de 2000 en Wayback Machine en muchas universidades.
• Luce RD y Raiffa H. (1957). Juegos y decisiones: introducción y estudio crítico. (Capítulo 3: Formas extensivas y normales, págs. 39-55). Wiley, Nueva York. ISBN 0-486-65943-7 
• Osborne MJ y Rubinstein A. 1994. Un curso de teoría de juegos (Capítulo 6: Juego extenso con información perfecta, págs. 89-115). MIT Press. ISBN 0-262-65040-1 
• Shoham, Yoav; Leyton-Brown, Kevin (2009), Sistemas multiagente: fundamentos algorítmicos, teóricos de juegos y lógicos, Nueva York: Cambridge University Press , ISBN 978-0-521-89943-7. Una referencia completa desde una perspectiva computacional; consulte el Capítulo 5. Descargable gratuitamente en línea.

• Horst Herrlich (2006). Axioma de elección . Saltador. ISBN 978-3-540-30989-5.6.1, "Desastres en la teoría de juegos" y 7.2 "Mensurabilidad (El axioma de determinación)", analiza los problemas en la extensión de la definición de caso finito a un número infinito de opciones (o movimientos).

Documentos históricos

• Neumann, J. (1928). "Zur Theorie der Gesellschaftsspiele". Annalen Matemáticas . 100 : 295–320. doi :10.1007/BF01448847. S2CID  122961988.
• Harold William Kuhn (2003). Lecciones sobre la teoría de juegos . Princeton University Press. ISBN 978-0-691-02772-2.Contiene las conferencias de Kuhn en Princeton de 1952 (oficialmente inéditas, pero circulan como fotocopias)