Nota de Aula 04 - Teoria dos Jogos

Prévia do material em texto

DEPARTAMENTO DE ECONOMIA / PUC-Rio
MICROECONOMIA II
Profs. Marcos Antonio C. da Silveira e Eduardo P.S. Fiuza
Nota de Aula 4: Teoria dos Jogos
Bibliogra…a:
� Varian, cap. 28; Cabral, cap. 4; Gibbons, cap. 1
1 Objetivo
� Jogo: instrumental analítico para modelagem da interação estratégica entre diferentes
agentes tomadores de decisões
� Interação estratégica: pay-o¤ de cada jogador depende não apenas de sua estratégia,
mas da estratégia dos demais jogadores
� Combinação de estratégias =) Resultado do jogo: pay-o¤ (ganho) de cada agente
� Estratégia ótima de cada agente depende de suas conjecturas quanto às estratégias
dos demais agentes
� O que a teoria prediz quanto ao resultado de um jogo, ou seja, quanto às estratégias
implementadas pelos agentes?
2 Motivação
� Problemas de interação estratégica disseminados na Economia e outras Ciências Socias
e em estratégia militar.
� Importante no estudo de Organização Industrial:
–Mercado competitivo: preço da …rma dado pelo mercado
–Mercado oligopolista: preço da …rma depende de sua produção e das concorrentes
3 Representação dos Jogos
� Forma normal: lista os jogadores, as estratégias e os respectivos payo¤s (ganhos). É
mais adequado e mais usado para representar jogos em que as ações são simultâneas
(jogos estáticos)
� Forma extensiva (diagramas em árvores): lista os jogadores, suas ações disponíveis a
cada estágio do jogo em que eles têm a vez de jogar, e seus payo¤s (ganhos). É o mais
adequado para representar jogos em que as ações são sequenciais (jogos dinâmicos).
Mas as estratégias –que são as sequências de ações possíveis de cada jogador –não
são prontamente visíveis neste formato.
1
4 Informação Completa X Informação Incompleta
� Combinação de estratégias =) Resultado do jogo: pay-o¤ dos jogadores
� Jogos de informação completa: função pay-o¤ de cada jogador é de conhecimento
comum dos jogadores
� Jogos de informação incompleta: algum jogador é incerto quanto à função pay-o¤ de
outro jogador (Ex.: leilão)
� Nesta nota de aula, estudamos apenas jogos com informação completa
5 Jogos na Forma Normal
De…nição 1 A representação de um jogo G na forma normal consiste de:
1. um conjunto I de n jogadores, indexados por i = 1; 2; :::; n;
2. um conjunto de estratégias Si para cada jogador i, onde si 2 Si é uma estratégia qualquer
do jogador i;
3. uma função pay-o¤ ui para cada jogador i, de…nida como
ui : S � S1 � S2 � :::� Sn �! R
s = (s1; s2; :::; sn) �! ui (s) = ui (s1; s2; :::; sn)
� Um jogo na forma normal é denotado como G = �I; (Si)i2I ; (ui)i2I	
� Si : conjunto das estratégias puras do jogador i
� Estratégia pura: o jogador joga com certeza aquela estratégia; não existe randomização
como a que acontece nas estratégias mistas, a serem vistas na próxima aula.
� Vetor s = (s1; s2; :::; sn) 2 S é uma combinação de estratégias puras, uma para cada
jogador
� Produto cartesiano S : conjunto de todas as combinações de estratégias puras
� Pay-o¤ de cada jogador depende não apenas de sua estratégia, mas também da es-
tratégia dos demais jogadores (interação estratégica entre os jogadores)
� Um jogo na forma normal com apenas dois jogadores admite uma representação bi-
matricial
2
Exemplo 1 Seja o jogo G =
�
I; (Si)i2I ; (ui)i2I
	
