Micro 4 Aula 6

Prévia do material em texto

TEORIA DOS JOGOS 
Miguel Vazquez
Miguel.Vazquez.Martinez@gmail.com
1o Semestre 2015
JOGOS SIMULTÂNEOS – ESTRATÉGIAS MISTAS
JOGO EM FORMA ESTRATÉGICA (O NORMAL)
Conjunto de jogadores
Espaço de estratégias puras de cada jogador 
O número de estratégias pode ser diferente para cada jogador
Espaço total de estratégias puras 
Supomos que é um conjunto finito.
Recompensas de cada jogador , donde é o conjunto de 
estratégias escolhidas pelos jogadores: 
 1,2, ,i I
iS
i iS S
( )iu s s
1( , , )Is s s
S
 1 2 3, , ,i i i iS s s s
JOGO DAS MOEDAS
O jogo das moedas (matching pennies) é um exemplo de não 
existência do equilíbrio de Nash
Tem dois jogadores
Os espaços de estratégias puras são 
Recompensas: se ambas as moedas coincidem, o jogador 2 ganha a moeda 
do jogador 1. Se as moedas não coincidem, o jogador 1 ganha a moeda do 
jogador 
 1,2i
 1 2 ,S S cara cruz 
Jugador 1
Jugador 2
(-1,1) (1,-1)
(1,-1) (-1,1)
cara
coroa
cara coroa
ESTRATÉGIAS MISTAS
Estratégia mista: 𝜓, distribuição de probabilidade sobre as 
estratégias puras
Supomos que a aleatorização de cada jogador é uma distribuição 
independente do resto dos jogadores
A recompensa será o valor esperado levando em consideração as 
probabilidades
E.g. 2 jogadores
 O primeiro tem J estratégias puras e o segundo K
𝑢1 𝜓1 , 𝜓2 = 𝑗=1
𝐽 𝜓1 𝑠1𝑗 𝑘=1
𝐾 𝜓2 𝑠2𝑗 𝑢1 𝑠1𝑗 , 𝑠2𝑘
𝑢2 𝜓1 , 𝜓2 = 𝑘=1
𝐾 𝜓2 𝑠2𝑘 𝑗=1
𝐽 𝜓1 𝑠1𝑗 𝑢2 𝑠1𝑗 , 𝑠2𝑘
ESTRATÉGIAS MISTAS
Qual a intuição atrás das estratégias mistas?
Harsanyi (1973) – incerteza do jogador 1 sobre a estratégia pura do 
jogador 2...
...e que depende do que sabe o jogador 2
EXEMPLO
Jogador 1
Jogador 2
cara (-1,1) (1,-1)
(1,-1) (-1,1)coroa
cara coroa
q 1 q
r
1 r
• Os ganhos esperados do jogador 1 são
– Se cara:
– Se coroa:
( 1) (1 ) (1) 1 2q q q      
1 (1 ) ( 1) 2 1q q q      
1
2
q 
1
2
q 
1
2
q 
Melhor coroase
se
se
Indiferente
Melhor cara
𝜓1 = (𝑟, 1 − 𝑟)
𝜓2 = (𝑞, 1 − 𝑞)
MELHOR RESPOSTA EM ESTRATÉGIAS MISTAS
• Jogador 1
• Nota – supomos que os sucesos são independentes, i.e. a 
probabilidade de (cara,cara) é rq
• A função é crescente em r se e 
decrescente se 
• A melhor resposta considerando estratégias puras e mistas é 
igual a considerar só estratégias puras
(2 1) (2 4 )q r q   (2 4 ) 0q 
(2 4 ) 0q 
𝑢1 𝜓1 , 𝜓2 = 𝑟𝑞 ∙ −1 + 𝑟 1 − 𝑞 ∙ 1 + 1 − 𝑟 𝑞 ∙ 1 + 1 − 𝑟 1 − 𝑞 ∙ −1 = 2𝑞 − 1 + 𝑟(2 − 4𝑞)
UTILIDADE (RECOMPENSA) ESPERADA
q
1( )u
1
cara coroa
1
2
1
0
-1
r
2( )u
1
0
-1
cruz coroa
1
1
2
𝑢1 𝜓1 , 𝜓2 𝑢2 𝜓1 , 𝜓2
MELHOR RESPOSTA PARA 1 (NÃO É FUNÇÃO!)
r
q
0
1
2
1
*( )r q
1cara
cruz
cruz cara
*
1 1/ 2
[0( ,1] 1 2
1/
) /
0 2
r
q
q
q
q
 

  
  
