Nota de Aula 05 - Teoria dos Jogos

Prévia do material em texto

DEPARTAMENTO DE ECONOMIA / PUC-Rio
MICROECONOMIA II
Prof. Marcos Antonio C. da Silveira
Nota de Aula 5: Teoria dos Jogos
Bibliogra…a: Varian, cap. 28; Cabral, cap. 4; Gibbons, cap. 1, seções 1.1 e 1.3
1 Jogos com Estratégias Mistas: De…nição
De…nição 1 Considere um jogo G =
�
I; (Si)i2I ; (ui)i2I
	
qualquer. Uma estratégia mista para o
jogador i é uma distribuição de probabilidade
�i : Si ! [0; 1]
sobre o conjunto de estratégias puras Si, onde �i (si) � 0 denota a probabilidade atribuída à
estratégia pura si. Por de…nição, segue que:
1 � �i (si) � 0 para todo si;X
si2Si
�i (si) = 1:
� Denote por �(Si) o conjunto de todas as estratégias mistas do jogador i. Logo, �i 2
�(Si) denota uma estratégia mista qualquer deste jogador.
� A teoria supõe que as estratégias mistas de jogadores diferentes são independentes.
Logo, a probabilidade de ocorrer a combinação de estratégias s = (s1; s2; :::; sn) é dada
por
�1 (s1)�2 (s2) :::�2 (sn) :
De…nição 2 Considere um jogo G =
�
I; (Si)i2I ; (ui)i2I
	
qualquer. A extensão deste jogo para
estratégias mistas é um novo jogo �(G) =
�
I; (� (Si))i2I ; (Ui)i2I
	
