Juego de forma extensiva

En teoría de juegos , un juego en forma extensiva es una especificación que permite la representación explícita de varios 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 al tomar una decisión, y sus recompensas para todos los posibles resultados 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 las de forma normal en que proporcionan una descripción más completa del juego en cuestión, mientras que la forma normal simplemente lo reduce a una matriz de recompensas.

Juegos de forma extensiva finita

Algunos autores, sobre todo en 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. Si bien el resto de este artículo sigue este enfoque gradual con ejemplos que lo ilustran, aquí presentamos de entrada los juegos finitos en forma extensiva tal como se construyen (finalmente). Esta definición general fue introducida por Harold W. Kuhn en 1953, quien extendió 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 con raíces , llamado árbol de caza.
Cada nodo terminal (hoja) del árbol del juego tiene una n -tupla de pagos , lo que significa que hay un pago para cada jugador al final de cada posible juego.
Una partición de los nodos no terminales del árbol del juego en n + 1 subconjuntos, uno para cada jugador (racional), 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 de información completa tiene, por lo tanto, un conjunto vacío de nodos Azar).
Cada nodo del jugador de Chance tiene una distribución de probabilidad sobre sus aristas salientes.
Cada conjunto de nodos de un jugador racional se divide además 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 las aristas salientes de dos nodos cualesquiera del mismo conjunto de información ; por lo tanto, el conjunto de todas las aristas salientes de un conjunto de información se divide en clases de equivalencia , cada clase representa una posible elección para el movimiento de un jugador en algún momento , 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 lo tanto, un camino a través del árbol desde la raíz hasta un nodo terminal. En cualquier nodo no terminal perteneciente al azar, se elige una rama saliente según la distribución de probabilidad. En el nodo de cualquier jugador racional, este debe elegir una de las clases de equivalencia para las aristas, lo que determina con precisión una arista saliente, excepto que (en general) el jugador desconoce cuál está siguiendo. (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 lo tanto, en una selección : elegir con precisión 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 las recompensas en juegos con nodos de azar. 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, omite la discusión más técnica sobre la formalización de afirmaciones acerca de cómo se juega, como por ejemplo: "un jugador no puede distinguir entre nodos en el mismo conjunto de información al tomar una decisión". Estas afirmaciones pueden precisarse mediante la lógica modal epistémica ; véase Shoham y Leyton-Brown (2009 , cap. 13) para más detalles.

Un juego de dos jugadores con información perfecta sobre un árbol de juego (tal como se define en la teoría de juegos combinatorios y la inteligencia artificial ) puede representarse como un juego en forma extensiva con resultados (es decir, ganar, perder o empatar ). Ejemplos de tales juegos incluyen el tres en raya , el ajedrez y el ajedrez infinito . ^{[ 1 ]}^{[ 2 ]} Un juego sobre un árbol expectminimax , como el backgammon , no tiene información imperfecta (todos los conjuntos de información son singletons), pero sí tiene movimientos aleatorios. Por ejemplo, el póker tiene tanto movimientos aleatorios (las cartas que se reparten) como información imperfecta (las cartas que guardan en secreto los demás jugadores). ( Binmore 2007 , cap. 2)

Información perfecta y completa

Una representación completa en forma extensiva especifica:

los jugadores de un juego
para cada jugador cada oportunidad que tienen de moverse
lo que cada jugador puede hacer en cada uno de sus movimientos
lo que cada jugador sabe para cada movimiento
las recompensas recibidas por cada jugador por cada posible combinación de movimientos

El juego de la derecha tiene dos jugadores: 1 y 2. Los números junto a cada nodo no terminal indican a qué jugador pertenece ese nodo de decisión. Los números junto a cada nodo terminal representan las recompensas para los jugadores (por ejemplo, 2,1 representa una recompensa de 2 para el jugador 1 y una recompensa de 1 para el jugador 2). Las etiquetas junto a cada arista del grafo indican el nombre de la acción que representa dicha arista.

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' . Las recompensas son las especificadas en el árbol. Hay cuatro resultados posibles representados por los cuatro nodos terminales del árbol: (U,U'), (U,D'), (D,U') y (D,D'). Las recompensas asociadas a cada resultado son, respectivamente, (0,0), (2,1), (1,2) y (3,1).

Si el jugador 1 juega D , el jugador 2 jugará U' para maximizar su ganancia, por lo que el jugador 1 solo recibirá 1. Sin embargo, si el jugador 1 juega U , el jugador 2 maximiza su ganancia jugando D' y el jugador 1 recibe 2. El jugador 1 prefiere 2 a 1, por lo que jugará U y el jugador 2 jugará D' . Este es el equilibrio perfecto en subjuegos .

Información imperfecta

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 así. 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 tal que:

Cada nodo del conjunto pertenece a un jugador.
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 ha llegado.

En su forma extensiva, un conjunto de información se indica mediante una línea punteada que conecta todos los nodos de ese conjunto o, a veces, mediante un bucle que rodea todos los nodos de ese conjunto.

Si un juego tiene un conjunto de información con más de un miembro, se dice que tiene información imperfecta . Un juego con información perfecta es aquel en el que, en cualquier etapa del juego, cada jugador sabe exactamente lo que ha ocurrido anteriormente; es decir, cada conjunto de información es un conjunto unitario . ^{[ 1 ]}^{[ 2 ]} Cualquier juego sin información perfecta tiene información imperfecta.

El juego de la derecha es igual que el anterior, salvo que el jugador 2 desconoce las acciones del jugador 1 al comenzar a jugar. El primer juego descrito cuenta con información completa; el de la derecha, no. Si ambos jugadores son racionales y ambos saben que ambos jugadores son racionales y todo lo que sabe cualquier jugador es conocido por todos los jugadores (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á el siguiente: el jugador 1 sabe que si juega U , el jugador 2 jugará D' (porque para el jugador 2 una recompensa de 1 es preferible a una recompensa 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 una recompensa de 2 es mejor que una recompensa 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 haciéndole creer 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 existe 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 jugará D sin duda . En este equilibrio, toda estrategia es racional dadas las creencias que se tienen y toda creencia es coherente con las estrategias jugadas. Nótese 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 una recompensa única para cada combinación de movimientos. Utilizando la forma normal del juego, ahora es posible resolverlo e identificar las 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 donde ambos jugadores tengan una preferencia proporciona un equilibrio de Nash. Este juego en particular tiene una única solución (D,U') con una recompensa de (1,2).

En juegos con espacios de acción infinitos e información imperfecta, los conjuntos de información no unitarios se representan, si es necesario, insertando una línea punteada que conecta los extremos (no nodales) detrás del arco descrito anteriormente o trazando el arco mismo con líneas discontinuas. En la competición de Stackelberg descrita anteriormente, si el segundo jugador no hubiera observado el movimiento del primer jugador, el juego ya no se ajustaría al modelo de Stackelberg; sería una competición de Cournot .

Información incompleta

Puede darse el caso de que un jugador no sepa con exactitud cuáles son las recompensas del juego ni 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 mediante 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 divina . Consideremos un juego en el que un empleador decide si contratar o no a un solicitante de empleo. La habilidad del solicitante puede ser alta o baja. Su nivel de habilidad es aleatorio; tiene una probabilidad de 1/3 de tener una habilidad baja o de 2/3 de tener una habilidad alta. En este caso, es conveniente modelar la naturaleza como otro jugador que elige la habilidad del solicitante según esas probabilidades. Sin embargo, la naturaleza no tiene recompensas. La elección de la naturaleza se representa en el árbol del juego mediante un nodo vacío. Las aristas que parten de un nodo de elección de la naturaleza se etiquetan con la probabilidad de que ocurra el evento que representa.

El juego de la izquierda es de información completa (todos los jugadores y sus recompensas son conocidos por todos), pero de información imperfecta (el empleador desconoce la jugada de la naturaleza). El nodo inicial se encuentra en el centro y no está ocupado, por lo que la naturaleza juega primero. La naturaleza selecciona con la misma probabilidad el tipo de jugador 1 (lo que en este juego equivale a seleccionar las recompensas en el subjuego jugado), ya sea t1 o t2. El jugador 1 posee conjuntos de información distintos para estos; es decir, el jugador 1 sabe qué tipo son (aunque esto no tiene por qué ser así). 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, existe información perfecta. De hecho, ahora es apropiado modificar la definición anterior de información completa: en cada etapa del juego, cada jugador sabe qué jugadas han realizado los demás jugadores . En el caso de información privada, cada jugador sabe qué jugada ha realizado la naturaleza. Los conjuntos de información se representan, como antes, mediante líneas discontinuas.

En este juego, si la naturaleza selecciona 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 atraviese sus conjuntos de información lo descalifica como subjuego ). Hay un equilibrio bayesiano perfecto separador ; es decir, un equilibrio en el que los diferentes 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 formar la creencia de que están en cualquiera de los nodos en el conjunto de información con probabilidad 1/2 (porque esta es la probabilidad de ver cualquiera de los tipos). El jugador 2 maximiza su pago jugando D' . Sin embargo, si juega D' , el tipo 2 preferiría jugar U. Esto no puede ser un equilibrio. Si ambos tipos juegan U , el jugador 2 nuevamente forma la creencia de que están en cualquiera de los nodos con probabilidad 1/2. En este caso, el jugador 2 juega D ' , pero entonces el tipo 1 prefiere jugar D.

