Teoria de Juegos Juegos Dinamicos

8/16/2019 Teoria de Juegos Juegos Dinamicos

1/15

Universidad Nacional del Callao - FCE TEORIA DE JUEGOS

JUEGOS DINAMICOS DE INFORMACIÓN COMPLETA

Juego Dinámico

Un juego dinámico, es un juego secuencial (a diferencia de los juegos estáticos), donde los

jugadores adquieren nueva información, respecto a lo realizado por los demás jugadores,mientras el juego se desarrolla. En los juegos dinámicos la estructura secuencial del juego tiene

relevancia, es por ello que se recomienda utilizar la forma extensiva para poder analizar un

juego dinámico.

Juego de informci!n com"#e$

Al igual que en los juegos estáticos de información completa, tanto la estructura del juego, la

racionalidad de los jugadores los futuros pagos, de acuerdo a las estrategias utilizadas, son de

conocimiento com!n.

Un juego dinámico de información completa puede ser representado mediante la forma normal

o estrat"gica, sin em#argo al utilizar esta representación podemos encontrar los equili#rios de

$as%, tal como se %a estudiado en la parte de juegos estáticos de información completa. &in

em#argo, en el caso de juegos dinámicos (como se dijo en la definición de juego dinámico)

resulta más apropiado contar con una representación del juego que muestre la estructura

secuencial del juego. 'a representación en su forma extensiva de un juego incorpora

explcitamente la estructura secuencial. Utilizando esta representación de los juegos dinámicos

podemos encontrar lo que se conoce como Equilibrio de Nash perfecto en subjuegos , el cual es

el concepto de solución en juegos dinámicos (a diferencia de los Equili#rios de $as% en juegos

estáticos) que será explicado más adelante.

E%em"#o &' Di#em de# Pri(ionero )diferenci en$re %uego( e($á$ico( * dinámico(+

ecordemos el enunciado del dilema del prisionero, el cual se representa en su forma normal de

la siguiente manera

*+

NC C

*

NC (2,2) (0,3)

C (3,0 ) (1,1 )

-ara poder representarlo en su forma extensiva utilizaremos el diagrama de ár#ol. -ara este caso

como a %emos entrado a la parte de juegos dinámicos %aremos una distinción en la forma

extensiva de representar un juego estático dinámico, para ello representamos el dilema del

prisionero en su forma extensiva donde

-anel A /ilema del prisionero en juegos estáticos

-anel 0 /ilema del prisionero en juegos dinámicos. -ara esta versión del

dilema del prisionero, tenemos que el jugador elige primero su acción, la cual es

o#servada por el jugador + antes de que "l de#a elegir su acción. Es por ello que se les

conoce como juegos secuenciales.

A continuación la forma extensiva del dilema del prisionero

Página 1 de 1

Panel A! J"ego es#á#ico Panel $! J"ego diná%ico


2/15


'as lneas punteadas del panel A que unen los nodos de decisión del jugador + nos %ace

referencia a que el juego es un juego estático, donde el plan de acción se toma al inicio del