tal que:
1. I é o mesmo conjunto de n jogadores do jogo G;
2. �(Si) é o conjunto de estratégias mistas do jogador i, como de…nido acima;
3. Ui é a função pay-o¤ do jogador i, de…nida como
Ui : � (S1)��(S2)� :::��(Sn) �! R
� = (�1; �2; :::; �n) �! ui (�) =
X
s2S
�1 (s1)�2 (s2) :::�n (sn)ui (s)
� A função utilidade dos jogadores tem a forma da utilidade esperada. Logo, conforme
a teoria da escolha com incerteza, as preferências dos jogadores sobre o espaço de
loterais satisfazem os axiomas da continuidade e da independência.
� A estratégia mista do jogador i pode ser interpretada como a ”expectativa ” dos
demais jogadores quanto às ações daquele jogador.
1
2 Jogos com Estratégias Mistas: Exemplo
2.1 Forma Normal do Jogo em Estratégias Puras
� Considere o jogo G = �I; (Si)i2I ; (ui)i2I	, tal que:
1. I = f1; 2g ;
2. S1= fA;Bg ; S2= fa; b; cg ;
3. u1 : S = S1 � S2 �! R; u2 : S = S1 � S2 �! R, onde
u1 (A; a) = 4; u2 (A; a) = 5;
u1 (A; b) = �1; u2 (A; b) = 0;
u1 (A; c) = 3; u2 (A; c) = 0;
u1 (B; a) = 2; u2 (B; a) = 3;
u1 (B; b) = 2; u2 (B; b) = 3;
u1 (B; c) = 1; u2 (B; c) = 1;
� Representação bimatricial:
jogador 2
a b c
jogador 1
A
B
�
4; 5 �1; 0 3; 0
2; 3 2; 3 1; 1
�
� Conjunto de todas as combinações de estratégias puras:
S = S1 � S2 = f(A; a) ; (A; b) ; (A; c) ; (B; a) ; (B; b) ; (B; c)g
2
2.2 Estratégias Mistas
� ´Uma estratégia mista �1 do jogador 1 é uma distribuição de probabilidade
�1 = (�1 (A) ; �1 (B))
sobre S1 = fA;Bg, onde:
–�1 (A) : probabilidade do jogador 1 jogar A
–�1 (B) : probabilidade do jogador 1 jogar B
–Por de…nição, segue que:
�1 (A) + �1 (B) = 1
1 � �1 (A) � 0
1 � �1 (B) � 0
–Exemplo: �1 (A) = 13 ; �2 (B) =
2
3
=)
�1 =
�
1
3
;
2
3
�
� Conjunto de todas as estratégias mistas do jogador 1:
�(S1) = f(�1 (A) ; �1 (B)) j�1 (A) + �1 (B) = 1; �1 (A) � 0;�1 (B) � 0g
� Uma estratégia pura qualquer é um caso particular de estratégia mista.
–Exemplo:
estratégia pura A () estratégia mista �1=(1; 0)
� Uma estratégia mista do jogador 1 pode ser interpretada como a ”expectativa” do
outro jogador quanto ao plano de ação do jogador 1
3
� Uma estratégia mista �2 do jogador 2 é uma distribuição de probabilidade
�2 = (�2 (a) ; �2 (b) ; �2 (c))
sobre S2 = fa; b; cg, onde:
–�2 (a) : probabilidade do jogador 2 jogar a
–�2 (b) : probabilidade do jogador 2 jogar b
–�2 (c) : probabilidade do jogador 2 jogar c
–Por de…nição, segue que:
�2 (a) + �2 (b) + �2 (c) = 1
1 � �2 (a) � 0
1 � �2 (b) � 0
1 � �2 (c) � 0
–Exemplo: �2 (a) = 0; �2 (b) = 12 ; �2 (c) =
1
2
=)
�2 =
�
0;
1
2
;
1
2
�
� Conjunto de todas as estratégias mistas do jogador 2:
�(S2) = f(�2 (a) ; �2 (b) ; �2 (c)) j�2 (a) + �2 (b) + �2 (c) = 1; �2 (a) � 0;�2 (b) � 0;�2 (c) � 0g
� Uma estratégia pura é um caso particular de estratégia mista
–Exemplo:
estratégia pura b() estratégia mista �2 = (0; 1; 0)
� Uma estratégia mista do jogador 2 pode ser interpretada como a ”expectativa” do
outro jogador quanto ao plano de ação do jogador 2
4
2.3 Combinação de Estratégias Mistas
� Uma combinação de estratégias mistas � especi…ca uma estratégia mista para cada
jogador:
� =
8<:
�1z }| {
(�1 (A) ; �1 (B));
�2z }| {
(�2 (a) ; �2 (b) ; �2 (c))
9=; 2 �(S1)��(S2)
Exemplo:
� =
8>>>>>><>>>>>>:
�1z }| {0BB@
�1(A)z}|{
1
3
;
�1(B)z}|{
2
3
1CCA;
�2z }| {0BB@
�2(a)z}|{
0 ;
�2(b)z}|{
1
2
;
�2(c)z}|{
1
2
1CCA
9>>>>>>=>>>>>>;
� Conjunto de todas as combinações de estratégias mistas:
�(S1)��(S2) = f(�1; �2) : �1 2 �(S1) ; �2 2 �(S2)g
� Cada combinação de estratégias mistas implica a seguinte dist. de prob. sobre os
resultados do jogo:
jogador 2
a b c
jogador 1
A
B
"
�1(A)�2(a)
4;5
�1(A)�2(b)
�1;0
�1(A)�2(c)
3;0
�1(B)�2(a)
2;3
�1(B)�2(b)
2;3
�1(B)�2(c)
1;1
#
Importante observar que:
�1 (A)�2 (a) + �1 (A)�2 (b) + �1 (A)�2 (c) + �1 (B)�2 (a) + �1 (B)�2 (b) + �1 (B)�2 (c) = 1
Exemplo: Seja a estratégia mista do exemplo anterior
jogador 2
a b c
jogador 1
A
B
"
0
4;5
1
6�1;0
1
6
3;0
0
2;3
2
6
2;3
2
6
1;1
#
5
2.3.1 Pay-o¤ Esperado
� Considere uma combinação de estratégias mistas qualquer:
� =
8<:
�1z }| {
(�1 (A) ; �1 (B));
�2z }| {
(�2 (a) ; �2 (b) ; �2 (c))
9=; 2 �(S1)��(S2)
� Combinação � implica a seguinte dist. de prob. s/ os resultados do jogo:
jogador 2
a b c
jogador 1
A
B
"
�1(A)�2(a)
4;5
�1(A)�2(b)
�1;0
�1(A)�2(c)
3;0
�1(B)�2(a)
2;3
�1(B)�2(b)
2;3
�1(B)�2(c)
1;1
#
� Pay-o¤ esperado do jogador 1:
U1 : � (S1)��(S2) �! R
U1 (�) = 4�1 (A)�2 (a) + (�1)�1 (A)�2 (b) + 3�1 (A)�2 (c)
+2�1 (B)�2 (a) + 2�1 (B)�2 (b) + 1�1 (B)�2 (c)
� Pay-o¤ esperado do jogador 2:
U2 : � (S1)��(S2) �! R
U2 (�) = 5�1 (A)�2 (a) + 0�1 (A)�2 (b) + 0�1 (A)�2 (c)
+3�1 (B)�2 (a) + 3�1 (B)�2 (b) + 1�1 (B)�2 (c)
� Exemplo: Combinação de estratégias mistas
� =
8>>>>>><>>>>>>:
�1z }| {0BB@
�1(A)z}|{
1
3
;
�1(B)z}|{
2
3
1CCA;
�2z }| {0BB@
�2(a)z}|{
0 ;
�2(b)z}|{
1
2
;
�2(c)z}|{
1
2
1CCA
9>>>>>>=>>>>>>;
Dist. de prob. sobre resultados do jogo:
jogador 2
a b c
jogador 1
A
B
"
0
4;5
1
6�1;0
1
6
3;0
0
2;3
2
6
2;3
2
6
1;1
#
Pay-o¤ dos jogadores:
U1 (�) = 4 � 0 + (�1) � 1
6
+ 3 � 1
6
+ 2 � 0 + 2 � 2
6
+ 1 � 2
6
=
8
6
U2 (�) = 5 � 0 + 0 � 1
6
+ 0 � 1
6
+ 3 � 0 + 3 � 2
6
+ 1 � 2
6
=
8
6
6
2.4 Pay-o¤ Esperado: Aplicação da Teoria da Incerteza
� Considere uma combinação de estratégias mistas qualquer:
� =
8<:
�1z }| {
(�1 (A) ; �1 (B));
�2z }| {
(�2 (a) ; �2 (b) ; �2 (c))
9=; 2 �(S1)��(S2)
� Combinação � implica a seguinte dist. de prob. s/ os resultados do jogo:
jogador 2
a b c
jogador 1
A
B
"
�1(A)�2(a)
4;5
�1(A)�2(b)
�1;0
�1(A)�2(c)
3;0
�1(B)�2(a)
2;3
�1(B)�2(b)
2;3
�1(B)�2(c)
1;1
#
� Logo, combinação � equivale às seguintes loterias L1 e L2 para jogadores 1 e 2:
L1 = (4;�1; 3; 2; 2; 1 ; �1 (A)�2 (a) ; �1 (A)�2 (b) ; �1 (A)�2 (c) ; �1 (B)�2 (a) ; �1 (B)�2 (b) ; �1 (B)�2 (c))
L2 = (5; 0; 0; 3; 3; 1 ; �1 (A)�2 (a) ; �1 (A)�2 (b) ; �1 (A)�2 (c) ; �1 (B)�2 (a) ; �1 (B)�2 (b) ; �1 (B)�2 (c))
� �(S1)��(S2): conjunto de todas as loterias
� Como jogadores comparam duas loterias q.q? Teoria da escolha sobre incerteza
� Suponha que preferências dos jogadores sobre conjunto de loterias pode ser represen-
tadas por função utilidade v.N-M:
U : � (S1)��(S2) �! R
–Pay-o¤ esperado do jogador 1:
U1 (�) = 4�1 (A)�2 (a) + (�1)�1 (A)�2 (b) + 3�1 (A)�2 (c)
+2�1 (B)�2 (a) + 2�1 (B)�2 (b) + 1�1 (B)�2 (c)
–Pay-o¤ esperado do jogador 2:
U2 (�) = 5�1 (A)�2 (a) + 0�1 (A)�2 (b) + 0�1 (A)�2 (c)
+3�1 (B)�2 (a) + 3�1 (B)�2 (b) + 1�1 (B)�2 (c)
7
2.5 Extensão de um Jogo em Estratégias Puras para Estratégia Mistas
� Conclusão: O jogo em estratégias puras G = �I; (Si)i2I ; (ui)i2I	 ; tal que:
– I = f1; 2g ;
–S1= fA;Bg ; S2= fa; b; cg ;
–u1 : S = S1 � S2 �! R; u2 : S = S1 � S2 �! R, onde
u1 (A; a) = 4; u2 (A; a) = 5;
u1 (A; b) = �1; u2 (A; b) = 0;
u1 (A; c) = 3; u2 (A; c) = 0;
u1 (B; a) = 2; u2 (B; a) = 3;
u1 (B; b) = 2; u2 (B; b) = 3;u1 (B; c) = 1; u2 (B; c) = 1;
foi estendido para um jogo em estratégias mistas
�(G) =
�
I; (� (Si))i2I ; (Ui)i2I
	
tal que:
– I = f1; 2g
–Conjunto das estratégias mistas do gogador 1:
�(S1) = f(�1 (A) ; �1 (B)) j�1 (A) + �1 (B) = 1;�1 (A) � 0;�1 (B) � 0g
–Conjunto de todas as estratégias mistas do jogador 2:
�(S2) = f(�2 (a) ; �2 (b) ; �2 (c)) j�2 (a) + �2 (b) + �2 (c) = 1;�2 (a) � 0;�2 (b) � 0;�2 (c) � 0g
–Pay-o¤ do jogador 1: U1 : � (S1)��(S2) �! R
U1 (�) = 4�1 (A)�2 (a) + (�1)�1 (A)�2 (b) + 3�1 (A)�2 (c)
+2�1 (B)�2 (a) + 2�1 (B)�2 (b) + 1�1 (B)�2 (c)
–Pay-o¤ do jogador 2: U1 : � (S1)��(S2) �! R
U2 (�) = 5�1 (A)�2 (a) + 0�1 (A)�2 (b) + 0�1 (A)�2 (c)
+3�1 (B)�2 (a) + 3�1 (B)�2 (b) + 1�1 (B)�2 (c)
8
3 Equilíbrio de Nash em Estratégias Mistas
De…nição 3 Equilíbrio de Nash em Estratégias Mistas
� Considere um jogo G qualquer e seja �(G) sua extensão para estratégias mistas.
� Uma combinação �� de estratégias mistas
�� = (��1; :::; �
�
i ; :::; �
�
n)
é um Equilíbrio de Nash deste jogo �(G) se e somente se para todo jogador i=1,2...,n,
podemos a…rmar que:
8�i 2 �(Si) ; Ui (��1; :::; ��i ; :::; ��n) � Ui (��1; :::; �i; :::; ��n)
Exercício 1 Derive todos os EN em estratégias mistas no jogo abaixo:
jogador 2
A
(q)
B
(1� q)
jogador 1 a (p)
b (1� p)
�
(2; 1) 0; 0
0; 0 (1; 2)
�
Solução 1 Solução do exercício 1:
� Uma estratégia mista qualquer do jogador 1 é dada por um vetor (p,1-p) onde p é a
probabilidade do jogador 1 jogar a estratégia "a"
� Uma estratégia mista qualquer do jogador 2 é dada pelo vetor (q,1-q) onde q é a
probabilidade do jogador 2 jogar a estratégia "A"
� Para encontrar os ENs em estratégias mistas, é preciso primeiro derivar as funções
de reação dos jogadores 1 e 2
� Função de reação do jogador 1: escolha ótima p do jogador 1 dado que jogador 2
escolhe q
p = R1(q)
� Função de reação do jogador 2: escolha ótima q do jogador 2 dado que jogador 1
escolhe q
q = R2(p)
9
� Derivação da função de reação do jogador 1:
–Suponha que jogador 2 joga estratégia "A" com probabilidade q, ou seja, estratégia
mista (q,1-q)
–Pay-o¤ do jogador 1 quando joga estratégia "a" c/ prob.1 (p=1):
2 � q + 0 � (1� q) = 2 � q
–Pay-o¤ do jogador 1 quando joga estratégia "b" c/prob.1 (p=0):
0 � q + 1 � (1� q) = 1� q
–Logo, é ótimo para jogador 1 jogar estratégia "a" c/ prob.1 (p=1) quando
2 � q > 1� q =) q > 1
3
–Logo, é ótimo para jogador 1 jogar estratégia "b" c/prob.1 (p=0) quando
2 � q < 1� q =) q < 1
3
–Logo, jogador 1 é indiferente entre estratégias "a" e "b" quando
2 � q = 1� q =) q = 1
3
–Função de reação do jogador 1:
p = R1(q) =
8<:
1; se q > 1
3
0; se q < 1
3
[0; 1] ; se q = 1
3
10
� Derivação da função de reação do jogador 2:
–Suponha que jogador 1 joga estratégia "a" com probabilidade p, ou seja, estratégia
mista (p,1-p)
–Pay-o¤ do jogador 2 quando joga estratégia "A" c/prob. 1 (q=1):
1 � p+ 0 � (1� p) = p
–Pay-o¤ do jogador 2 quando joga estratégia "B" c/prob. 1 (q=0):
0 � p+ 2 � (1� p) = 2 � (1� p)
–Logo, é ótimo para jogador 2 jogar estratégia "A" (q=1) quando
p > 2 � (1� p) =) p > 2
3
–Logo, é ótimo para jogador 2 jogar estratégia "B" (q=0) quando
p < 2 � (1� p) =) p < 2
3
–Logo, jogador 2 é indiferente entre estratégias "A" e "B" quando
p = 2 � (1� p) =) p = 2
3
–Função de reação do jogador 2:
q = R2(p) =
8<:
1; se p > 2
3
0; se p < 2
3
[0; 1] ; se p = 2
3
11
� Por de…nição, Equilíbrio de Nash é um vetor ((p�; 1� p�); (q�; 1� q�)) tal que:
p� = R1(q�)
q� = R2(p�)
Então, ENs em estratégias mistas deste jogo são os seguintes:0@0@ p�z}|{1 ; 1�p�z}|{0
1A ;
0@ q�z}|{1 ; 1�q�z}|{0
1A1A() (a;A)
0@0@ p�z}|{0 ; 1�p�z}|{1
1A ;
0@ q�z}|{0 ; 1�q�z}|{1
1A1A() (b; B)
0BB@
0BB@
p�z}|{
2
3
;
1�p�z}|{
1
3
1CCA ;
0BB@
q�z}|{
1
3
;
1�q�z}|{
2
3
1CCA
1CCA
12
Intuição do EN em estratégias mistas :
� Num jogo em estratégias mistas, a estratégia do jogador i pode ser interpretada como
a ”expectativa”dos demais jogadores quanto ao plano de ação do jogador i
� Logo, o EN deste jogo pode ser interpretado como um conjunto de expectativas con-
…rmadas pela ação dos jogadores
Propriedades do EN em estratégias mistas :
� EN em estratégias mistas não necessariamente único
� EN em estratégias puras também é EN em estratégias mistas
� Existência do EN: Teorema de Nash (ver proposição adiante)
Proposição 1 Teorema de Nash
� Considere um jogo G = �I; (Si)i2I ; (ui)i2I	 qualquer, tal que Si é …nito para todo i.
� Seja �(G) a extensão deste jogo para estratégias mistas.
� Então, podemos a…rmar que o jogo �(G) possui um EN
Exercício 2 Veri…que que o jogo abaixo não possui equilíbrio de Nash em estratégias puras,
mas possui equilíbrio de Nash em estratégias mistas
A B
a
b
�
0; 0 0;�1
1; 0 �1; 3
�
13
4 Dominância em Estratégias Mistas
Proposição 2 Uma estratégia mista que atribui probabilidade positiva a uma estratégia pura
estritamente dominada é também estritamente dominada
Exemplo 1 Neste jogo, W domina estritamente T:
Q W T
A
B
�
1; 0 1; 2 0; 1
0; 3 0; 1 2; 0
�
Considere a estratégia mista �2:
�2 (Q) = 0; 3; �2 (W ) = 0; 6; �2 (T ) = 0; 1
Transferindo a probabilidade atribuída a T para a estratégia W, obtemos uma nova estraté-
gia mista �02, dada por,
�02 (Q) = 0; 3; �
0
2 (W ) = 0; 7; �
0
2 (T ) = 0; 0
que domina estritamente a primeira
Proposição 3 Uma estratégia mista estritamente dominada não faz parte de um EN em
estratégias mistas
Corolário 1 Suponha que uma estratégia mista atribui probabilidade positiva a uma estraté-
gia pura estritamente dominada.
Logo, pela proposição (2), ela tb é estritamente dominada por outra estratégia mista.
Então, pela proposição (3), ela não pode fazer parte de um EN em estratégias mistas
14
� Num jogo com estratégias puras, se uma estratégia si é estritamente dominada por
outra estratégia pura s0i, então nunca é ótimo jogar si
–A recíproca, no entanto, não é verdadeira
Exemplo 2 Considere o jogo abaixo:
jogador 2
L R
jogador 1
T
M
B
24 3;_ 0;_0;_ 3;_
1;_ 1;_
35
� B nunca é estratégia ótima:
–ótimo p/ jogador 1 jogar T quando jogador 2 joga L
–ótimo p/ jogador 1 jogar M quando jogador 2 joga R
� No entanto, B não é estritamente dominada
� Num jogo com estratégias mistas, a recíproca da proposição acima também é ver-
dadeira, ou seja, uma estratégia pura si é estritamente dominada por uma estratégia
mista �i se e somente se nunca é ótimo jogar si.
Exemplo 3 Seja q a prob. do jogador 2 jogar L no exemplo acima. Então,...
� B nunca é estratégia ótima:
– se q � 1
2
, então é ótimo para jogador 1 jogar T
– se q � 1
2
, então é ótimo para jogador 1 jogar M
� estratégia mista �1 =
�
1
2
; 1
2
; 0
�
domina estritamente B
15