• Author / Uploaded
• leidy0529

Citation preview

Juegos dinámicos con información perfecta

Unidad 5. Juegos dinámicos con información perfecta (3 clases) 1. Definiciones y elementos del juego

2. Dominancia y amenazas no creíbles. Ejemplos 2. Solución por inducción hacia atrás 3. Equilibrio perfecto en subjuegos

4. Equilibrio bayesiano perfecto débil

Agenda •

Conceptos básicos

•

Estructura del juego dinámico forma extensiva

•

Elementos básicos de la representación extensiva

•

Ejemplos

•

Formalización del orden de los sucesos

Características • Hay situaciones en las que la interacción de los agentes tiene forma interactiva • Cada interacción revela información total o parcial sobre las acciones de los demás • La información recopilada sirve para revisar y actualizar las estrategias individuales

Información perfecta • Cada jugador tiene la misma información que estaría disponible al final del juego • Cada uno puede ver los movimientos de los demás jugadores

Se representan con árboles de decisión

Ventajas del uso de árboles de decisión • Describe explícitamente el orden de los movimientos de los jugadores • Define la información disponible para cada jugador • Muestra las acciones disponibles en cada punto del juego

Representación en la forma extensiva

Definición del juego dinámico Un juego en forma extensiva de información perfecta tiene la forma

Identificar los elementos

Elementos del juego dinámico 1. N es el conjunto de jugadores 2. K es el conjunto finito de los nodos del árbol 3. R es una relación sobre K que define un árbol

4. Z son los nodos terminales del árbol

Elementos del juego dinámico 5. Ki es una partición K/Z que denota los nodos donde cada jugador juega. 6. A(k) denota el conjunto de acciones posible del jugador i en el nodo k. ak son los elementos del conjunto k

Elementos del juego dinámico 7. ui(z) denota la utilidad del agente i cuando el resultado final del juego es el nodo terminal z..

Cuando la utilidad se representa en términos de

pagos, ui(z) se denota como 𝜋𝑖(𝑧)

Elementos de la representación en Forma Extensiva 1. Conjunto de jugadores. 𝑁 = 0, 1, 2, … , 𝑛 El 0 representa la naturaleza (acciones exógenas al juego).

2. El orden de sucesos. Se formaliza mediante un árbol de sucesos: unos nodos x e y; un conjunto de nodos 𝐾, una relación binaria de precedencia 𝑅, una de precedencia inmediata 𝑃 y nodos finales 𝑍.

Elementos de la representación en Forma Extensiva 3. Orden de movimientos. El conjunto de nodos iniciales e intermedios 𝐾, Z se particiona en 𝑛 + 1 subconjuntos 𝐾0, 𝐾1, …. 𝐾𝑛 . • Si 𝑥 ∈ 𝐾𝑖 indica que una vez materializado el suceso representado en el nodo 𝑥, es el jugador 𝑖 ∈ 𝑁 quien a ha de ejecutar una acción. • Postulamos que 𝐾0 = 𝑥0 (la naturaleza mueve primero)

Representación de un árbol de eventos

Elementos de la representación en Forma Extensiva 4. Acciones Posibles. Para todo nodo 𝑥 ∈ 𝐾, el conjunto de acciones posibles a disposición del jugador quien decide en ese momento del juego se denota por 𝐴(𝑥). • Por supuesto: • Esto es a cada sucesor inmediato de 𝑥 se le asocia una única acción diferente 𝑎 ∈ 𝐴(𝑥). 𝐴 𝑥 y 𝑃−1(𝑥) son isomórficos.

Elementos de la representación en Forma Extensiva 5. Conjuntos de información. Para cada 𝑖 ∈ 𝑁, consideramos una partición 𝐻𝑖 de su conjunto de nodos 𝐾𝑖 en conjuntos disjuntos, esto es:

Cuando dos nodos comparten el mismo conjunto de información (conjuntos no disjuntos) el jugador i no es capaz de distinguir entre ellos

Elementos de la representación en Forma Extensiva

6. Pagos • Asociado con cada posible juego existe un pago para cada 𝑖 ∈ 𝑁. • Para cada 𝑧 ∈ 𝑍 (nodos finales) asignamos un vector 𝑛dimensional:

Elementos de la representación en Forma Extensiva • Cada 𝜋𝑖(𝑧) es identificado como el pago del jugador 𝑖 si el nodo final 𝑧 es alcanzado. • Los pagos 𝜋𝑖(∙) incorporan como los jugadores evalúan todo posible resultado del juego y reflejar toda consideración relevante.

Juego en forma extensiva

