Juegos en Forma Extensiva Alvaro J. Riascos Villegas Universidad de los Andes y Quantil

Marzo 18 de 2010

Alvaro J. Riascos Villegas (Universidad de los Andes y Juegos Quantil) en Forma Extensiva

Marzo 18 de 2010

1 / 36

Introducción

De…nition Un juego en forma extensiva es una estructura D E Γ = N , R, Z , fKi gi =1,...,N , fHi gi =1,...,N , fA(k )gk 2K nZ , fui gi =1,...,N donde:

N es un conjunto de jugadores, N = f1, ...N g . R es una relación que de…ne un árbol con raíz donde K denota el conjunto de todos los nodos del árbol. Z son los nodos terminales del árbol.

Alvaro J. Riascos Villegas (Universidad de los Andes y Juegos Quantil) en Forma Extensiva

Marzo 18 de 2010

2 / 36

Juegos en forma extensiva

fKi gi =1,...,N es una partición de K nZ que denota los nodos donde cada jugador juega. Para i = 1, ..., N; Hi es una partición de Ki . Cada h 2 Hi denota un conjunto de información. Para i = 1, ..., N, y k 2 Ki , A(k ) denota las acciones posibles del jugador i en el nodo k. Denotamos un elemento de a 2 A(k ) por ak . Dados k y k 0 2 h 2 Hi debe complirse que A(k ) = A(k 0 ). Abusando un poco del lenguaje de…nimos A(h) = A(k ), k 2 h y denotamos una acción a 2 A(h) por ah .

Alvaro J. Riascos Villegas (Universidad de los Andes y Juegos Quantil) en Forma Extensiva

Marzo 18 de 2010

3 / 36

Juegos en forma extensiva Para i = 1, ..., N, y z 2 Z , ui (z ) denota la utilidad del agente i en caso de que el resultado …nal del juego sea el nodo terminal z. Interpretamos estas funciones de utilidad como funciones de utilidad (instantáneas) de Von Neumann y Morgenstern. Esto no excluye que existan pagos intermedios. Es fácil extender la de…nición al caso en que existen nodos en los que sucede algún evento incierto importante para el juego (i.e., jugadas de la naturaleza). Suponer que la naturaleza solo juega al comienzo del juego es sin pérdida de generalidad. Por ejemplo, en Bagamon (Backgammon), se lanzan los dados muchas veces durante un juego. Supongamos que para la totalidad de un juego se lanzan n veces. Entonces podríamos modelar este juego como uno en el que al inicio la naturaleza juega una de 6n alternativas. Alvaro J. Riascos Villegas (Universidad de los Andes y Juegos Quantil) en Forma Extensiva

Marzo 18 de 2010

4 / 36

Ejemplos (información perfecta)

Información perfecta: porque los conjuntos de información tienen un solo nodo.

Alvaro J. Riascos Villegas (Universidad de los Andes y Juegos Quantil) en Forma Extensiva

Marzo 18 de 2010

5 / 36

Ejemplos (información imperfecta)

Información imperfecta: algunos conjunto de información tiene más de un nodo.

Alvaro J. Riascos Villegas (Universidad de los Andes y Juegos Quantil) en Forma Extensiva

Marzo 18 de 2010

6 / 36

Ejemplos (memoria imperfecta)

Vamos a concentrarnos en juegos con memoria perfecta.

Alvaro J. Riascos Villegas (Universidad de los Andes y Juegos Quantil) en Forma Extensiva

Marzo 18 de 2010

7 / 36

Ejemplos ¿Cuál es nuestra mejor predicción de este juego?

Ahora el objetivo será desarrollar conceptos de equilibrio que exploten las características propias de la descripción de un juego en forma extensiva. Antes de continuar en esa dirección obsérvese que un juego en forma extensiva puede representarse de forma natural como un juego en forma estratégica. Alvaro J. Riascos Villegas (Universidad de los Andes y Juegos Quantil) en Forma Extensiva

Marzo 18 de 2010

8 / 36

Estrategias