EQUILÍBRIO DE NASH EM ESTRATÉGIAS MISTAS
Na aula anterior, equilíbrio de Nash em estratégias puras:
A generalização direta seria
Mas basta comprovar 
* * *( , ) ( , ) i i i i i i i ii u s s u s s s S    
∀𝑖 𝑢𝑖 𝜓𝑖
∗, 𝜓−𝑖
∗ ≥ 𝑢𝑖 𝜓𝑖 , 𝜓−𝑖
∗
∀𝑖 𝑢𝑖 𝜓𝑖
∗, 𝜓−𝑖
∗ ≥ 𝑢𝑖 𝑠𝑖 , 𝜓−𝑖
∗
PRIMEIRA PARTE DO CASO PRÁTICO
Justificar que os equilíbrios obtidos com as duas definições é igual
Definição 1
Definição 2
∀𝑖 𝑢𝑖 𝜓𝑖
∗, 𝜓−𝑖
∗ ≥ 𝑢𝑖 𝜓𝑖 , 𝜓−𝑖
∗
∀𝑖 𝑢𝑖 𝜓𝑖
∗, 𝜓−𝑖
∗ ≥ 𝑢𝑖 𝑠𝑖 , 𝜓−𝑖
∗
MELHOR RESPOSTA 2
q
r
0
1
2
1
*( )q r
1cara
cruz
cruz cara
*
0 1/ 2
[0( ,1] 1 2
1/
) /
1 2
q
r
r
r
r
 

  
  
