title page ¡juegos diferenciales de todos modos! · 1seny,(1.3) y˙ p = w 1 cosy,(1.4) donde f y y...
TRANSCRIPT
Home Page
Title Page
Contents
JJ II
J I
Page 1 of 35
Go Back
Full Screen
Close
Quit
¿Cooperación o Competencia?
¡Juegos diferenciales de todos modos!
José Daniel López Barrientos
Facultad de Ciencias Actuariales
Universidad Anáhuac México
Agosto 17, 2017
Home Page
Title Page
Contents
JJ II
J I
Page 2 of 35
Go Back
Full Screen
Close
Quit
Índice
1. Juegos competitivos 8
1.1. Juegos diferenciales . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2. Ecuaciones Diferenciales Estocásticas . . . . . . . . . . . . . . . . 12
1.3. JJDDEE con modos múltiples . . . . . . . . . . . . . . . . . . . . . 16
1.4. Un resultado clásico . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2. ¡Júntense! 22
2.1. El Principio de racionalidad grupal . . . . . . . . . . . . . . . . . 23
2.2. Racionalidad individual y consistencia de los subjuegos . . . . . 27
3. El procedimiento de asignación de recompensas instantáneas 31
Home Page
Title Page
Contents
JJ II
J I
Page 3 of 35
Go Back
Full Screen
Close
Quit
Home Page
Title Page
Contents
JJ II
J I
Page 4 of 35
Go Back
Full Screen
Close
Quit
Home Page
Title Page
Contents
JJ II
J I
Page 5 of 35
Go Back
Full Screen
Close
Quit
Figura 1: Twilight Struggle (https://boardgamegeek.com/boardgame/
12333/twilight-struggle) y Street Fighter II.
Home Page
Title Page
Contents
JJ II
J I
Page 6 of 35
Go Back
Full Screen
Close
Quit
Home Page
Title Page
Contents
JJ II
J I
Page 7 of 35
Go Back
Full Screen
Close
Quit
Home Page
Title Page
Contents
JJ II
J I
Page 8 of 35
Go Back
Full Screen
Close
Quit
1. Juegos competitivos
Velocidad caminar trotar correr
caminar 4 5 6
trotar 3 4 5
correr 1 2 3matriz de pagos para jugador renglón:
A =
4 5 6
6 8 10
3 6 9
.
Home Page
Title Page
Contents
JJ II
J I
Page 9 of 35
Go Back
Full Screen
Close
Quit
Definición 1.1. Sea V`(π1, π2) el pago que recibe el `-ésimo jugador (` = 1, 2) en un
juego de dos jugadores que usan las estrategias π1 y π2, respectivamente. Decimos que
el par (π1∗, π2∗) es un equilibrio de Nash para el juego en cuestión si
V1(π1, π2∗) ≤ V1(π1∗, π∗2) y V2(π1∗, π2) ≤ V2(π1∗, π2∗).
Asimismo, llamamos a V1(π1∗, π2∗) y V2(π1∗, π2∗) los valores del juego para el ju-
gador 1 y el jugador 2, respectivamente. En el caso de un juego se suma-cero, tenemos
que V1(π1∗, π2∗) = −V2(π1∗, π2∗) := V(π1∗, π2∗) y decimos que esta cantidad es
el valor del juego.
Home Page
Title Page
Contents
JJ II
J I
Page 10 of 35
Go Back
Full Screen
Close
Quit
1.1. Juegos diferenciales
Home Page
Title Page
Contents
JJ II
J I
Page 11 of 35
Go Back
Full Screen
Close
Quit
Posiciones:
xE = w1senφ, (1.1)
yE = w1 cos φ, (1.2)
xP = W1senψ, (1.3)
yP = W1 cos ψ, (1.4)
donde φ y ψ son los ángulos que forman los vectores E y P, respectivamente,
con el eje de las abscisas.
Observación 1.2. Las ecuaciones (1.1)-(1.4) son la razón por la que la clase de los
juegos que admiten que las variables de estado sean descritas por un sistema de ecuacio-
nes diferenciales se llamen juegos diferenciales. En ese juego, las estrategias para los
jugadores son φ y ψ. Note que, en efecto, φ y ψ pueden escribirse en términos de las
variables de estado (xE, yE) y (xP, yP).
Home Page
Title Page
Contents
JJ II
J I
Page 12 of 35
Go Back
Full Screen
Close
Quit
1.2. Ecuaciones Diferenciales Estocásticas
dS(t)S(t)
= µdt.
Home Page
Title Page
Contents
JJ II
J I
Page 13 of 35
Go Back
Full Screen
Close
Quit
dS(t)S(t)
= µdt + σdW(t). (1.5)
Home Page
Title Page
Contents
JJ II
J I
Page 14 of 35
Go Back
Full Screen
Close
Quit
Ejemplo 1.3. Dos inversionistas compiten eligiendo estrategias
de inversión, uno para maximizar cierto índice de rendimiento, y
otro para minimizarlo. Si suponemos que los agentes tienen a su
disposición dos activos, uno riesgoso, cuyo precio evoluciona de
acuerdo con (1.5), y uno sin riesgo, cuyo precio se actualiza según
la ecuación diferencial ordinaria dB(t)B(t) = rdt, donde r > 0 es la
tasa libre de riesgo, entonces podemos definir las riquezas de los
jugadores en términos de estas cantidades.
Home Page
Title Page
Contents
JJ II
J I
Page 15 of 35
Go Back
Full Screen
Close
Quit
Solución. Sea u`(t) la proporción de la fortuna del `-ésimo
inversionista que se destina al activo riesgoso en el tiempo
t ≥ 0 (naturalmente, ` = 1, 2). Defina x`(t) como la riqueza
del i-ésimo jugador en el tiempo t ≥ 0, entonces la riqueza
del `-ésimo jugador obedece a la dinámica
dx`(t) = u`(t)x`(t)dS(t)S(t)
+ (1 − u`(t))x`(t)dB(t)B(t)
= x`(t) [r + u`(t)(µ − r)dt + u`(t)σdW(t)] ,
con x(0) = x0.
Home Page
Title Page
Contents
JJ II
J I
Page 16 of 35
Go Back
Full Screen
Close
Quit
1.3. JJDDEE con modos múltiples
bE(~x, 1, φ, ψ) =
w1sen[φ(xP, yP)],
w1 cos[φ(xP, yP)],bP(~x, 1, φ, ψ) =
W1sen[ψ(xE, yE)],
W1 cos[ψ(xE, yE)].
bE(~x, 2, φ, ψ) =
w2sen[φ(xP, yP)],
w2 cos[φ(xP, yP)],bP(~x, 2, φ, ψ) =
W2sen[ψ(xE, yE)],
W2 cos[ψ(xE, yE)].
Home Page
Title Page
Contents
JJ II
J I
Page 17 of 35
Go Back
Full Screen
Close
Quit
Caracterizamos el cambio entre un modo y otro con una cadena de Markov
a tiempo continuo Θ(•) := {θ(t) : t ≥ 0}. Para efectos de ilustración, la matriz
de transición de este proceso está dada por
P(t) =12
1 + e−2λt 1 − e−2λt
1 − e−2λt 1 + e−2λt
.
No es difícil demostrar que el generador infinitesimal del proceso Θ(•) está dado
por
Q =
−λ λ
λ −λ
.
Home Page
Title Page
Contents
JJ II
J I
Page 18 of 35
Go Back
Full Screen
Close
Quit
Haremos patente la incertidumbre de un jugador sobre la posición del otro
(de ahí la necesidad de usar radares) sumando un término no-nulo de difusión
a los coeficientes de deriva. Este número dependerá del modo en que se en-
cuentre nuestro sistema. Así, el cambio en la posición de los jugadores quedará
dererminado por el sistema siguiente de ecuaciones diferenciales estocásticas:
dxE(t) = wθsen[φ(xP, yP)]dt + σθdW(t), (1.6)
dyE(t) = wθ cos[φ(xP, yP)]dt + σθdW(t), (1.7)
dxP(t) = Wθsen[ψ(xE, yE)]dt + σθdW(t), (1.8)
dyP(t) = Wθ cos[ψ(xE, yE)]dt + σθdW(t). (1.9)
Aquí, θ = 1, 2 representa el modo en el que se encuentra el sistema, y σθ > 0
simboliza la dificultad que enfrenta cada jugador para rastrear a su oponente.
Home Page
Title Page
Contents
JJ II
J I
Page 19 of 35
Go Back
Full Screen
Close
Quit
1.4. Un resultado clásico
En general:
d~x(t) = b(x(t), θ(t), u1(t), u2(t))dt + σ(~x(t), θ(t))dW(t), (1.10)
P[θ(t + ∆t) = j|θ(t) = i; ~x(s), θ(s) para s ≤ t] = λu1(t),u2(t)ij (~x(t))∆t + o(∆t),(1.11)
∑j∈S
λu1(t),u2(t)ij (~x(t)) = 0. (1.12)
Home Page
Title Page
Contents
JJ II
J I
Page 20 of 35
Go Back
Full Screen
Close
Quit
Y el índice de rendimiento del `-ésimo jugador en el juego que inicia en el
estado (~xs, θs) es:
V`(~xs, θs, π1, π2) = Eπ1,π2
~xs,θs
[∫∞s
e−δ(t−s)r`(~x(t), θ(t), π1t , π2
t )dt]
. (1.13)
Home Page
Title Page
Contents
JJ II
J I
Page 21 of 35
Go Back
Full Screen
Close
Quit
Teorema 1.4. (cf. [2, Teorema 3.2], [4, Teorema 5.8.1].) Bajo ciertas condiciones,
un par de estrategias(π1∗, π2∗) es un equilibrio de Nash para el juego competitivo
Γ(x0, θ0) si existen funciones V1 : Rm × S → R y V2 : Rm × S → R tales que
δV1(~x, θ)−12
Tr[V1~x~x(~x, θ) · σ(~x, θ)σ ′(~x, θ)]
= supπ1
t
r1(~x, θ, π1t , π2∗
t ) +⟨
b(~x, θ, π1t , π2∗
t ), V1~x (~x, θ)
⟩+∑i 6=θ
λπ1
t ,π2∗t
i,θ (~x)V1(~x, θ)
,
δV2(~x, θ)−12
Tr[V2~x~x(~x, θ) · σ(~x, θ)σ ′(~x, θ)]
= supπ2
t
r2(~x, θ, π1∗t , π2
t ) +⟨
b(~x, θ, π1∗t , π2
t ), V2~x (~x, θ)
⟩+∑i 6=θ
λπ1∗
t ,π2t
i,θ (~x)V2(~x, θ)
,
para toda pareja (~x, θ) ∈ Rm × S . En particular
V`(~xs, θs) = Eπ1∗,π2∗
~xs,θs
[∫∞s
e−δ(t−s)r`(~x(t), θ(t), π1∗t , π2∗
t )dt]
para ` = 1, 2.
Home Page
Title Page
Contents
JJ II
J I
Page 22 of 35
Go Back
Full Screen
Close
Quit
2. ¡Júntense!
Vea https://boardgamegeek.com/boardgame/30549/pandemic y https:
//boardgamegeek.com/boardgame/181304/mysterium.
Home Page
Title Page
Contents
JJ II
J I
Page 23 of 35
Go Back
Full Screen
Close
Quit
2.1. El Principio de racionalidad grupal
Home Page
Title Page
Contents
JJ II
J I
Page 24 of 35
Go Back
Full Screen
Close
Quit
Para alcanzar la racionalidad grupal los jugadores deben maximizar:
Eu1,u2x0,θ0
[∫∞0
e−δt (r1(x(t), θ(t), u1(t), u2(t)) + r2(x(t), θ(t), u1(t), u2(t)))dt]
.
Home Page
Title Page
Contents
JJ II
J I
Page 25 of 35
Go Back
Full Screen
Close
Quit
Definición 2.1. Sea
W(~x0, θ0, φ1, φ2) := Eφ1,φ2
~x0,θ0
[∫∞0
e−δt(
r1(~x(t), θ(t), φ1t , φ2
t ) + r2(~x(t), θ(t), φ1t , φ2
t ))
dt]
el pago que percibe una coalición en un juego colaborativo de dos jugadores que usan las
estrategias φ1 ∈ Π1 y φ2 ∈ Π2. Decimos que el par (φ1∗, φ2∗) ∈ Π1 ×Π2 es óptimo
para el juego colaborativo
Γc(x0, θ0) :=(~x(•), Θ(•), ~xs, θs, r1 + r2, Π1, Π2,S
)si
W(~x0, θ0, φ1∗, φ∗2) := sup(φ1,φ2)
W(~x0, θ0, φ1, φ2).
Home Page
Title Page
Contents
JJ II
J I
Page 26 of 35
Go Back
Full Screen
Close
Quit
Teorema 2.2. (cf. [4, Teorema 5.8.2].) Bajo ciertas condiciones, un par de estrategias(φ1∗, φ2∗) es óptimo para el juego colaborativo Γc(x0, θ0) si existe una función W :
Rm × S → R tal que
δW(~x, θ)−12
Tr[(W~x~x(~x, θ) · σ(~x, θ)σ ′(~x, θ)]
= sup(φ1
t ,φ2t )
{[r1(~x, θ, φ1
t , φ2t ) + r2(~x, θ, φ1
t , φ2t )]
+⟨
b(~x, θ, φ1t , φ2
t ), W~x(~x, θ)⟩+∑i 6=θ
λφ1
t ,φ2t
i,θ (~x)W(~x, θ)}
(2.1)
para todo (~x, θ) ∈ Rm × S . En particular
W(~xs, θs) = W(~xs, θs, φ1∗, φ∗2).
Home Page
Title Page
Contents
JJ II
J I
Page 27 of 35
Go Back
Full Screen
Close
Quit
2.2. Racionalidad individual y consistencia de los subjuegos
Home Page
Title Page
Contents
JJ II
J I
Page 28 of 35
Go Back
Full Screen
Close
Quit
Definimos implícitamente las recompensas instantáneas (B1(t), B2(t)) para el jue-
go Γc(x∗0 , θ∗0) mediante las relaciones
ξ`(~x∗(τ), θ∗(τ)) = E~x∗(τ),θ∗(τ)
[∫∞τ
e−δ(t−τ)B`(t)dt]
para ` = 1, 2, (2.2)
donde (~x∗(·), θ∗(·)) es la trayectoria que obtenemos al insertar el par óptimo de
estrategias(φ1∗, φ2∗) en (1.10)-(1.12).
El Principio de racionalidad individual reza así:
ξ`(x∗(t), θ∗(t)) ≥ V`(x∗(t), θ∗(t)).
Las funciones ξ1 y ξ2 se llaman reemplazo de las ganancias en Γc(x0, θ0).
Home Page
Title Page
Contents
JJ II
J I
Page 29 of 35
Go Back
Full Screen
Close
Quit
Sean τ ∈ [0,∞[ y t ≥ τ. Defina
γ(τ; t, ~x∗(t), θ∗(t)) := E~x∗(τ),θ∗(τ)
[∫∞t
e−δ(s−τ)B`(s)ds∣∣~x∗(t) = ~x∗t , θ∗(t) = θ∗t
].
Home Page
Title Page
Contents
JJ II
J I
Page 30 of 35
Go Back
Full Screen
Close
Quit
Note que
γ`(τ; t, x∗(t), θ∗(t)) = e−δ(t−τ)Ex∗(t),θ∗(t)
[∫∞t
e−δ(s−t)B`(s)ds]
= e−δ(t−τ)ξ`(x∗(t), θ∗(t))
= e−δ(t−τ)γ`(t; t, x∗(t), θ∗(t)).
Esta característica se llama consistencia de los subjuegos.
Home Page
Title Page
Contents
JJ II
J I
Page 31 of 35
Go Back
Full Screen
Close
Quit
3. El procedimiento de asignación de recompensas
instantáneas
Escriba γ`(τ; τ, ~x∗(τ), θ∗(τ)) de la manera siguiente
E~x∗(τ),θ∗(τ)
[∫ τ+∆t
τe−δ(s−τ)B`(s)ds
+ e−δ∆tγ`(τ + ∆t; τ + ∆t, ~x∗τ + ∆~x∗τ, θ∗(τ + ∆t)∣∣~x∗(τ) = x∗τ, θ∗(τ) = θ∗τ
]= E~x∗(τ),θ∗(τ)
[∫ τ+∆t
τe−δ(s−τ)B`(s)ds
+ γ`(τ; τ + ∆t, ~x∗τ + ∆~x∗τ, θ∗(τ + ∆t)∣∣~x∗(τ) = ~x∗τ, θ∗(τ) = θ∗τ
].
La última igualdad se sigue de la consistencia de los subjuegos Γc(~x∗τ, θ∗τ).
Home Page
Title Page
Contents
JJ II
J I
Page 32 of 35
Go Back
Full Screen
Close
Quit
Entonces
E~x∗(τ),θ∗(τ)
[∫ τ+∆t
τe−δ(s−τ)B`(s)ds
∣∣~x∗(τ) = ~x∗τ, θ∗(τ) = θ∗τ
]= E~x∗(τ),θ∗(τ)
[γ`(τ; τ + ∆t, ~x∗τ, θ∗τ)− γ`(τ; τ + ∆t, ~x∗τ + ∆x∗τ, θ∗(τ + ∆t))
].
Divida por ∆t y haga ∆t ↓ 0 para obtener que
B`(τ) = δξ`(~x∗τ, θ∗τ)−12
Tr[(ξ`~x~x(~x∗τ, θ∗τ) · σ(~x, θ)σ ′(~x∗τ, θ∗τ)]
−⟨
b(~x∗τ, θ∗τ , φ1∗τ , φ2∗
τ ), ξ`~x(~x∗τ, θ∗τ)
⟩−∑i 6=θ
λφ1∗
τ ,φ2∗τ
i,θ (~x∗τ)ξ`(~x∗τ, θ∗τ)
nos da una recompensa instantánea que depende de la forma de ξ`(x∗τ, θ∗τ) (vea
[4, Theorem 5.8.3]).
Home Page
Title Page
Contents
JJ II
J I
Page 33 of 35
Go Back
Full Screen
Close
Quit
Ejemplo 3.1. Un par de reemplazos de ganancias está dado por
ξ`NB(x∗τ, θ∗τ) = V`(x∗τ, θ∗τ) +12
[W(x∗τ, θ∗, τ)− V1(x∗τ, θ∗τ)− V2(x∗τ, θ∗τ)
]ξ`P(x∗τ, θ∗τ) = V`(x∗τ, θ∗τ)
+V`(x∗τ, θ∗τ)
V1(x∗τ, θ∗τ) + V2(x∗τ, θ∗τ)
[W(x∗τ, θ∗, τ)− V1(x∗τ, θ∗τ)− V2(x∗τ, θ∗τ)
]
Home Page
Title Page
Contents
JJ II
J I
Page 34 of 35
Go Back
Full Screen
Close
Quit
¿Comentarios? ¿Preguntas? ¿Sugerencias?
José Daniel López Barrientos
e-mail: [email protected]
Home Page
Title Page
Contents
JJ II
J I
Page 35 of 35
Go Back
Full Screen
Close
Quit
Referencias
[1] Ghosh, M.K.; Arapostathis, A.; Marcus, S.I. (1992) Optimal control of swit-
ching diffusions with application to flexible manufacturing systems. SIAM J.
Control Optim. 30, 1-23.
[2] Ghosh, M.K.; Marcus, S.I. (1998) Stochastic differential games with multiple
modes. Stochastic Analysis and Applications 16, 91-105.
[3] Song, Q.; Yin, G.; Zhang, Z. (2008) Numerical solutions for stochastic differen-
tial games with regime switching. IEEE Transactions on Automatic Control
53, 509-521.
[4] Yeung, D.W.K.; Petrosyan, L. (2006) Cooperative Stochastic Differential Games.
Springer, NY.