juego (por am#os jugadores) mientras que el juego representado en el panel 0 nos muestra la

secuencialidad del juego, donde el jugador + decidirá qu" estrategia usar dependiendo de la

estrategia tomada por el jugador .

Diferencia entre acción y estrategia

En los juegos estáticos vistos anteriormente no exista diferencia entre acción estrategia. 'a

estrategia de un jugador consista en la elección de una acción. &in em#argo, en los juegos

dinámicos una estrategia es mu diferente a una acción. 'os jugadores pueden ir tomando

distintas acciones a lo largo del juego. 'a estrategia de un jugador es un plan contingente

completo de acción.

Re"re(en$ci!n e,$en(i-

'a definición matemática de un juego en su forma extensiva consiste en la descripción de los

elementos que lo componen

. Un conjunto finito de jugadores N .

Un conjunto finito de acciones A=×i∈ N A i .

Un conjunto finito de nodos X .

A continuación se utiliza el ejemplo anterior donde se representan los nodos los cuales están

encerrados con un crculo rojo

Página & de 1

J 2J 2

J 1

J 1

J 2

C N

N C N C

(22) (03) (30) (11)(11)(30)(03)(22)

C N C N

N C

J 2


3/15


+. Una función p: X que especifica en !nico inmediato predecesor de cada nodo.

1a dos tipos de nodos

• Nodos terminales T ={ x∈ X } que no pertenecen a ning!n jugador, sino que

representan los resultados del juego a los que se asocian los pagos

correspondientes de cada jugador.

• 'os demás nodos X ∖T son los nodos de decisión, donde alg!n jugador es

requerido a tomar una acción. /entro de ellos está el nodo inicial x

0 donde el

juego empieza.

2. Una funciónγ : X ∖{ x0 }→ A que asigna la acción que lleva %acia cada nodo (no

inicial) x desde su inmediato predecesor.

3. Una colección de conjuntos de información H una función H : X ∖T → H que

a cada nodo de decisión x le asigna un conjunto de información h= H ( x )∈ H .

4. Una función I : H → N que a cada conjunto de información le asigna un jugador. El

conjunto de información de i se denota H i={h∈ H : i= I (h ) } .'a interpretación de un conjunto de información es que un jugador no puede distinguir

en qu" nodo está entre los nodos que pertenecen a un mismo conjunto de información

cuando elige una acción cualesquiera de ellos. -or lo tanto, se requiere que todos los

nodos de decisión asignados a un mismo conjunto de información tengan las mismas

acciones disponi#les.

Página ' de 1


J 2

J 2

J 1

J 1

J 2

C N

N C N C

(22) (03) (30) (11)(11)(30)(03)(22)

C N C N

N C

J 2


4/15


As, podemos definir el conjunto de acciones disponi#les en cada conjunto de

información h : A (h )= {a∈ A : a∈ A ( x ) para x∈h }

A continuación se utiliza el ejemplo anterior donde se se5alan los conjuntos de información del

jugador +

6. Una colección de pagos v={v1 (∙ ) , … , vn (∙ ) } que a cada jugador le asigna un pago en

cada nodo terminal v i :T → R .

-or lo tanto, podemos definir un juego dinámico en su forma extensiva por la colección de todos

sus elementos Γ E= ⟨ X , A , N , p ( ∙ ) , γ ( ∙ ) , H , H ( ∙ ) , I ( ∙ ) , v ⟩ .

&e %an asumido N A finitos ( por lo tanto X finito), pero la definición se puede

extender directamente al caso más general. Un juego dinámico se dice finito si X es finito

(que implica N A finitos)

Información perfecta e imperfecta

Un juego extensivo es de información perfecta si cada conjunto de información contiene un

!nico nodo. /e lo contrario, es un juego de información imperfecta. As, el juego del dilema del

Página ( de 1


J 2J 2

J 1

J 1

J 2

C N

N C N C

(22) (03) (30) (11)(11)(30)(03)(22)

C N C N

N C

J 2


5/15


prisionero que vimos anteriormente (-anel A) es un juego de información imperfecta, mientras

que la versión del juego en su forma dinámica (-anel 0) es un juego de información perfecta.

E($r$egi Pur

Definición

Una estrategia pura para el jugador i es una función si : H i → A tal que

si ( h )∈ A (h ) ,∀h∈ H i . Al conjunto de estrategias puras de i lo denotamos por S i .

Es importante enfatizar que una estrategia especifica una acción para todos y cada uno de los

conjuntos de información del jugador. Ello incluso si de acuerdo a la estrategia alg!n conjunto

de información no va a ser alcanzado en el juego.

En concreto, sean h h ' dos conjuntos de información que pertenecen al jugador i

donde h ' se encuentra en una etapa posterior en el juego que h . Una estrategia del

jugador i de#e asignar una acción a h ' aun cuando la acción especificada en h

impida que se llegue a h ' durante el juego. 'a idea detrás de una estrategia en un juego

dinámico es que de#e especificar qu" %ara el jugador en cada nodo de decisión del juego. Es

por ello que una estrategia en un juego dinámico es un plan contingente completo de acción.

/os planes contingentes completos de acción que se diferencian sólo en una acción constituen

dos estrategias diferentes. -or lo tanto, es com!n que los jugadores tengan muc%as posi#les

estrategias en juegos dinámicos. Especficamente, si | A (h )| es el n!mero de acciones

disponi#les del jugador i en el conjunto de información h , entonces el n!mero de

estrategias puras de dic%o jugador es

|Si|=∏h∈ H

i

| A (h )|

E%em"#o &. Di#em de# Pri(ionero )e($r$egi( en %uego( en (u form e,$en(i-+

ecordemos el enunciado del dilema del prisionero

Página de 1


J 2J 2

J 1

J 1

J 2

C N

N C N C

(22) (03) (30) (11)(11)(30)(03)(22)

C N C N

N C

J 2


6/15


En el juego del dilema del prisionero (-anel A), cada jugador tiene sólo un conjunto de

información (aunque el jugador tiene un !nico nodo de decisión en el suo el jugador + tiene

dos nodos de decisión), en el cual dos acciones están disponi#les NC C . &us

estrategias de#en especificar qu" acción tomar en dic%o conjunto de información. El conjunto

de todas las estrategias puras posi#les de cada jugador son entonces S1= { NC , C }

S2= { NC , C } . 7emos que estos son iguales a los conjuntos de acciones de los jugadores

A1= { NC , C } A2= { NC , C }. Es en este sentido que mencionamos anteriormente que

no %a diferencia práctica entre acción estrategia en los juegos estáticos.

En cam#io, el juego del dilema del prisionero presentado en el -anel 0 es un juego dinámico.

En este caso el jugador sigue teniendo un !nico conjunto de información su conjunto de

estrategias puras sigue siendo S1= { NC , C }. &in em#argo, el jugador dos tiene dos

conjuntos de información aqu"l al que se llega luego de que el jugador juegue NC

aqu"l al que se llega luego de que el jugador juegue C . Una estrategia pura del jugador +

de#e especificar qu" acción va a tomar en cada uno de sus conjuntos de información. /efinimos

una estrategia pura del jugador + como un vector ( X , Y ) , donde X indica la acción a

tomar si el jugador juega NC e Y indica la acción a tomar si el jugador juega C .

El conjunto de estrategias puras del jugador + será entonces

S1=

{( NC , NC ) , ( NC , C ) , (C , N C ) , (C , C ) } . El n!mero de estrategias puras del jugador +es 3, que es lo que se o#tiene al calcular

|S2|=∏h∈ H

2

| A (h )|=2 × 2=4

E($r$egi Mi,$

Definición

Página ) de 1


7/15


Una estrategia mixta i para el jugador i es (al igual que para juegos estáticos) una

distri#ución de pro#a#ilidad so#re su conjunto de estrategias purasS i .

Representación Normal de Juegos Extensivos

&iempre es posi#le reducir un juego en su forma extensiva a un juego en su forma normal o

estrat"gica, donde los pagos están asociados a perfiles de estrategias en lugar de a nodos

terminales. Un perfil de estrategias puras lleva a un !nico nodo terminal. &ea ! s∈T el !nico

nodo terminal asociado con el perfil de estrategias puras s . Entonces

"i (s )=vi (! s ) ,∀ i∈ N . Asimismo, el pago esperado asociado al perfil de estrategias mixtas

es

# i ( )=∑s∈ S (∏ $∈ N $ ( s $ ))vi ! s

En la práctica, veremos que para juegos dinámicos es muc%as veces más conveniente considerar

las estrategias de comportamiento de los jugadores en lugar de sus estrategias mixtas.

E($r$egi de Com"or$mien$o

Definición

Una estrategia de comportamiento i ( A (h) ) para el jugador i es una distri#ución de

pro#a#ilidad so#re sus acciones disponi#les en cada uno de sus conjuntos de información

h∈ H i . En otras pala#ras, asumimos que un jugador asigna pro#a#ilidades a sus decisiones

en cada uno de sus conjuntos de información, en lugar de asignar pro#a#ilidades a sus

estrategias puras. Am#as definiciones son equivalentes #ajo el supuesto, que vamos a mantener,

que los jugadores tienen 8memoria perfecta9 un jugador no puede olvidar lo que %izo en una

etapa anterior del juego (este resultado es conocido como el teorema de :u%n).

CONCEPTOS DE SOLUCIÓN

E/UILI0RIO DE NAS1

ecordemos la definición de equili#rio de $as% dada anteriormente un equili#rio de $as% es un

perfil de estrategias ¿

tal que para cada jugador i

# i ( i¿

, −i¿ )% # i ( i , −i

¿ ) ,∀ i∈ &i .

Sendero de E2ui#i3rio

Página * de 1


8/15


9/15


J 1

AAA 2,0 1,1 0,2

AAR 2,0 1,1 0,0

ARA 2,0 0,0 0,2

ARR 2,0 0,0 0,0

RAA 0,0 1,1 0,2

RAR 0,0 1,1 0,0

RRA 0,0 0,0 0,2

RRR 0,0 0,0 0,0


10/15


no sea óptimo para *, * jugara rec%azar si *+ juega (1−1 ) . Este nodo no está en el sendero

de equili#rio por lo que sólo constitue una 8amenaza9 de *. &in em#argo, es una amenaza no

cre#le porque, de darse el caso, * actuara de manera óptima aceptando la propuesta (1−1 )

de *+. As *+ preferira jugar (1−1 ) o#tener en lugar de jugar (0−2 ) o#tener 0 .

-or su puesto, *+ puede realizar esta misma deducción por lo tanto, no esperaramos que el

equili#rio de $as% ( ARR , (0−2 ) ) se d" en realidad.

Analicemos otro de estos E$, por ejemplo ( ARA , (0−2 ) )

J 2

=Es este equili#rio secuencialmente racional>

-ara encontrar los equili#rios de $as% que son secuencialmente racionales podemos aplicar el

procedimiento conocido como inducción hacia atr!s. -osteriormente vamos a explicar

detalladamente este procedimiento. -or a%ora, sólo lo ilustramos aplicándolo al ejemplo

anterior. Empezamos determinando las acciones óptimas de * en los !ltimos nodos de decisión

A luego de (2−0 ) , A luego de (1−1 ) tanto A como R luego de

(0−2 ) . En seguida vamos %acia atrás determinamos qu" es lo óptimo para *+ en el primer

nodo de decisión dado que anticipa correctamente lo que óptimamente va a %acer * en cada

uno de los nodos finales de decisión. ;omo luego de (0−2 ) tanto A como R son

óptimos para *, de#emos tratar cada uno de estos casos por separado. En caso de que * juegue

A luego de (0−2 ) , lo óptimo para *+ es jugar (0−2 ) . En caso de que * juegue

R luego de

(0−2 ), lo óptimo para *+ es jugar

(1−1 ). As, vemos que en el ejemplo

previo sólo %a dos E$ secuencialmente racionales

Página 1 de 1

(1−1 ) (0−2 )(2−0 )

J 1

J 1J 1

R R R A A A

0 12 000


11/15


EN = ( AAA , (0−2 ) ) , ( AAR , (1−1 ) )}

En #ase a estos resultados podemos identificar tres posi#les casos de acuerdo a las acciones

óptimas para el jugador

. &iempre Acciones de color celeste

+. ;aso Acción de color verde (En caso de que * juegue A luego de (0−2 ) , lo

óptimo para *+ es jugar (0−2 ) )

2. ;aso + Acción de color naranja (En caso de que * juegue R luego de (0−2 ) , lo


/e igual manera podemos identificar los casos para el jugador + de acuerdo a sus acciones

óptimas

. ;aso Acción de color verde (En caso de que * juegue A luego de (0−2 ) , lo


+. ;aso + Acción de color naranja (En caso de que * juegue R luego de (0−2 ) , lo


El juego en su forma extensiva quedara de la forma

J 2

-or lo tanto los equili#rios de $as% secuencialmente racionales son los a %allados.

1emos visto cómo se puede aplicar el principio de racionalidad secuencial en un ejemplo de un

juego finito de información perfecta. El concepto de solución que incorpora este principio de

Página 11 de 1

(1−1 ) (0−2 )(2−0 )

J 1

J 1J 1

R R R A A A

0 12 001


12/15


manera más general es conocido como equilibrio de Nash perfecto en "ubjuegos Antes de

presentar este concepto, necesitamos primero definir qu" es un su#juego.

Su3%uego

/ado un juego en forma extendida, un su#juego es cualquier su#conjunto de nodos queconstitue un juego por derec%o propio. Ello significa que de#e satisfacer dos condiciones

. ;omienza con un conjunto de información que contiene un !nico nodo contiene todos

los sucesores (inmediatos su#siguientes) de este nodo. El su#juego no contiene otros

nodos además de "stos.

+. &i el su#juego contiene el nodo x , entonces contiene todos los nodos que están en el

mismo conjunto de información que x . (Es decir, no %a conjuntos de información

8rotos9)

Página 1& de 1


J 2J 2

J 1 J 1

J 2

C N

N C N C

(22) (03) (30) (11)(11)(30)(03)(22)

C N C N

N C

J 2


13/15


-odemos identificar que el -anel A (juego estático) cuenta con un !nico su#juego que es el

juego mismo. El panel 0 (juego dinámico) cuenta con tres su#juegos el juego mismo cada

su#juego que comienza en un nodo de decisión del jugador +.

-uesto que un su#juego es un juego en s mismo podemos aplicarle los conceptos de solución

usuales. -recisamente eso es lo que %ace el equili#rio de $as% -erfecto en &u#juegos.

E2ui#i3rio de N(6 Perfec$o en Su3%uego(

/ado un juego en su forma extensiva, un perfil de estrategias ¿

es un equili#rio de $as%

-erfecto en &u#juegos (E$-&) si induce un equili#rio de $as% (E$) en todos los su#juegos del

juego (incluendo el juego original).

$otese que si ¿

es un E$-&, entonces tam#i"n es un E$ (dado que el juego original

tam#i"n es un su#juego). -ero no todo E$ es un E$-&. -or lo tanto, el conjunto de los E$-& es

un su#conjunto del conjunto de los E$ { EN(S }⊆ { EN } . As, el E$-& nos #rinda una

predicción más precisa so#re los resultados que ca#en esperar en un juego dinámico.

El procedimiento de inducción %acia atrás que ilustramos previamente es clave porque #rinda un

m"todo para encontrar los E$-&. /ado que en cada su#juego los jugadores eligen sus acciones

óptimas anticipando correctamente las acciones óptimas de los demás, a ning!n jugador le

conviene desviarse de su estrategia , por lo tanto, estamos encontrando un E$ en cada

su#juego.

/etallamos los pasos del m"todo de inducción %acia atrás para juegos finitos de información

perfecta

. Encontrar las acciones óptimas en los !ltimos nodos de decisión.

+. Encontrar las acciones óptimas en los pen!ltimos nodos de decisión dado que los

jugadores anticipan correctamente las acciones óptimas que van a ser tomadas en los

!ltimos nodos de decisión.

2. As sucesivamente %asta llegar al nodo inicial.

&i nunca se encuentra más de una acción óptima en cada nodo, entonces el procedimiento

#rinda un !nico E$-&. En caso contrario, todos los E$-& se encuentran repitiendo el

procedimiento para cada acción óptima identificada.

-ara esta categora de juegos, contamos con el siguiente teorema

Teorem de 7erme#o


14/15


15/15

Documents

Teoria de Juegos Juegos Dinamicos