MELHORES RESPOSTAS
r
q
0
1
2
1
*( )r q
1cara
cruz
cara
*( )q r
cruz
Agora equilibrio em
estratégias mistas
BATALHA DOS SEXOS
Futebol Ballet
Futebol 4 , 2 0 , 0
Ballet 0 , 0 2 , 4
ela
ele
q 1 q
r
1 r
BATALHA DOS SEXOS
Fútbol Ballet
Fútbol 4 , 2 0 , 0
Ballet 0 , 0 2 , 4
ela
ele
q 1 q
r
1 r
BATALHA DOS SEXOS
Fútbol Ballet
Fútbol 4 , 2 0 , 0
Ballet 0 , 0 2 , 4
ela
ele
q 1 q
r
1 r
1( ) 4 (1 ) 0     u rq r q (1 ) 0  r q (1 )(1 ) 2   r q
*
0 1/ 3
[0,1] 1/
1
)
/
( 3
1 3
 

  
  
r
q
q q
q
𝑢1 𝜓
𝑟 = 1 → 𝑢1 𝜓 = 𝑞 ∙ 4
𝑟 = 0 → 𝑢1 𝜓 = 2 − 2𝑞
EQUILÍBRIOS
r
q
0
2
3
1
*( )r q
1ballet
fútbol
ballet
*( )q r
fútbol
1
3
EQUILÍBRIOS
r
q
0
2
3
1
*( )r q
1ballet
fútbol
ballet
*( )q r
fútbol
1
3
EXISTENCIA DEL EQUILIBRIO DE NASH (EN)
Teorema de Nash (1950): Em todo jogo com um número finito de 
jogadores, cada um deles com um número finito de estratégias, 
existe pelo menos um equilíbrio de Nash, incluindo possivelmente 
estratégias mistas
MELHORES RESPOSTAS E EQUILÍBRIOS DE NASH
Pensem num jogo 2×2
A pode escolher entre as ações aA1 e a
A
2
B pode escolher entre as ações aB1 e a
B
2
Há quatro combinações de ações:
(aA1, a
B
1), (a
A
1, a
B
2), (a
A
2, a
B
1), (a
A
2, a
B
2)
Cada combinação poderá proporcionar recompensas diferentes 
aos jogadores
MELHORES RESPOSTAS E EQUILÍBRIOS DE NASH
Suponha que os ganhos de A e B, quando as ações escolhidas 
forem aA1 e a
B
1, sejam:
UA(aA1, a
B
1) = 6 e U
B(aA1, a
B
1) = 4
Analogamente, suponha que:
UA(aA1, a
B
2) = 3 e U
B(aA1, a
B
2) = 5
UA(aA2, a
B
1) = 4 e U
B(aA2, a
B
1) = 3
UA(aA2, a
B
2) = 5 e U
B(aA2, a
B
2) = 7
MELHORES RESPOSTAS E EQUILÍBRIOS DE NASH
UA(aA1, a
B
1) = 6 e U
B(aA1, a
B
1) = 4
UA(aA1, a
B
2) = 3 e U
B(aA1, a
B
2) = 5
UA(aA2, a
B
1) = 4 e U
B(aA2, a
B
1) = 3
UA(aA2, a
B
2) = 5 e U
B(aA2, a
B
2) = 7
24
MELHORES RESPOSTAS E EQUILÍBRIOS DE NASH
UA(aA1, a
B
1) = 6 e U
B(aA1, a
B
1) = 4
UA(aA1, a
B
2) = 3 e U
B(aA1, a
B
2) = 5
UA(aA2, a
B
1) = 4 e U
B(aA2, a
B
1) = 3
UA(aA2, a
B
2) = 5 e U
B(aA2, a
B
2) = 7
Se B escolhe a ação aB1, então a melhor resposta de A é ??
25
MELHORES RESPOSTAS E EQUILÍBRIOS DE NASH
UA(aA1, a
B
1) = 6 e U
B(aA1, a
B
1) = 4
UA(aA1, a
B
2) = 3 e U
B(aA1, a
B
2) = 5
UA(aA2, a
B
1) = 4 e U
B(aA2, a
B
1) = 3
UA(aA2, a
B
2) = 5 e U
B(aA2, a
B
2) = 7
Se B escolhe a ação aB1, então a melhor resposta de A é a ação 
aA1 (pois 6 > 4)
26
MELHORES RESPOSTAS E EQUILÍBRIOS DE NASH
UA(aA1, a
B
1) = 6 e U
B(aA1, a
B
1) = 4
UA(aA1, a
B
2) = 3 e U
B(aA1, a
B
2) = 5
UA(aA2, a
B
1) = 4 e U
B(aA2, a
B
1) = 3
UA(aA2, a
B
2) = 5 e U
B(aA2, a
B
2) = 7
Se B escolhe a ação aB1, então a melhor resposta de A é a ação 
aA1 (pois 6 > 4)
Se B escolhe a ação aB2, então a melhor resposta de A é ??
27
MELHORES RESPOSTAS E EQUILÍBRIOS DE NASH
UA(aA1, a
B
1) = 6 e U
B(aA1, a
B
1) = 4
UA(aA1, a
B
2) = 3 e U
B(aA1, a
B
2) = 5
UA(aA2, a
B
1) = 4 e U
B(aA2, a
B
1) = 3
UA(aA2, a
B
2) = 5 e U
B(aA2, a
B
2) = 7
Se B escolhe a ação aB1, então a melhor resposta de A é a ação 
aA1 (pois 6 > 4)
Se B escolhe a ação aB2, então a melhor resposta de A é a ação 
aA2 (pois 5 > 3)
28
MELHORES RESPOSTAS E EQUILÍBRIOS DE NASH
Se B escolhe aB1, então A escolhe a
A
1
Se B escolhe aB2, então A escolhe a
A
2
A “curva” de melhor resposta de A é:
Melhor 
resposta
de A
aA1
aA2
aB2a
B
1
Ação de B
+
+MELHORES RESPOSTAS E EQUILÍBRIOS DE NASH
UA(aA1, a
B
1) = 6 e U
B(aA1, a
B
1) = 4
UA(aA1, a
B
2) = 3 e U
B(aA1, a
B
2) = 5
UA(aA2, a
B
1) = 4 e U
B(aA2, a
B
1) = 3
UA(aA2, a
B
2) = 5 e U
B(aA2, a
B
2) = 7
MELHORES RESPOSTAS E EQUILÍBRIOS DE NASH
UA(aA1, a
B
1) = 6 e U
B(aA1, a
B
1) = 4
UA(aA1, a
B
2) = 3 e U
B(aA1, a
B
2) = 5
UA(aA2, a
B
1) = 4 e U
B(aA2, a
B
1) = 3
UA(aA2, a
B
2) = 5 e U
B(aA2, a
B
2) = 7.
Se A escolhe a ação aA1, então a melhor resposta de B é ??
MELHORES RESPOSTAS E EQUILÍBRIOS DE NASH
UA(aA1, a
B
1) = 6 e U
B(aA1, a
B
1) = 4
UA(aA1, a
B
2) = 3 e U
B(aA1, a
B
2) = 5
UA(aA2, a
B
1) = 4 e U
B(aA2, a
B
1) = 3
UA(aA2, a
B
2) = 5 e U
B(aA2, a
B
2) = 7.
Se A escolhe a ação aA1, então a melhor resposta de B é a ação 
aB2 (porque 5 > 4)
MELHORES RESPOSTAS E EQUILÍBRIOS DE NASH
UA(aA1, a
B
1) = 6 e U
B(aA1, a
B
1) = 4
UA(aA1, a
B
2) = 3 e U
B(aA1, a
B
2) = 5
UA(aA2, a
B
1) = 4 e U
B(aA2, a
B
1) = 3
UA(aA2, a
B
2) = 5 e U
B(aA2, a
B
2) = 7.
Se A escolhe a ação aA1, então a melhor resposta de B é a ação 
aB2 (porque 5 > 4)
Se A escolhe a ação aA2, então a melhor resposta de B é ??
MELHORES RESPOSTAS E EQUILÍBRIOS DE NASH
UA(aA1, a
B
1) = 6 e U
B(aA1, a
B
1) = 4
UA(aA1, a
B
2) = 3 e U
B(aA1, a
B
2) = 5
UA(aA2, a
B
1) = 4 e U
B(aA2, a
B
1) = 3
UA(aA2, a
B
2) = 5 e U
B(aA2, a
B
2) = 7
Se A escolhe a ação aA1, então a melhor resposta de B é a ação 
aB2 (porque 5 > 4)
Se A escolhe a ação aA2, então a melhor resposta de B é a ação 
aB2 (porque 7 > 3)
MELHORES RESPOSTAS E EQUILÍBRIOS DE NASH
Se A escolhe aA1 , então B escolhe a
B
2
Ação 
de A a
A
1
aA2
aB2a
B
1
Melhor resposta de B 
MELHORES RESPOSTAS E EQUILÍBRIOS DE NASH
Se A escolhe aA1 , então B escolhe a
B
2
Se A escolhe aA2 , então B escolhe a
B
2
Ação 
de A a
A
1
aA2
aB2a
B
1
Melhor resposta de B 
MELHORES RESPOSTAS E EQUILÍBRIOS DE NASH
Se A escolhe aA1 , então B escolhe a
B
2
Se A escolhe aA2 , então B escolhe a
B
2
A “curva” de melhor resposta de B é:
Ação 
de A a
A
1
aA2
aB2a
B
1
Melhor resposta de B 
MELHORES RESPOSTAS E EQUILÍBRIOS DE NASH
Se A escolhe aA1 , então B escolhe a
B
2
Se A escolhe aA2 , então B escolhe a
B
2
A “curva” de melhor resposta de B é:
Ação 
de A a
A
1
aA2
aB2a
B
1
Melhor resposta de B 
Notem que aB2 é 
ação estritamente 
dominante para B
MELHORES RESPOSTAS E EQUILÍBRIOS DE NASH
Resposta de A
aA1
aA2
aB2a
B
1
aA1
aA2
aB2a
B
1
+
+
Escolha de A
Escolha de B Resposta de B
Como as curvas de melhores respostas 
podem ser usadas para localizar os EN?
B A
MELHORES RESPOSTAS E EQUILÍBRIOS DE NASH
Resposta de A
aA1
aA2
aB2a
B
1
+
+
Resposta de B
Há equilíbrio de Nash?
Sobrepondo-as!
MELHORES RESPOSTAS E EQUILÍBRIOS DE NASH
aA1
aA2
aB2a
B
1
+
+
Há equilíbrio de Nash?
Resposta de A
Resposta de B
Sim, (aA2, a
B
2). Por que?
aA2 é melhor resposta a a
B
2
aB2 é melhor resposta a a
A
2