Upload
others
View
2
Download
0
Embed Size (px)
Citation preview
MHD’15 - FTJ: 0 J. Bautista, G. López
Joaquín Bautista, Guillermo López
Fundamentos de Teoría de Juegos - II
UNIVERSITAT POLITÈCNICA DE CATALUNYA – BARCELONATECH
Modelos y Herramientas de Decisión – Máster Universitario de Ingeniería de Organización - ETSEIB
OPE – ORGANIZACIÓN DE LA PRODUCCIÓN Y DE EMPRESA (ASPECTOS TÉCNICOS, JURÍDICOS Y ECONÓMICOS EN PRODUCCIÓN )
OPE-PROTHIUS – OPE-MSc.2015/06 (20150313) - http://futur.upc.edu/OPE - www.prothius.com - Departamento de Organización de Empresas – UPC
MHD’15 - FTJ: 1 J. Bautista, G. López
Técnicas básicas de resolución
Juegos de suma nula.
Valor Max Min / Min Max
Punto de silla
Juegos 2 x 2
Juegos 2 x n
Juegos m x 2
Juegos m x n.
Contenido
MHD’15 - FTJ: 2 J. Bautista, G. López
Técnicas básicas de resolución Esquema de resolución:
1. Interpretar
2. Forma extendida
3. Forma normal
4. Dominancias:
4.1. Si obtenemos matriz (1x1) → FIN
4.2. Si no → Ir al paso 5
5. Buscar el punto de silla con las estrategias no dominadas
5.1. Si existe punto de silla → FIN
- Si es un problema ‘2 x 2’ → Solucionar mediante fórmulas
5.2. Si no - Si es un problema ‘2 x n’ → Solucionar mediante gráficos y/o sistema
- Si es un problema ‘n x m’ → Solucionar mediante PL
MHD’15 - FTJ: 3 J. Bautista, G. López
Ejemplo 2: Póker simplificado
II
(‐1,1)(‐1,1)
2$2$
III I
(‐1,1)(‐1,1)
2$2$
III I I IIV IV
(1,‐1)(0,0)
2$
(1,‐1)(3,‐3)
2$
(1,‐1)(‐3,3)
2$
(1,‐1)(0,0)
2$
A /KA /A K /KK /A
Ex aequo J1 gana 3, J2 pierde 3
Juegos de suma nula. Valor Max Min / Min Max (1)
MHD’15 - FTJ: 4 J. Bautista, G. López
Ejemplo 2: Póker simplificado
Tabla con utilidades de J1
J2 A/A A/P P/A P/P
J1
A/A 0 -1/4 5/4 1
A/P 1/4 -1/4 2/4 0
P/A -5/4 -1 -1/4 0
P/P -1 -1 -1 -1
-1/4
1/4
Max Min
-1/4 -5/4
-1
-1/4 5/4 1 Min Max
Juegos de suma nula. Valor Max Min / Min Max (2)
MHD’15 - FTJ: 5 J. Bautista, G. López
Juegos de suma nula. Punto de silla
Ejemplo 3: Punto de silla (todo jugador tiene una estrategia tal que si la abandona sale perdiendo)
Tabla de utilidades del J1
J2
µ1 µ2 µ3
J1
σ1 -3 -2 6
σ2 2 0 2
σ3 5 -2 4
-3
0
-2
5 0 6
Max Min
Min Max
Punto de silla: σ2,μ2 Valor del juego: 0
ESTRATEGIAS PURAS Para J1: σ1 = 0; σ2 = 1; σ3 = 0 Para J2: µ1 = 0; µ2 = 1; µ3 = 0
MHD’15 - FTJ: 6 J. Bautista, G. López
Juegos 2 x 2. Ejemplo
Ejemplo 4: Juego 2 x 2
• Punto de silla:
J2
y1 y2
J1 x1 -0.5 1
x2 0.5 0
-0.5
0
0.5 1
J1: Max Min → 0 J2: Min Max → 0.5
No existe punto de silla
El valor del juego se encontrará entre 0 y 0.5.
MHD’15 - FTJ: 7 J. Bautista, G. López
Juegos 2 x 2. Programa lineal
Juegos 2 x 2: PLs
• Matriz de juego:
J2
y1 y2
J1 x1 a11 a12
x2 a21 a22
Primal:
max[ ]v
s.a.
x1+ x
2=1
v! a11x1! a
21x22" 0
v! a12x1! a
22x22" 0
x1, x
2# 0
Dual:
min[ ] !v
s.a.
y1+ y
2=1
!v " a11y1" a
12y22# 0
!v " a21y1" a
22y22# 0
y1, y
2# 0
MHD’15 - FTJ: 8 J. Bautista, G. López
Juegos 2 x 2. Fórmulas de equilibrio
Juegos 2 x 2: Fórmulas
• Valor del juego:
• Probabilidad de que J1 utilice x1 o x2:
• Probabilidad de que J2 utilice y1 o y2:
J2
y1 y2
J1 x1 a11 a12
x2 a21 a22
21122211
21122211
aaaaaaaav−−+
⋅−⋅=
21122211
21221 aaaa
aax−−+
−=
21122211
12112 aaaa
aax−−+
−=
21122211
12221 aaaa
aay−−+
−=
21122211
21112 aaaa
aay−−+
−=
MHD’15 - FTJ: 9 J. Bautista, G. López
Juegos 2 x 2. Resolución
Ejemplo 4: Juego 2 x 2 (Continuación)
• Fórmulas:
v =-0.5 !0"1!0.5
-0.5+ 0"1" 0.5= 0.25
x1=
0! 0.5
-0.5+ 0!1! 0.5= 0.25 x
2=
-0.5!1
-0.5+ 0!1! 0.5= 0.75
y1=
0!1
-0.5+ 0!1! 0.5= 0.5 y
2=
-0.5! 0.5
-0.5+ 0!1! 0.5= 0.5
Valor del juego
ESTRATEGIAS MIXTAS Para J1: x1 = 0.25 ; x2 = 0.75 Para J2: y1 = 0.5 ; y2 = 0.5
J2
y1 y2
J1 x1 -0.5 1
x2 0.5 0
MHD’15 - FTJ: 10 J. Bautista, G. López
Juegos 2 x n. Resolución gráfica
Ejemplo 5: Juego 2 x n
J2
y1 y2 … yn
J1 x1 a11 a12 … a1n
x2 a21 a22 … a2n
J2
y1 y2 y3 y4
J1 x1 7 4 2 1
x2 2 3 4 6
Valor del juego
Restricciones de J1 = Estrategias de J2
Corte y2 <−> y3 :
x1=1 x
2=10.5 2 3
Corte: y2! y
3
x1=1 3, x
2= 2 3
y1= 0, y
2= 2 3, y
3=1 3, y
4= 0
vJ1=10 3
MHD’15 - FTJ: 11 J. Bautista, G. López
Ejemplo 6: Juego m x 2
J2
y1 y2
J1
x1 a11 a12
x2 a21 a22
… … …
xm am1 am2
Valor del juego
J2
y1 y2
J1
x1 7 2
x2 4 3
x3 2 4
x4 1 6
Restricciones de J2 = Estrategias de J1
Para J1: El valor del juego será el mínimo en la frontera de máxima ganancia de J1.
y1=1 y
2=10.5 3 5
Juegos m x 2. Resolución gráfica
Corte: x1 ! x4
y1 = 2 5, y2 = 3 5x1 =1 2, x2 = 0, x3 = 0, x4 =1 2vJ 2 = 4
MHD’15 - FTJ: 12 J. Bautista, G. López
Juegos m x n: PL Primal
J2
y1 y2 … yn
J1
x1 a11 a12 … a1n
x2 a21 a22 … a2n
… … … … …
xm am1 am2 … amn
Estrategias mixtas de J1
- Nº de variables: m+1
- Objetivo: maximizar la ganancia mínima de J1 marcada por las estrategias de J2.
s.a.:
x1+ x
2+...+ x
m=1
v! a11x1! a
21x2!...! a
m1xm" 0
v! a12x1! a
22x2!...! a
m2xm" 0
v! a1nx1! a
2nx2!...! a
mnxm" 0
x1, x
2,.., x
m! 0
vJ1 = max[ ]v
x1, x
2,..., x
m( )v
....
Juegos m x n. Programa Lineal (1)
MHD’15 - FTJ: 13 J. Bautista, G. López
Juegos m x n: PL Dual
J2
y1 y2 … yn
J1
x1 a11 a12 … a1n
x2 a21 a22 … a2n
… … … … …
xm am1 am2 … amn
Estrategias mixtas de J2
- Nº de variables: n+1
- Objetivo: minimizar la máxima pérdida de J2 marcada por las estrategias de J1.
s.a.:
1...21 =+++ nyyy!v " a11y1 " a12y2 " ... " a1nyn # 0!v " a21y1 " a22y2 " ... " a2nyn # 0
!v " am1y1 " am2y2 " ...amnyn # 0y1, y
2,.., y
n! 0
y1, y
2,..., y
n( )!v
vJ 2 = min[ ] !v
....
Juegos m x n. Programa Lineal (2)
MHD’15 - FTJ: 14 J. Bautista, G. López
Juegos m x n. Programa Lineal (3)
J2
y1 y2 y3
J1
x1 4 9 2
x2 3 5 7
x3 8 1 6
2
3
1
8 9 7
Max Min
Min Max
Primal: max[ ]vs.a.x1 + x2 + x3 =1v ! 4x1 ! 3x2 !8x32 " 0v ! 9x1 ! 5x2 !1x32 " 0v ! 2x1 ! 7x2 ! 6x32 " 0x1, x2, x3 # 0
Ejemplo 7: Juego 3 x 3
Dual: min[ ] !vs.a.y1 + y2 + y3 =1!v " 4y1 " 9y2 " 2y3 # 0!v " 3y1 " 5y2 " 7y3 # 0!v "8y1 "1y2 " 6y3 # 0y1, y2, y3 # 0
MHD’15 - FTJ: 15 J. Bautista, G. López
Juegos m x n. Programa Lineal (4)
Ejemplo 8: Juego 4 x 4:
Ejercicio: Modelizar y resolver el siguiente juego 4 x 4.
y1 y2 y3 y4
x1 7 12 1 14
x2 2 13 8 11
x3 16 3 10 5
x4 9 6 15 4