Juego de forma extensiva

Amplia representación de un juego en la teoría de juegos.

En teoría de juegos , un juego de forma extensiva es una especificación de un juego que permite (como su nombre indica) 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 ganancias para todos los resultados posibles del juego. Los juegos de formato extensivo también permiten la representación de información incompleta en forma de eventos aleatorios modelados como " movimientos naturales ". 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.

Juegos finitos de forma extensiva

Algunos autores, particularmente en los libros de texto introductorios, inicialmente definen el juego en forma extensiva como simplemente un árbol de juego con pagos (sin información imperfecta o incompleta), y agregan los otros elementos en capítulos posteriores como refinamientos. Mientras que el resto de este artículo sigue este suave enfoque con ejemplos motivadores, presentamos de antemano los juegos finitos en forma extensiva tal como (en última instancia) se construyen 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 de 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 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 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 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 representa 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.

Por tanto, una obra es un camino a través del árbol desde la raíz hasta un nodo terminal. En cualquier nodo no terminal perteneciente a Chance, se elige una rama saliente de acuerdo con la distribución de probabilidad. En cualquier nodo de jugador racional, el jugador debe elegir una de las clases de equivalencia para las aristas, lo que determina precisamente una arista de salida excepto (en general) que el jugador no sabe cuál está siendo seguida. (Un observador externo que conozca las elecciones de los demás jugadores hasta ese momento, y la realización de los movimientos de la Naturaleza, puede determinar la ventaja con precisión.) Por lo tanto, una estrategia pura para un jugador consiste en una selección : elegir precisamente una clase de ventajas salientes para cada información. conjunto (de él). En un juego de información perfecta, los conjuntos de información son únicos . Es menos evidente cómo deben interpretarse los pagos 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; Este supuesto implica que todo jugador racional evaluará un resultado aleatorio a priori según su utilidad esperada .

La presentación anterior, si bien define con precisión la estructura matemática sobre la cual se juega el juego, elude sin embargo la discusión más técnica de formalizar afirmaciones sobre cómo se juega 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ítulo 13) para más detalles.

Un juego de información perfecta para dos jugadores sobre un árbol de juegos (como se define en la teoría de juegos combinatoria y la inteligencia artificial ) se puede representar como un juego de forma extensiva con resultados (es decir, ganar, perder o empatar ). Ejemplos de este tipo de juegos incluyen el tres en raya , el ajedrez y el ajedrez infinito . ^{[1] [2]} Un juego sobre un árbol expectminimax , como el de backgammon , no tiene información imperfecta (todos los conjuntos de información son únicos) 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 tienen en secreto). (Binmore 2007, capítulo 2)

Información perfecta y completa.

Una representación completa en formato extensivo especifica:

1. los jugadores de un juego
2. para cada jugador cada oportunidad que tiene para moverse
3. lo que cada jugador puede hacer en cada una de sus jugadas
4. lo que cada jugador sabe para cada movimiento
5. los pagos recibidos por cada jugador por cada posible combinación de movimientos

Un juego representado en forma extensiva.

El juego de la derecha tiene dos jugadores: 1 y 2. Los números de cada nodo no terminal indican a qué jugador pertenece ese nodo de decisión. Los números de cada nodo terminal representan los pagos a los jugadores (por ejemplo, 2,1 representa un pago de 2 al jugador 1 y un pago de 1 al jugador 2). Las etiquetas de 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 se 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. Jugador 1 prefiere 2 a 1 y así 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 ocurre 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 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 moverse no puede diferenciar entre 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.

Un juego con información imperfecta representada en forma extensiva.

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 sucedió anteriormente en el juego; es decir, cada conjunto de información es un conjunto único . ^{[1] [2]} Cualquier juego sin información perfecta tiene información imperfecta.

El juego de la derecha es el mismo que el juego anterior excepto que el jugador 2 no sabe qué hace el jugador 1 cuando viene 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 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 lo sabe, 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 un pago de 1 es preferible a un pago de 0) y así 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 El equilibrio será ( U , D' ) porque el jugador 1 prefiere recibir 2 a 1 y por eso jugará U y por tanto el jugador 2 jugará D' .

En el segundo juego está menos claro: el jugador 2 no puede observar el movimiento del jugador 1. Al jugador 1 le gustaría 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 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 consistente con las estrategias utilizadas. Observe cómo la imperfección de la información cambia el resultado del juego.

Para resolver más fácilmente este juego del equilibrio de Nash , ^[3] se puede convertir a la forma normal . ^[4] Dado que se trata de 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. Usando 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 cuadro donde ambos jugadores tengan una preferencia proporciona un equilibrio de Nash. Este juego en particular tiene una solución única de (D,U') con un pago de (1,2).

En juegos con espacios de acción infinitos e información imperfecta, los conjuntos de información no únicos 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 discontinuando el arco mismo. 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 competencia de Cournot .

Información incompleta

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 . Considere un juego en el que un empleador considera si debe contratar a un solicitante de empleo. La capacidad del solicitante de empleo puede ser una de dos cosas: alta o baja. Su nivel de habilidad es aleatorio; o tienen baja habilidad con probabilidad de 1/3 o alta habilidad con probabilidad de 2/3. En este caso, es conveniente modelar la naturaleza como otra especie de jugador que elige la habilidad del solicitante de acuerdo con esas probabilidades. La naturaleza, sin embargo, no tiene ningún beneficio. La elección de la naturaleza está representada en el árbol del juego mediante un nodo vacío. Los bordes que provienen de un nodo de elección de la naturaleza están etiquetados con la probabilidad de que ocurra el evento que representa.

Un juego con información incompleta e imperfecta representada de forma extensiva.

El juego de la izquierda es de información completa (todos los jugadores y pagos son conocidos por todos) pero de información imperfecta (el empleador no sabe cuál fue el movimiento de la naturaleza). El nodo inicial está en el centro y no está lleno. , entonces la naturaleza se 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 distintos conjuntos de información para estos; es decir, el jugador 1 sabe de qué tipo es (no tiene por qué ser así). Sin embargo, el jugador 2 no respeta la elección de la naturaleza. No conocen el tipo de jugador 1; sin embargo, en este juego sí observan las acciones del jugador 1; es decir, hay información perfecta. De hecho, ahora resulta apropiado modificar la definición anterior de información completa: en cada etapa del juego, cada jugador sabe lo que han jugado los demás jugadores . En el caso de la información privada, cada jugador sabe lo que ha jugado la naturaleza. Los conjuntos de información se representan como antes mediante líneas discontinuas.

En este juego, si la naturaleza selecciona t1 como tipo de 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 del estado de subjuego ). ). Hay un equilibrio bayesiano perfecto que lo separa ; es decir, un equilibrio en el que diferentes tipos hacen cosas diferentes.