De…nition Sea Ai = [ A(h). Una estrategia pura si para el jugador i = 1, ..., N en h 2H i

un juego en forma extensiva Γ es una función si : Hi todo h 2 Hi , si (h) 2 A(h).

Alvaro J. Riascos Villegas (Universidad de los Andes y Juegos Quantil) en Forma Extensiva

! Ai tal que para

Marzo 18 de 2010

9 / 36

Estrategias

Dada una estrategia conjunta (si )i =1,...N ésta induce un camino único a lo largo del árbol comenzando en la raíz y terminando en algún nodo z = ζ (s ) 2 Z . En ocasiones utilizaremos la notación (s1 , ..., sN ) para denotar la estrategia conjunta (si )i =1,...N .

Alvaro J. Riascos Villegas (Universidad de los Andes y Juegos Quantil) en Forma Extensiva

Marzo 18 de 2010

10 / 36

Representación estratégica de un juego en forma extensiva

De…nition (Forma normal o estratégica) Para i = 1, ..., N, sea Si = fsi : Hi

N

! Ai p si (h) 2 A(h)g, s 2 S = Π Si i =1

y de…nimos ζ (s ) 2 Z como el nodo …nal correspondiente al único camino que sobre el árbol de…ne la estrategia conjunta s. Para i = 1, ..., N de…nimos π i (s1 , ..., sN ) = ui (ζ (s1 , ..., sN )). El juego G = f1, ..., N g , fSi gi =1,...,N , fπ i gi =1,...,N se llama la representación normal del juego en forma extensiva.

Alvaro J. Riascos Villegas (Universidad de los Andes y Juegos Quantil) en Forma Extensiva

Marzo 18 de 2010

11 / 36

Ejemplo

El juego en forma extensiva:

Tiene como representación estratégica (o normal): 1n2 N E

F 0,2 -1,-1

C 0,2 1,1

Alvaro J. Riascos Villegas (Universidad de los Andes y Juegos Quantil) en Forma Extensiva

Marzo 18 de 2010

12 / 36

Conceptos de equilibrio

Utilizando la forma normal de un juego en forma extesiva es posible extender los conceptos de equilibrio de los juegos de forma estratégica a juegos en forma extensiva. En el ejemplo anterior el juego tiene dos equilibrios de Nash en estrategias puras. Uno de ellos no es un equilibrio "creíble". La descripción misma de un juego en forma extensiva como una interacción dinámica con conjuntos de información y estructura de árbol motiva otros conceptos de equilibrio. Comenzamos estudiando los juegos en forma extensiva de información perfecta.

Alvaro J. Riascos Villegas (Universidad de los Andes y Juegos Quantil) en Forma Extensiva

Marzo 18 de 2010

13 / 36

Juegos de información perfecta

Los juegos de información perfecta son juegos en forma extensiva en donde los conjunto de información son lo más …nos posibles. Es decir, cada conjunto de información de cada jugador es un solo nodo. El ajedrez que discutiremos con cierto detalle más adelante es un buen ejemplo. El concepto de inducción hacia atrás (backward induction) juega un papel central en los juegos en forma extensiva. Corresponde al concepto de equilibrio perfecto en subjuegos en juegos de información perfecta que estudiaremos más adelante.

Alvaro J. Riascos Villegas (Universidad de los Andes y Juegos Quantil) en Forma Extensiva

Marzo 18 de 2010

14 / 36

Inducción hacia atrás De…nition Decimos que la estrategia conjunta b s = (b s1 , ..., b sN ) es una estrategia de inducción hacia atrás en un juego de información perfecta si puede obtenerse de la siguinete forma: 1

Para cada nodo k que precede inmediatamente a un nodo terminal z sea Ki el conjunto que contiene a k. Esto determina que le corresponde jugar al jugador i.

2

3

b si (k ) maximiza el pago del agente i entre las posibilidades que tiene en ese nodo.

4

Repita los pasos anteriores hasta la raíz del árbol.

Convierta el nodo k en un nodo terminal donde los pagos son los que determina la estrategia b s (k ).

Alvaro J. Riascos Villegas (Universidad de los Andes y Juegos Quantil) en Forma Extensiva

Marzo 18 de 2010

15 / 36

Inducción hacia atrás

Example

Alvaro J. Riascos Villegas (Universidad de los Andes y Juegos Quantil) en Forma Extensiva

Marzo 18 de 2010

16 / 36

Inducción hacia atrás Theorem (Kuhn) Si s es una estrategia de inducción hacia atrás en un juego de información perfecta entonces s es un equilibrio de Nash. La demostración de este teorema es muy sencilla e intuitiva. El converso de este teorema no es cierto. El ejemplo clásico es el problema de entrada de una …rma. En este juego, el equilibrio de Nash que no es creíble, no es una estrategia de inducción hacia atrás. El teorema de Kuhn no a…rma nada sobre la unicidad de las estrategias de inducción hacia atrás. El siguiente ejemplo muestra que las estrategias de inducción hacia atrás no son únicas.

Alvaro J. Riascos Villegas (Universidad de los Andes y Juegos Quantil) en Forma Extensiva

Marzo 18 de 2010

17 / 36

Inducción hacia atrás Este juego tiene dos estrategias de inducción hacia atrás que no son equivalentes en términos de sus utilidades para los jugadores.

Las estrategias f((2, 0) , (y , y , y )) , ((1, 1) , (n, y , y ))g . Alvaro J. Riascos Villegas (Universidad de los Andes y Juegos Quantil) en Forma Extensiva

Marzo 18 de 2010

18 / 36

El juego de ajedrez

Theorem (Zermelo [1912]) En ajedrez se cumple alguna de las siguientes: 1

Las blancas tiene una estrategia ganadora.

2

Las negras tienen una estrategia ganadora.

3

Ambos jugadores pueden forzar como mínimo un empate. Éste es, históricamente, el primer teorema en teoría de juegos (véase Hart [1992], Handbook of Game Theory). Por el teorema de Kuhn el ajedrez tiene por lo menos una estrategia de inducción hacia atrás y por lo tanto, un equilibrio de Nash.

Alvaro J. Riascos Villegas (Universidad de los Andes y Juegos Quantil) en Forma Extensiva

Marzo 18 de 2010

19 / 36

El ajedrez es un juego de suma cero luego todos sus equilibrios tiene el mismo pago. Además cualquier equilibrio de Nash es un equilibrio Maxmin). Por lo tanto la estrategia que garantiza el teorema de Kuhn es una estrategia que garantiza un pago mínimo independientemente de la estrategia de los otros jugadores.

