Story Transcript
Inducción hacia adelante, señalización y reputación 14.126 Teoría de juegos Sergei Izmalkov y Muhamet Yildiz
Mapa de ruta 1. Inducción hacia adelante 2. Juegos de señalización 1. equilibrio secuencial 2. criterios intuitivos
3. Reputación 1. La paradoja de los grandes almacenes, juegos finitos repetidos 2. Juego del ciempiés con información incompleta 3. Juego repetido finito de entrada diferida con información incompleta.
1
Inducción hacia adelante
La batalla de los sexos con opciones exteriores 1
2,2
B
B 3,1
S 0,0
S
0,0
1,3
2
Inducción hacia adelante • Hay que interpretar las acciones como resultados de elección consciente incluso las que están fuera del curso normal. • Criterio intuitivo • Teorías falsas
Creencia firme en la racionalidad En cualquier historial del juego, se asume que cada agente es racional si es posible. (Esto es, si hay dos estrategias s y s’ de un jugador i que son coherentes con un historial del juego, y si s es estrictamente dominada pero s’ no, en este historial ningún jugador j cree que i juega s.)
3
Ejemplos 1
1
2
2 5 0
2 0
1
1 1 2
1 2 3 1
3 1
2 3
2 3
Quemar dinero 0
1
D
BB
B
B 3,1
S 0,0
B
B 2,1
S -1,0
S
0,0
1,3
S -1,0
0,3
BS
SB
SS
0B 0S DB DS
O T
H E
R
4
Tabla para el juego de subasta Ui = 20(2+2minjbidj - bidi)
min
1
2
3
1
60
-
-
2
40
80
-
3
20
60
100
bid
Equilibrio Nash del juego de subasta • 3 equilibrios: s1 = todos juegan 1; s2 = todos juegan 2; s3 = todos juegan 3. • Asuma que los jugadores tiemblan con la posibilidad de que ε < 1/2 y juegan cada estrategia no planeada w.p. ε/2. p. ej. w.p. ε/2, piensan que se va a jugar otro equilibrio - s3 es un equilibrio si y sólo si - s2 es un equilibrio si y sólo si - s1 es un equilibrio si y sólo si
5
1 0.8 0.6 0.4 0.2 0.047
0 -0.2
(1-ε /2 )n-1/2
-0.4 -0.6 -0.8 -1
(1-ε )n+(1 ε /2 )n-1 0
0.032
0.05
0.1
0.15
0.2
Juego de subasta con tarifa de entrada Cada jugador decide primero si jugar en el juego de subasta (E o X); si juega, ha de pagar una tarifa p > 60.
min
1
2
3
1 2 3
60 40 20
80 60
100
Bid
Por cada m =1,2,3, ∃ SPE: (m,m,m) se juega en la subasta y los jugadores juegan si y sólo si 20(2+m) ≥ p. Inducción hacia adelante: cuando 20(2+m) < p, (Em) es estrictamente dominada por (Xk). Tras E, ningún jugador asignará probabilidad positiva a una puja mínima ≤ m. Equilibrio FI:
(Em,Em,Em) donde 20(2+m) ≥ p. ¿Y si hay una licitación antes de la puja?
6
Señalización
Modelo • Jugadores: (S)ender, (R)eceiver 1. La naturaleza selecciona t de T – la distribución de probabilidad es π 2. S observa t, y envía mensaje m de un conjunto M; 3. R observa m – pero no t – y realiza la acción a; 4. S obtiene US(t,m,a) y R obtiene UR(t,m,a). Esto es sabido por todos.
7
Cerveza - Quiche 0 1
quiche
cerveza
1 1
{.1}
2 0
3 0
tw
1 0
0 0
ts cerveza {.9}
quiche 2 1
3 1
Buen equilibrio 0 1
quiche
cerveza
{.1}
2 0
3 0
tw
1 0
0 0
ts cerveza {.9}
3 1
1 1
quiche 2 1
8
Mal equilibrio 0 1
1 1
quiche
cerveza
{.1}
2 0
3 0
tw
1 0
0 0
ts cerveza {.9}
quiche 2 1
3 1
Cerveza - Quiche - M 0 1 $1M 1000002 -999999 2 0
$1M
{.1}
tw
1 0 1000003 - $1M 1000000 3 1
quiche
cerveza
1 1
0 0 0
ts cerveza {.9}
1000003 3 1000000
quiche
$1M
1000002 2 -999999 1
9
Cho -- Kreps • T(m); M(t); A(m) • El conjunto de acción es finito; • ρ(m;t) = probabilidad de que t envíe m •
φ (a;m)
= probabilidad de que R elija a,
• • Para el subconjunto I de T, • MBR
Equilibrio secuencial • Creencias:
µ(t │m) =
•
está
maximizada en m. • φ (.;m) está en MBR(µ(.|m),m)
10
Prueba de un equilibrio • U*(t) = utilidad esperada de tipo t en equilibrio; 1. Escoja un criterio, diciendo que el mensaje fuera de equilibrio particular (OEM) no se puede enviar por algún tipo t. Diga también, que a no se tomará en respuesta a m si a no está en BR(T(m),m). Itere. [Ts(m)] 2. Para cada OEM m, considere todas las respuestas de equilibrio secuenciales de R a m en el juego original. Todos ellos son racionales secuencialmente, dado Ts(m). Si no, FALLO.
Dominancia • Para cada OEM m, elimine t si ∃ m’ s.a.
0 0
m’
0 0
m’
m {.9}
{.1}
a2
tw ts
a1
m
a1 a2
-1 0 1 1 -1 1 -1 0
11
Dominancia de equilibrio & criterio intuitivo Dominación de equilibrio: ∀ OEM m, elimina (t,m) si
Criterio intuitivo: ∀ OEM m, define
entonces el equilibrio no cumple el criterio de intuición.
Mal equilibrio 0 1
quiche
cerveza
{.1}
2 0
3 0
tw
1 0
0 0
ts cerveza {.9}
3 1
1 1
quiche 2 1
12
Buen equilibrio 0 1
1 1
quiche
cerveza
{.1}
2 0
3 0
tw
1 0
0 0
ts cerveza {.9}
quiche 2 1
3 1
Cerveza - Quiche - M 0 1 $1M cerveza 1000002 -999999 2 0 1 0 1000003 - $1M 1000000 3 1
quiche {.1}
tw
$1M
n
1000003 3 1000000 0
0 0
ts cerveza {.9}
1 1
quiche
$1M
1000002 2 -999999 1
13
Reputación
Entrada diferida 1 X
Enter
2
Acc.
(1,0)
Fight (0,1)
(-1,-1)
14
Entrada diferida, repetida dos veces, muchas veces Enter 2 Acc. 1
1
Fight X
X Acc. 2 Enter 1
1,1
Fight
X
0,2
2,0
Fight
(1,1) 0,-1 Enter 2 Acc.
1
X
-1,0
Enter 2 Acc.
0,-1
Fight -1,0
(-2,-2)
¿Qué ocurriría si se repitiese n veces?
Repetida dos veces PD 1
D
C
2 D
C 1
C 10 10
1 D 2
C
1
1 D
2
D C
D C
5 11
6 6
0 12
5 11
C
D
C
D C 11 5
D
C
6 6
D 2
2 D
1 7
C
C 11 5
D
C
D
C
D C D
6 6
12 0
7 1
6 6
1 7
7 1
2 2
¿Qué ocurriría si T = {0,1,2,…,n}?
15
Juego del ciempiés 1
2
1
2
1
2
98 98
97 100
99 99
98 101
1
100 100
… 1 1
0 3
2 2
Juego del ciempiés – con duda
{.999} 1
197
5
4
3
2
1
2
2
1
2
1
2
∝5
=n
∝1
∝3
100 100
… 1 1 {.001}
96 99
0 3 1
2
98 98
97 100
99 99
98 101
2
1
2
1
2
0 99
-1 98
0 100
-1 99
0 101
0 100
… -1 1
0 3
16
Hechos sobre el ciempiés • Cada conjunto de información de 2 se alcanza con probabilidad positiva. • 2 siempre pasa con probabilidad positiva. • Si 2 estrictamente prefiere pasar en n, entonces - 1 debe preferir estrictamente pasar en n+1, - 2 debe preferir estrictamente pasar en n+2, - su posterior en n es su anterior.
• Por cualquier n > 2, 1 pasa con probabilidad positiva. Si 1 pasa w/p 1 en n, entonces el 2 posterior en n-1 es su anterior.
Juego del ciempiés – con duda
{.999} 1
197
5
4
3
2
1
2
2
1
2
1
2
96 99
98 98
97 100
99 99
98 101
=n 100 100
… 1 1 {.001}
0 3 1
2
∝5 2
1
∝3 2
1
∝1 2
0 99
-1 98
0 100
-1 99
0 101
0 100
… -1 1
0 3
17