Si ambos tipos desempeñan la misma acción (agrupación), no se puede mantener el equilibrio. Si ambos juegan D , el jugador 2 solo puede formarse la creencia de que está en cualquiera de los nodos del conjunto de información con probabilidad 1/2 (porque esta es la posibilidad de ver cualquier tipo). El jugador 2 maximiza su pago 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 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 el tipo 1 prefiere jugar D.

Si el tipo 1 juega U y el tipo 2 juega D , el jugador 2 jugará D' cualquier acción que observe, pero luego el tipo 1 prefiere D. Por lo tanto , el único equilibrio es con el tipo 1 jugando D , el tipo 2 jugando U y el jugador 2 jugando U' si observan D y aleatorizando si observan U. A través de sus acciones, el jugador 1 ha señalado su tipo al jugador 2.

Definicion formal

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, ${\displaystyle V}$ ${\displaystyle v^{0}\in V}$ ${\displaystyle T\subset V}$ ${\displaystyle D=V\setminus T}$ ${\displaystyle p:V\rightarrow D}$
• ${\displaystyle \mathbf {H} }$es una partición llamada partición de información, ${\displaystyle 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 acciones 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 on 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 jugador del conjunto de información . Sea un solo jugador el que haga 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.

Espacio de acción infinito

Puede ser que un jugador tenga un número infinito de acciones posibles para elegir en un nodo de decisión particular. 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 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 están representados por un único nodo colocado en el centro del arco. Se utiliza un dispositivo similar para representar espacios de acción que, si bien no son infinitos, son lo suficientemente grandes como para resultar poco práctico representarlos con un borde para cada acción.

Un juego con infinitos espacios de acción representados de forma extensiva

El árbol de la izquierda representa dicho juego, 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 número entero entre 0 y 5000). Esto se especificaría en otra parte. En este caso, se supondrá que es lo primero y, para ser más concretos, se supondrá que representa a dos empresas que participan en la competencia de Stackelberg . Los beneficios 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 necesaria ]} de cada función de pago con respecto a la variable estratégica del seguidor (empresa 2) ( ) y encontrando su función de mejor respuesta ,. Se puede realizar el mismo proceso para el líder, excepto que, al calcular su beneficio, sabe que la empresa 2 adoptará la respuesta anterior y, por tanto, esto puede sustituirse en su problema de maximización. Luego se puede resolver tomando la primera derivada, obteniendo . Introduciendo esto en la función de mejor respuesta de la empresa 2, se encuentra el equilibrio perfecto de Nash en subjuegos. ${\displaystyle q_{1}}$ ${\displaystyle q_{2}}$ ${\displaystyle c_{1}}$ ${\displaystyle c_{2}}$ ${\displaystyle q_{2}}$ ${\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}^{*})}$

Ver también

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

Referencias

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

• Hart, Sergio (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 . Prensa de la Universidad de Oxford EE. UU. 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 (Ch3 Juegos de forma extensiva, págs. 67-106). Prensa del MIT. 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 (Ch6 Juego extenso con información perfecta, págs. 89-115). Prensa del MIT. ISBN 0-262-65040-1 
• Shoham, Yoav; Leyton-Brown, Kevin (2009), Sistemas multiagente: fundamentos lógicos, algorítmicos y de teoría de juegos, Nueva York: Cambridge University Press , ISBN 978-0-521-89943-7. Una referencia integral desde una perspectiva computacional; consulte el Capítulo 5. Descargable gratis en línea.

Otras lecturas

• 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 "Mesurabilidad (el axioma de la determinación)", analiza los problemas al extender la definición de caso finito a un número infinito de opciones (o movimientos)

Artículos 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). Conferencias sobre teoría de juegos . Prensa de la Universidad de Princeton. ISBN 978-0-691-02772-2.contiene las conferencias de Kuhn en Princeton de 1952 (oficialmente inéditas anteriormente, pero en circulación como fotocopias)