Alvaro J. Riascos Villegas (Universidad de los Andes y Juegos Quantil) en Forma Extensiva

Marzo 18 de 2010

20 / 36

El juego de ajedrez

El problema fundamental es que no se conoce si las blancas o las negras pueden forzar un empate, o ganar. La limitación sin embargo no es teórica sino de tipo computacional. Según el teorema de Zermelo, basta con hacer inducción. El problema con esta estrategia es que el número de jugadas admisibles en el ajedrez ha sido estimado en alrededor de 1020 Estos son números comparables al número de moléculas en el universo.

1043 .

Esta observación llama la atención sobre la importacia de distinguir el concepto de inteligencia entre una puramente conceptual y una de tipo computacional.

Alvaro J. Riascos Villegas (Universidad de los Andes y Juegos Quantil) en Forma Extensiva

Marzo 18 de 2010

21 / 36

Inducción hacia atrás en juegos de información incompleta

El concepto de inducción hacia atrás tiene di…cultades cuando el juego no es de información perfecta como lo ilustra el siguiente ejemplo.

Alvaro J. Riascos Villegas (Universidad de los Andes y Juegos Quantil) en Forma Extensiva

Marzo 18 de 2010

22 / 36

Subjuegos

El concepto de estrategia de inducción hacia atrás no se generaliza de forma inmediata al caso de juegos de información imperfecta. Las estrataegias de inducción hacia atrás en un juego de información perfecta son casos especiales del concepto de equilibrio perfecto en subjuegos que introduciremos a continuación. La generalización requiere la introducción del concepto de subjuego.

De…nition (Subjuegos) Un nodo k de…ne un subjuego Γk si para todo k 0 sucesor de k (en un sentido débil) todos los nodos en A(k 0 ) son sucesores de k. El subjuego Γk consiste del subjuego con raíz inical k.

Alvaro J. Riascos Villegas (Universidad de los Andes y Juegos Quantil) en Forma Extensiva

Marzo 18 de 2010

23 / 36

Subjuegos

Example En el primer juego el único subjuego es el mismo juego. En el segundo, el nodo S no de…ne un subjuego. 3,2

y z

1

w 2 x a

2,3

y 1

0,5

z 4,1

1

b w 2

2,3

x 3,2

Alvaro J. Riascos Villegas (Universidad de los Andes y Juegos Quantil) en Forma Extensiva

Marzo 18 de 2010

24 / 36

Subjuegos

De…nition (Equilibrio perfecto en subjuegos) Una estrategia conjunta s es un equilibrio perfecto en subjuegos si es un equilibrio de Nash de todo subjuego.

Alvaro J. Riascos Villegas (Universidad de los Andes y Juegos Quantil) en Forma Extensiva

Marzo 18 de 2010

25 / 36

Subjuegos

En este juego existen dos equilibrios de Nash en el único subjuego (propio) y dos en subjuegos.

Alvaro J. Riascos Villegas (Universidad de los Andes y Juegos Quantil) en Forma Extensiva

Marzo 18 de 2010

26 / 36

Subjuegos El concepto de equilibrio perfecto en subjuegos es un re…namiento estricto del concepto de equilibrio de Nash (por ejemplo, recordemos el juego de entrada de una …rma). En este juego existe un equilibrio de Nash f(out, r ), (R )g que no es perfecto en subjuegos (en el único subjuego propio el equilibrio de Nash es f(r ), (L)g).

Alvaro J. Riascos Villegas (Universidad de los Andes y Juegos Quantil) en Forma Extensiva

Marzo 18 de 2010

27 / 36

Subjuegos

El concepto de equilibrio perfecto en subjuegos generaliza el concepto de inducción hacia atrás a juegos de información imperfecta.

Theorem En un juego …nito de información perfecta, el conjunto de estrategias de inducción hacias atrás coincide con los equilibrios perfectos en subjuegos.