com n=2, tal que:
� I = f1; 2g ;
� S1= fA;Bg ; S2= fa; b; cg ;
� Conjunto de todas as combinações de estratégias dado por:
S = S1 � S2 = f(A; a) ; (A; b) ; (A; c) ; (B; a) ; (B; b) ; (B; c)g
� 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;
� Este jogo pode ser representado através da bi-matriz:
jogador 2
a b c
jogador 1
A
B
�
4; 5 �1; 0 3; 0
2; 3 2; 3 1; 1
�
� Veja outro jogo:
jogador 2
E D
jogador 1
A
B
�
1; 2 0; 1
2; 1 1; 0
�
� Qual seria a representação deste jogo na forma extensiva? Veja Fig.1
3
 
2,1 0,1 1,0 1,2 
E E D D 
A B 
FIGURA 1 
JOGO ESTÁTICO NA FORMA EXTENSIVA 
2 2 
1 
6 Dominância de Estratégias
� Note que o jogo acima pode ser resolvido da seguinte forma: não é racional para o
jogador 1 jogar A, pois, independente do que o jogador 2 jogar, o payo¤ de 1 jogando
B sempre é maior que jogando A.
� Da mesma forma, não é racional para o jogador 2 jogar D, pois, independente do que
1 jogar, o payo¤ de 2 jogando E é maior que jogando D.
� Portanto, 1 sempre joga B e 2 joga E. A solução do jogo é (A,E), que gera payo¤s (1,2).
Diz-se que o jogo é solucionável por eliminação iterada de estratégias estritamente
dominadas.
6.1 Dominância Fraca e Estrita
Notation 1 Considere a notação:
s�i = (s1; :::; si�1; si+1; :::; sn) 2 S�i = S1 � :::� Si�1 � Si+1 � :::� Sn
s = (si; s�i) = (s1; :::; si�1; si; si+1; :::; sn) 2 S
De…nição 2 Considere um jogo G qualquer. A estratégia si 2 Si do jogador i domina fraca-
mente a estratégia �si 2 Si deste mesmo jogador i se e somente se
ui (si; s�i) � ui (�si; s�i) ; 8s�i 2 S�i
e, além disso, existe pelo menos uma combinação de estratégias s�1 2 S�i dos demais
jogadores, tal que
ui (si; s�i) > ui (�si; s�i)
Exemplo 2 No jogo adiante, D domina fracamente U, enquanto L domina fracamente R:
jogador 2
L R
jogador 1
U
M
D
24 5; 1 4; 06; 1 3; 1
6; 4 4; 4
35
De…nição 3 Considere um jogo G qualquer. A estratégia si 2 Si do jogador i domina estri-
tamente a estratégia �si 2 Si deste mesmo jogador i se e somente se
ui (si; s�i) > ui (�si; s�i) ; 8s�i 2 S�i
Exemplo 3 No jogo adiante, M domina estritamente D e U:
jogador 2
L R
jogador 1
U
M
D
24 �4;�1 �1; 1�1; 1 1;�1
�2; 5 �3; 2
35
E entre L e R? Um domina o outro?
Proposição 1 Dominância estrita implica dominância fraca, mas a recíproca não é ver-
dadeira
4
6.2 Eliminação Iterada de Estratégias Estritamente Dominadas (EIEED)
� A …m de encontrar a solução do jogo, é preciso fazer hipóteses quanto ao comporta-
mento dos jogadores e quanto a sua estrutura de informação
� Quanto ao comportamento dos jogadores, é comum supor a hipótese de racionalidade
� O objetivo de um jogador racional é maximizar sua função pay-o¤
–Logo, um jogador racional jamais escolhe uma estratégia estritamente dominada
� Quanto à estrutura de informação, uma alternativa é supor "common knowledge"
De…nição 4 Common Knowledge signi…ca que todo jogador conhece a estrutura do jogo,
todo jogador sabe que os outros jogadores conhecem a estrutura do jogo, todo jogador sabe
que os outros jogadores sabem que ele conhece a estrutura do jogo, e assim por diante.
� As hipóteses de racionalidade e common knowledge implicam que, se uma combinação
de estratégias s 2 S é o resultado da aplicação do processo EIEED sobre um jogo G,
então ela é o resultado deste jogo.
Exemplo 4 A…nal, o que é EIEED? Vamos resolver o jogo adiante usando este processo:
a b c
A
B
�
1; 0 1; 2 0; 1
0; 3 0; 1 2; 0
�
Na primeira rodada de racionalidade, b domina estritamente c. Então, c é eliminada:
a b
A
B
�
1; 0 1; 2
0; 3 0; 1
�
Na segunda rodada de racionalidade, A domina estritamente B. Então, B é eliminada:
a b
A
�
1; 0 1; 2
�
Na terceira rodada de racionalidade, b domina estritamente a. Então, a é eliminada e o
resultado do jogo é (A,b)
5
Exemplo 5 No jogo adiante, nenhuma estratégia é eliminada através do EIEED:
L C R
U
M
D
24 0; 4 4; 0 5; 34; 0 0; 4 5; 3
3; 5 3; 5 6; 6
35
Exemplo 6 No jogo adiante, uma das estratégias é eliminada por dominância estrita, mas
isto não é su…ciente para resolver o jogo por EIEED:
L C R
U
M
D
24 3; 4 4; 0 5; 34; 5 0; 4 5; 3
3; 6 3; 5 6; 6
35
Na primeira rodada, L domina estritamente C. Então, C é eliminada:
L R
U
M
D
24 3; 4 5; 34; 5 5; 3
3; 6 (6; 6)
35
Na segunda rodada, nehuma estratégia é eliminada
6
7 Equilíbrio de Nash
� Nem sempre a aplicação do processo de EIEED produz o resultado do jogo
–Quando isto ocorre, como caracterizar o resultado do jogo?
–Primeiro passo é estabelecer o conceito de Equilíbrio de Nash
� Antes, precisamos entender o que é estratégia ótima. Considerejogo do ex. (1):
jogador 2
a b c
jogador 1
A
B
�
4; 5 �1; 0 3; 0
2; 3 2; 3 1; 1
�
–Se jogador 1 joga A, então é ótimo para jogador 2 jogar a
–Se jogador 1 joga B, então é ótimo para jogador 2 jogar a ou b
–Se jogador 2 joga a, então é ótimo para jogador 1 jogar A
–Se jogador 2 joga b, então é ótimo para jogador 1 jogar B
–Se jogador 2 joga c, então é ótimo para jogador 1 jogar A
De…nição 5 Equilíbrio de Nash
� Considere um jogo G qualquer
� Uma combinação de estratégias
s� = (s�1; :::; s
�
i ; :::; s
�
n)
é um Equilíbrio de Nash (EN) deste jogo quando, para todo jogador i=1,2...,n, pode-
se a…rmar que s�i é uma estratégia ótima do jogador i dado que os demais jogadores
jogam suas estratégias em s�, ou seja,
8si 2 Si; ui (s�1; :::; s�i ; :::; s�n) � ui (s�1; :::; si; :::; s�n) :
Exemplo 7 As combinações de estratégias (A; a) e (B; b) são EN no jogo do exemplo 1:
jogador 2
a b c
jogador 1
A
B
�
4; 5 �1; 0 3; 0
2; 3 2; 3 1; 1
�
� Um jogo com estratégias puras pode ter nenhum, um ou mais de um EN:
Exemplo 8 Jogo adiante não tem EN:
jogador 2
a b
jogador 1
A
B
�
0; 0 0;�1
1; 0 �1; 3
�
7
Exemplo 9 Jogo adiante tem apenas um EN: (A; b)
a b c
A
B
�
1; 0 1; 2 0; 1
0; 3 0; 1 2; 0
�
Exemplo 10 Jogo adiante tem 2 ENs: (A; a); (B; b)
jogador 2
a b
jogador 1
A
B
�
2; 1 0; 0
0; 0 1; 2
�
� Intuição do Equilíbrio de Nash:
– jogadores são racionais e conhecem tão bem o jogo quanto o teorista =)
–qualquer previsão do resultado do jogo pelo teorista corroborada pelos jogadores=)
– se resultado previsto não é EN, então algum jogador não é racional
– conclusão: equilíbrio de Nash é condição mínima para que uma combinação de
estratégias seja resultado do jogo
� Problemas do EN como solução do jogo:
–EN pode não existir
–pode existir mais de um EN. Qual deles é o resultado do jogo? Re…namentos do
EN
� Equilíbrio de Nash X E…ciência de Pareto:
–um EN não necessariamente é uma solução ótima no sentido de Pareto
–uma solução ótima no sentido de Pareto não necessariamente é um EN
Exemplo 11 (Dilema dos Prisioneiros) No jogo adiante:
� (C,C) é um EN Pareto-ine…ciente,...
� enquanto (NC,NC) é ótimo de Pareto, embora não seja um EN:
prisioneiro 2
NC C
prisioneiro 1
NC
C
� �1;�1 �9; 0
0;�9 �6;�6
�
8
8 Relação entre Equilíbrio de Nash e Dominância de Estratégias
� As proposições abaixo estabelecem uma relação entre EIEED e EN?
Proposição 2 Se uma combinação de estratégias s� = (s�1; :::; s�i ; :::; s�n) é o resultado da apli-
cação do processo EIEED sobre um jogo, então s� é um EN deste jogo
Exemplo 12 No jogo do exemplo (4)
a b c
A
B
�
1; 0 (1; 2) 0; 1
0; 3 0; 1 2; 0
�
o processo EIEED permite encontrar o resultado do jogo (A,b). Logo, pela proposição (2),
(A,b) é um EN deste jogo.
Proposição 3 Uma estratégia si do jogador i não pode fazer parte de um EN se ela é elimi-
nada em alguma etapa do processo EIEED
Exemplo 13 Considere o jogo adiante:
L C R H
U
M
D
V
2664
5; 4 4; 0 5; 3 6; 3
4; 5 0; 4 3; 3 4; 2
3; 6 3; 5 6; 6 2; 2
4; 2 2; 1 3; 4 7; 7
3775
Na primeira rodada, U domina estritamente M e L domina estritamente C. Logo, M e C
são eliminadas:
L R H
U
D
V
24 5; 4 5; 3 6; 33; 6 6; 6 2; 2
4; 2 3; 4 7; 7
35
Na segunda rodada, nenhuma estratégia é eliminada.
Neste exemplo, existem três ENs cujas estratégias não são eliminadas pelo processo EIEED.
� Segue da proposição (3) acima que o EIEED facilita a determinação do EN quando o
jogo é muito complexo, mesmo se este processo não indique o resultado …nal do jogo
–Como? Antes de procurar EN, elimine todas as estratégias estritamente domi-
nadas
–Observe como esta sugestão facilitou achar o EN no exemplo (13) acima!!!!
Corolário 1 Corolário da Proposição (3). Um jogo com mais de um EN não possui uma
combinação de estratégias s = (s1; :::; si; :::; sn) que seja o resultado da aplicação do EIEED
Exemplo 14 Considere o jogo do exemplo anterior. Como existem três ENs, o processo
EIEED não permite encontrar o resultado do jogo.
9
� A proposição (3) estabelece que uma estratégia estritamente dominada não pode fazer
parte de um EN
–Pergunta: uma estratégia fracamente dominada pode fazer parte de um EN?
–Exemplo adiante responde esta pergunta:
L C R
U
M
D
24 4; 4 4; 0 5; 34; 5 0; 4 5; 3
3; 6 3; 5 6; 6
35
� (M,L) é um EN do jogo. Porque?
� L domina estritamente C e U domina fracamente M
� após L eliminar C na primeira rodada de racionalidade, U não mais domina
fracamente M
� Conclusão: uma estratégia fracamente dominada pode fazer parte de um EN
10