Si el jugador 1 juega U y el jugador 2 juega D , el jugador 2 jugará D' independientemente de la acción que observe, pero el jugador 1 prefiere D. Por lo tanto, el único equilibrio posible es que el jugador 1 juegue D , el jugador 2 juegue U y el jugador 2 juegue U' si observa D , y que se elija al azar si observa U. Mediante sus acciones, el jugador 1 ha indicado su tipo al jugador 2.

Definición formal

Formalmente, un juego finito en forma extensiva es una estructura $\Gamma =\langle {\mathcal {K}},\mathbf {H} ,[(\mathbf {H} _{i})_{i\in {\mathcal {I}}}],\{A(H)\}_{H\in \mathbf {H} },a,\rho ,u\rangle$ dónde:

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

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

${\mathcal {I}}=\{1,...,I\}$ es un conjunto finito de jugadores, $0$ es (un jugador especial llamado) naturaleza, y $(\mathbf {H} _{i})_{i\in {\mathcal {I}}\cup \{0\}}$ es una partición del jugador del conjunto de información $\mathbf {H}$ . Dejar $\iota (v)=\iota (H)$ ser un solo jugador que realiza un movimiento en el nodo $v\in H$ .
$\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
$u=(u_{i})_{i\in {\mathcal {I}}}:T\rightarrow \mathbb {R} ^{\mathcal {I}}$ es una función de perfil de pago.