Alvaro J. Riascos Villegas (Universidad de los Andes y Juegos Quantil) en Forma Extensiva

Marzo 18 de 2010

28 / 36

Subjuegos

En juegos de información imperfecta, no siempre existe un equilibrio perfecto en subjuegos (en estrategias puras):

Esto motiva la introducción de un concepto de equilibrio basado en la noción de estrategias de comportamiento.

Alvaro J. Riascos Villegas (Universidad de los Andes y Juegos Quantil) en Forma Extensiva

Marzo 18 de 2010

29 / 36

Estrategias mixtas y de comportamiento

De…nition (Estrategias mixtas y de comportamiento) Una estrategia mixta en un juego en forma extensiva es una estrategia mixta del juego en su representación normal. Una estrategia de comportamiento es una función γi para el jugador i tal que: 1 2

γi : Hi ! ∆(Ai ).

El soporte de γi (h) está en A(h).

Alvaro J. Riascos Villegas (Universidad de los Andes y Juegos Quantil) en Forma Extensiva

Marzo 18 de 2010

30 / 36

Recordación perfecta

En lo juegos de memoria perfecta las estrategias mixtas y de comportamiento son estratégicamente equivalentes. Esta es un proposición importante que no vamos a demostrar.

Alvaro J. Riascos Villegas (Universidad de los Andes y Juegos Quantil) en Forma Extensiva

Marzo 18 de 2010

31 / 36

Subjuegos

El teorema análogo al teorema de Nash de existencia del equilibrio en estrategias mixtas en el caso de equilibrios en subjuegos es el teorema de Selten: Todo juego …nito de memoria perfecta tiene un equilibrio perfecto en subjuegos en estrategias de comportamiento (y por lo tanto en estrategias mixtas equivalentes del juego en forma normal). Este teorema se demuestra utilizando inducción hacia atrás en cada uno de los subjuegos comenzando con un subjuego que no tenga subjuegos propios. Véase Figura 7.26 de [JR]. Si el juego no es de memoria perfecta, no existe necesariamente un equilibrio perfecto en subjuegos - en estrategias puras o de comportamiento (ejercicio).

Alvaro J. Riascos Villegas (Universidad de los Andes y Juegos Quantil) en Forma Extensiva

Marzo 18 de 2010

32 / 36

Subjuegos No todo equilibrio perfecto en subjuegos es sensato:

Este juego solo tiene un subjuego. Tiene varios equilibrios de Nash (por lo tanto equilibrios perfectos en subjuegos): El jugador 1 juega L y el jugador 2 juega m. Este equilibrio lo sustenta la amenaza 2 de jugar m en caso de poder hacerlo. ¿Es esta amenaza creíble para el jugador 1?

Alvaro J. Riascos Villegas (Universidad de los Andes y Juegos Quantil) en Forma Extensiva

Marzo 18 de 2010

33 / 36

Subjuegos Supongamos que 1 escoge la estrategia M o R. Dependiendo de cual escoja 2 tendrá una mejor respuesta (en el primer caso r y en el segundo caso l). El jugador 2 deberá basar su decisión en la expectativa que él tiene de que el jugador juego la estrategia M o R dado que a él le corresponde jugar. Sean p (x ) y p (y ) las probabilidades que él le asigna a tener que jugar en el nodo x o y .

Alvaro J. Riascos Villegas (Universidad de los Andes y Juegos Quantil) en Forma Extensiva

Marzo 18 de 2010

34 / 36

Subjuegos

Lo que el jugador 2 va hacer es maximizar su utilidad esperada de escoger una de sus tres acciones (l, m o r ). Estas son respectivamente: 4p (y ), 1 y 4p (x ). Sin conocimiento de las expectativas del agente 2, es imposible determinar su estrategia. No es di…cil demostrar (página 308) de [JR] que no importa cuales sean sus expectativas escoger m no es óptimo (basta con observar que la estrategia mixta de jugar con probabilidad 12 , l y 12 , r ; genera una utilidad esperada estrictamente mayor a jugar m). Existe un equilibrio en el que 2 juega m con probabilidad cero y 1 juega L con probabilidad cero (ejercicio).

Alvaro J. Riascos Villegas (Universidad de los Andes y Juegos Quantil) en Forma Extensiva

Marzo 18 de 2010

35 / 36

Subjuegos

En conclución la amenaza m por parte del jugador 2 no es creíble. La razón por la que esto sucede es que el concepto de equilibrio perfecto en subjuegos no impone ninguna restricción sobre el comportamiento del jugador 2 en el conjunto de información que no es alcanzado en el equilibrio de Nash (perfecto en subjuegos) propuesto. La razón es que este conjunto de información no de…ne un subjuego.

Alvaro J. Riascos Villegas (Universidad de los Andes y Juegos Quantil) en Forma Extensiva

Marzo 18 de 2010

36 / 36