PO2 Apresentação 03 TeoriadosJogos EstratégiasMaximin

Prévia do material em texto

1
TEORIA DOS JOGOS
DEP-CTG-UFPE
Maximin / Minimax
� Características 
– Problemas de sequência de decisões alternadas
– Avaliação tipicamente até a próxima decisão
– Situações sem a possibilidade de cooperação 
(competição estrita)
� Pressuposto Principal
– Jogo competitivo
� Solução
– Avaliar os prêmios após uma sequência de escolhas
Estratégias
� Estratégias puras
– Escolhas não aleatórias entre alternativas de ação
Estratégia i: ação adotada pelo jogador I
Estratégia j: ação adotada pelo jogador J
Estratégias
� Jogos finitos
– O número de estratégias puras é finito
� Jogos infinitos
– O número de estratégias puras de pelo menos um 
jogador é infinito
Maximin / Minimax
� A análise do jogo (escolha da melhor estratégia) 
exige a avaliação de prêmios ou de perdas como 
consequência de uma combinação de estratégias 
adotadas
– Prêmios
– Perdas
� O prêmio (perda) é referente a um dos jogadores (k)
� Para o outro jogador, este prêmio (perda) representa na 
verdade uma perda (prêmio)
),(),( jipjil kk −=
),( jipk
),(),( jiljip JI = ),(),( jiljip IJ =
Prêmios 
(Jogador I)
JOGADOR J
j1 j2 ... jn
JOGADOR I
i1 pI(i1,j1) pI(i1,j2) ... pI(i1,jn)
i2 pI(i2,j1) pI(i2,j2) ... pI(i2,jn)
...
... ... ... ...
im pI(im,j1) pI(im,j2) ... pI(im,jn)
Tabela de prêmios
2
Prêmios 
(Jogador J)
JOGADOR J
j1 j2 ... jn
JOGADOR I
i1 pJ(i1,j1) pJ(i1,j2) ... pJ(i1,jn)
i2 pJ(i2,j1) pJ(i2,j2) ... pJ(i2,jn)
...
... ... ... ...
im pJ(im,j1) pJ(im,j2) ... pJ(im,jn)
Tabela de prêmios Estratégias
� Estratégias dominadas
– Uma estratégia é dominada por outra se esta 
última sempre for pelo menos tão boa quanto a 
primeira, e algumas vezes melhor, independente 
do que faz o oponente
– As estratégias dominadas podem ser eliminadas 
imediatamente
Maximin / Minimax
� Sequência de decisões
– Visão do jogador I
� Jogador I seleciona i
� Jogador J seleciona j
– Visão do jogador J
� Jogador J seleciona j
� Jogador I seleciona i
Ordem das
decisões
Ordem da
avaliação
Ordem das
decisões
Ordem da
avaliação
Maximin / Minimax
� Perspectivas
– Problema do jogador I
� Maximizar seu prêmio (Minimizar sua perda) por meio de 
uma estratégia
– Problema do jogador J
� Minimizar o prêmio (Maximizar a perda) do outro jogador 
por meio de uma estratégia
),(),(Min jiljip JIj =
),(),(Max jiljip JIi = ),(),(Min jipjil JIi =
),(),(Max jipjil JIj =
Maximin / Minimax
� Escolha (Prêmio para o jogador I)
– Maximin (Jogador I)
– Minimax (Jogador J)
� Técnicas de solução
– Tabela de prêmios
– Estratégias equalizadoras
),(MaxMin jipIij
),(MinMax jipIji
Exemplo
� Disputa por mercado consumidor
– Duas empresas (I e J) estão disputando um
mercado de uma mesma região. Existe a
possibilidade de concentrar a estratégia de vendas
dos produtos que cada uma comercializa em
diferentes camadas sociais (A, B, C). A perda para
a empresa I é avaliada proporcionalmente à fatia de
mercado perdida devido à escolha das classes
sociais
3
Exemplo
� Matriz de Perdas
– Não existem estratégias dominadas
lI(i,j) iA iB iC
jA 0 1 -2
jB 3 -2 0
jC -1 0 2
Exemplo
lI(i,j) iA iB iC
jA 0 1 -2
jB 3 -2 0
jC -1 0 2
� Matriz de Perdas
1),(),(MaxMin == ABIIji jiljil
minimax) a(estratégi * Bii =
Exemplo
lI(i,j) iA iB iC
jA 0 1 -2
jB 3 -2 0
jC -1 0 2
� Matriz de Perdas
1),(),(MinMax −== CAIIij jiljil
maximin) a(estratégi * Cjj =
Maximin / Minimax
� Problema
– Pode ser que, depois do jogador J escolher j, exista uma 
outra estratégia que apresente menor perda
– Decisões sequenciais seriam periodicamente alteradas
� Solução
– Aleatorizar a escolha das estratégias
– A ideia é neutralizar a escolha do oponente, igualando 
as perdas para qualquer estado
– A consequência dependerá apenas da estratégia 
escolhida pelo primeiro jogador
Estratégias
� Estratégias mistas
– Escolhas aleatórias entre estratégias puras
� Estratégia x: regra randomizada do jogador I
� Estratégia y: regra randomizada do jogador J
– Interpretação
� Estratégia xi: probabilidade do jogador I usar a estratégia i
� Estratégia yj: probabilidade do jogador J usar a estratégia j
Minimax
� O prêmio (ou perda) de uma estratégia mista 
pode ser obtida a partir dos prêmios (ou perdas) 
das estratégias puras
∑=
j
jkk yjipyip ).,(),(
∑=
i
ikk xjipjxp ).,(),(
j
i j
ikk yxjipyxp .).,(),( ∑∑=
4
Estratégias equalizadoras
� Estratégia equalizadora (x0 / y0)
� Se x0 (y0) é uma estratégia equalizadora não 
dominada, então x0 (y0) é uma estratégia minimax 
(maximin)
jcteVjxp
icteVyip
xk
yk
∀==
∀==
,.),(
,.),(
0
0
0
0
Valor do jogo
� Valor superior do jogo
� Valor inferior do jogo
� Propriedade
),(MaxMin yxpV
xy
=
),(MinMax yxpV
yx
=
VV ≥
Teorema do Máximo Mínimo
� Seja um jogo finito de dois participantes de soma-zero em 
que são permitidas estratégias mistas, então:
onde
� Se o teorema do máximo mínimo é válido, então o jogo é 
estável.
� V é chamado de Valor do Jogo
),(),(MinMax),(MaxMin 00 yxpyxpyxp kk
xykyx
==
maximin estratégia a é 0y
minimax estratégia a é 0x
VVV ==
Exemplo
� Matriz de Prêmios
– Não existem estratégias dominadas
pI(i,j) j1 j2
i1 3 2
i2 0 7
Exemplo
� Matriz de Prêmios
maximin) a(estratégi * 1ii =
pI(i,j) j1 j2
i1 3 2
i2 0 7
minimax) a(estratégi * 1jj =
2=V
3=V
instável jogo
Exemplo
� Matriz de Prêmios
pI(i,j) j1 j2 y
i1 3 2 3y1+2(1-y1)
i2 0 7 7(1-y1)
x 3x1 2x1+7(1-x1) V
)1(723 111 xxx −+=



=
=
8/1
8/7
2
1
x
x
)1(7)1(23 111 yyy −=−+



=
=
8/3
8/5
2
1
y
y
5
Exemplo
� Matriz de Prêmios
pI(i,j) j1 j2 y
i1 3 2 2,625
i2 0 7 2,625
x 2,625 2,625 2,625
625,28/21 ==== VVV
maximin) a(estratégi * xi =
minimax) a(estratégi * yj =
Resolução por Programação Linear
� Estratégias Maximin (Jogador I)
0,,
1
,0),(
a sujeito
Max
1
1
1
1
,, 11
≥
=
∀≥−
∑
=
+
+
+
m
m
i
i
mI
m
xx
xx
x
jxjxp
x
m
K
K
*
1+= mxv
Resolução por Programação Linear
� Estratégias Minimax (Jogador J)
0,,
1
,0),(
a sujeito
Min
1
1
1
1
,, 11
≥
=
∀≤−
∑
=
+
+
+
n
n
j
j
nI
nyy
yy
y
iyyip
y
n
K
K
*
1+= nyv
Exemplo
� Matriz de Prêmios
pI(i,j) j1 j2
i1 3 2
i2 0 7
Exemplo
� Estratégia Maximin (Jogador I)
0,
1
0).,().,(
0).,().,(
a sujeito
Max
21
21
3222121
3212111
3
,, 321
≥
=+
≥−+
≥−+
xx
xx
xxjipxjip
xxjipxjip
x
II
II
xxx
Exemplo
� Estratégia Maximin (Jogador I)
0,
1
072
03
a sujeito
Max
21
21
321
31
3
,, 321
≥
=+
≥−+
≥−
xx
xx
xxx
xx
x
xxx
6
Exemplo
� Estratégia Maximin (Jogador I)
)625,2;125,0;875,0(
8
21
;
8
1
;
8
7*
≅






=x
Exemplo
� Estratégia Minimax (Jogador J)
0,
1
0).,().,(
0).,().,(
a sujeito
Min
21
21
3222112
3221111
3
,, 321
≥
=+
≤−+
≤−+
yy
yy
yyjipyjip
yyjipyjip
y
II
II
yyy
Exemplo
� Estratégia Minimax (Jogador J)
0,
1
07
023
a sujeito
Min
21
21
32
321
3
,, 321
≥
=+
≤−
≤−+
yy
yy
yy
yyy
y
yyy
Exemplo
� Estratégia Minimax (Jogador J)
)625,2;375,0;625,0(
8
21
;
8
3
;
8
5*
≅






=y