Espacio de acción infinito

Es posible que un jugador tenga un número infinito de acciones posibles para elegir en un nodo de decisión determinado. El dispositivo utilizado para representar esto es un arco que une dos aristas que sobresalen del nodo de decisión en cuestión. Si el espacio de acciones es un continuo entre dos números, los límites inferior y superior se colocan en la parte inferior y superior del arco, respectivamente, generalmente con una variable que se utiliza para expresar las recompensas. El número infinito de nodos de decisión que podrían resultar se representa mediante un único nodo colocado en el centro del arco. Un dispositivo similar se utiliza para representar espacios de acciones que, si bien no son infinitos, son lo suficientemente grandes como para que resulte impracticable representarlos con una arista 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á en otro lugar. Aquí, se supondrá que se trata del primer caso y, para mayor concreción, se supondrá que representa a dos empresas que participan en una competencia de Stackelberg . Las recompensas para las empresas se representan a la izquierda, con $q_{1}$ y $q_{2}$ como la estrategia que adoptan y $c_{1}$ y $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 de cada función de pago con respecto a la variable de estrategia del seguidor (empresa 2) ( ⁠ $q_{2}$ ) y encontrar su mejor función de respuesta, $q_{2}(q_{1})={\tfrac {5000-q_{1}-c_{2}}{2}}$ . 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 ⁠ $q_{1}$ al tomar la primera derivada, obteniendo $q_{1}^{*}={\tfrac {5000+c_{2}-2c_{1}}{2}}$ . Al introducir esto en la función de mejor respuesta de la empresa 2, $q_{2}^{*}={\tfrac {5000+2c_{1}-3c_{2}}{4}}$ y $(q_{1}^{*},q_{2}^{*})$ es el equilibrio de Nash perfecto del subjuego.

Véase también

Referencias

^ https ://www.math.uni-hamburg/Infinite Games, Yurii Khomskii (2010) Infinite Games (sección 1.1), Yurii Khomskii (2010)
1 2 "Ajedrez infinito, PBS Infinite Series" PBS Infinite Series. Información perfecta definida en 0:25, con fuentes académicas arXiv : 1302.4377 y arXiv : 1510.08155 .
↑ Watson, Joel. (09/05/2013). Estrategia : una introducción a la teoría de juegos . págs. 97–100 . ISBN 978-0-393-91838-0OCLC 1123193808
↑ Watson, Joel. (09/05/2013). Estrategia : una introducción a la teoría de juegos . págs. 26–28 . ISBN 978-0-393-91838-0OCLC 1123193808
↑ Watson, Joel. (09/05/2013). Estrategia : una introducción a la teoría de juegos . págs. 22–26 . ISBN 978-0-393-91838-0OCLC 1123193808

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). Jugando 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 extensiva, págs. 74-78). Rand Corp. ISBN 0-486-64216-X
Fudenberg D y Tirole J. (1991) Teoría de juegos (Cap. 3 Juegos en forma extensiva, pp. 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-1Una introducción matemática de 88 páginas; véanse los capítulos 4 y 5. Disponible gratuitamente en línea. Archivado el 15 de agosto de 2000 en la Wayback Machine de muchas universidades.
Luce RD y Raiffa H. (1957). Juegos y decisiones: introducción y análisis 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, de teoría de juegos y lógicos , Nueva York: Cambridge University Press , ISBN 978-0-521-89943-7. Una referencia completa desde una perspectiva computacional; véase el Capítulo 5. Descargable gratuitamente en línea .

Lecturas adicionales

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 determinismo)", analiza los problemas de extender 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 hasta ahora, pero que circulaban en forma de fotocopias).