Resumiendo En la representación gráfica de los juegos de forma extensiva: • Lo movimientos se representan por líneas (árbol). • Los nodos intermedios se rotulan con el índice 𝑖 ∈ 𝑁 del jugador que toma la decisión en ese punto. • Las líneas que parten de los nodos intermedios 𝑥 ∈ 𝐾, son rotulados con las respectivas acciones 𝑎 ∈ 𝐴(𝑥), conduciendo a los respectivos sucesores en 𝑃−1(𝑥).

Ejemplo 1.

Juego de “cara y sello”

• Hay dos jugadores. Jugador 1 y Jugador 2 • Cada uno tiene una ficha blanca para lanzar. • Número de lanzamientos:5 veces • Cara (marcado en verde) o sello (sin marca)

• Pagos:

Acción

Jugador 1

Jugador 2

Coinciden los lados

Recibe un punto

Pierde un punto

No coinciden los lados

Pierde un punto

Recibe un punto

Ejemplo 1. Juego de “cara y sello” Configuración del juego Dos tipos de interacción

• Simultáneo:

back to back

• Secuencial:

Jugador 1 lanza primero y le sigue el jugador 2

Ejemplo 1. Juego de “cara y sello” Elementos del juego • N =2 • Acciones: Cara (Head) o Sello (Tail) • Conjuntos de información: Uno para cada jugador • Estrategias = Acciones • Pagos: 𝝅𝟏 𝑯, 𝑯 = 𝟏 ; 𝝅𝟏 𝑯, 𝑻 = (−𝟏) 𝝅𝟐 𝑯, 𝑯 = −𝟏 ; 𝝅𝟐 𝑯, 𝑻 = (𝟏)

Juego de cara y sello. Representación estratégica

Juego de cara y sello. Representación secuencial

Ejemplo 1.b. Juego de cara y sello

Jugador 2 lanza primero

Juego en forma extensiva. Orden de los sucesos (formalización) Con K la colección de eventos del juego R es una relación binaria bajo el criterio de precedencia lógica definida como: Sean

𝑥, 𝑦 ∈ 𝐾 → 𝑥𝑅𝑦

Si cada senda de juego que es posible en y también es posible en x Si y ocurre es porque x también ocurre

Propiedades de R R es un estricto orden parcial sobre K • Irreflexibilidad

∀𝑥 ∈ 𝐾,¬(𝑥𝑅𝑥)

Ningún x precede lógicamente a x

• Transitividad

∀𝑥, 𝑥´𝑥´´ ∈ 𝐾 → 𝑆𝑖 𝑥𝑅𝑥´ ∧ 𝑥´𝑅𝑥´´ ⇒ 𝑥𝑅𝑥´´

Relación binaria de precedencia inmediata P

No hay nodos entre x y x´ que tengan precedencia lógica

Definición de conjuntos de órdenes de sucesos • Conjunto de predecesores inmediatos

𝑥, 𝑥´ ∈ 𝐾 → 𝑃(𝑥) ≡ 𝑥´ ∈ 𝐾: 𝑥´𝑃𝑥 • Conjunto de sucesores inmediatos

𝑥, 𝑥´ ∈ 𝐾 → 𝑃−1(𝑥) ≡ 𝑥´ ∈ 𝐾: 𝑥𝑃𝑥´

Estructura del conjunto (K,R) (K,R) son un conjunto de eventos parcialmente ordenados que reflejan el despliegue del juego (K,R) debe tener una estructura de árbol de eventos

Propiedades del árbol de eventos de (K,R) 1. Hay un nodo inicial o raíz x0 tal que:

𝑃 𝑥0 = Φ

∀𝑥 ≠ 𝑥0 → 𝑥0𝑅𝑥 El nodo inicial precede a todos los demás nodos

Propiedades del árbol de eventos de (K,R) 2. Hay una serie de nodos intermedios

una senda de predecesores que vincula el nodo intermedio a su nodo raíz

Propiedades del árbol de eventos de (K,R) Corolario:

∀ 𝑥 ≠ 𝑥0 ∃! 𝑃 𝑥 = 𝑥´ Clave para asociar a cada nodo un conjunto de eventos previos de manera unívoca (historia subyacente)

Propiedades del árbol de eventos de (K,R) 3. Sea Z el conjunto de nodos finales

𝑍 = 𝑥 ∈ 𝐾: 𝑃−1 𝑥 = Φ

¿Cómo es la historia del juego para cada uno de los nodos definidos?

Próxima semana Próximo tema: Estrategias puras en juegos dinámicos. Cap. 5 Libro de Alvaro Riascos. NO entra: Forma multiagente o de Selten Leer pg. 124 DESDE Ejemplo 5.7 Solución por inducción hacia atrás

Gracias