Teoria dos Jogos Microeconomia Curso Cec lia Menon

Prévia do material em texto

Notas de Aula 7 - Teoria dos Jogos
Microeconomia
Curso Cećılia Menon
1 Introdução
1.1 Interdependência Estratégica
1.1.1 Teoria dos Jogos
A teoria dos jogos permite modelar comportamentos estratégicos dos agentes econômicos. É o instrumento
adequado quando existe interdependência estratégica entre os agentes do modelo analisado.
No modelo de consumo usual, o consumidor decide entre posśıveis cestas de bens, dados os preços e a
sua renda. No modelo da firma competitiva, a firma maximiza o seu lucro, dada a sua tecnologia de
produção e dados os preços dos insumos e dos bens que vende. No modelo de equiĺıbrio geral competitivo,
tanto os consumidores quanto as firmas são tomadores de preços: tomam os preços como dados e não há
interdependência estratégica entre os agentes econômicos.
Porém, existem situações onde as ações de um agente dependem das ações de outro agente diretamente.
Nesses casos, assumimos que o payoff (utilidade) do agente depende não só da sua ação, mas da ação de
outros agentes. Modelos de oligopólio são um exemplo, em que o lucro de determinada firma depende do
comportamento de suas rivais.
Em um jogo, cada jogador deve levar em conta a estratégia dos outros jogadores antes de escolher o melhor
para si. Isso gera uma circularidade, caracteŕıstica fundamental da teoria dos jogos.
O objetivo da teoria dos jogos é determinar o resultado de um jogo. Cada método de análise dá origem a
um conceito de solução particular, chamado equiĺıbrio.
A maioria dos conceitos tem sua origem no conceito de equiĺıbrio de Nash e são, usualmente, equiĺıbrios de
Nash que satisfazem certas propriedades. Por isso, são chamados de refinamentos. Cada refinamento tenta
solucionar alguma deficiência do conceito de equiĺıbrio de Nash particular a alguma situação ou modelo.
1.2 Noções Preliminares
1.2.1 Jogo
Definição (informal): Jogo. Um jogo refere-se a qualquer situação envolvendo dois ou mais agentes,
chamados jogadores, onde exista interdependência estratégica.
Para descrevermos um jogo é necessário conhecermos três objetos:
• Os jogadores,
• A regra do jogo,
• O resultado (payoff) do jogo.
1.2.2 Hipóteses sobre os Jogadores
São feitas duas hipóteses básicas sobre os jogadores:
1. Os jogadores são racionais. As ações de um jogador são consistentes com o objetivo desejado: maxi-
mizar o seu payoff ou a sua a utilidade.
1
2. Os jogadores são inteligentes. Os jogadores sabem tudo o que sabemos sobre o jogo e conseguem fazer
as mesmas inferências que fazemos sobre a situação em que se encontram.
A segunda hipótese não é tão inócua quanto parece. Na teoria de equiĺıbrio geral os indiv́ıduos são racionais,
mas não é necessário que sejam inteligentes no sentido acima: os agentes econômicos não precisam conhecer
toda a estrutura de teoria de equiĺıbrio geral ao tomarem suas decisões.
1.2.3 Formas de Representação
Existem duas formas de representarmos um jogo:
FORMA NORMAL: Representação em forma matricial. Esta forma é adequada para situações onde
os jogadores se “movem” (decidem suas ações) simultaneamente. Modelo estático. Esta forma também é
conhecida como forma estratégica.
FORMA EXTENSIVA: Representação em forma de árvore. Esta forma é adequada para situações onde
exista uma ordem cronológica dos eventos do jogo. Modelo dinâmico.
Existe uma correspondência entre essas duas formas, que veremos mais a frente.
1.2.4 Jogos Não-Cooperativos
Vamos estudar jogos não-cooperativos : analisamos cada agente separadamente e não como um grupo. Essa
definição não implica que um jogador não possa cooperar com o outro, ela é apenas de cunho metodológico,
onde cada agente é visto como uma entidade separada, autônoma, e não há grupos de agentes se comportando
como um único agente.
1.3 Conhecimento Comum
1.3.1 Ideia
Uma hipótese bastante usada em teoria dos jogos é a de conhecimento comum (“common knowledge”). Essa
hipótese diz que a racionalidade dos jogadores e a estrutura do jogo é de conhecimento comum para todo
jogador.
Se considerarmos dois jogadores, um determinado fato é de conhecimento comum dos jogadores se o jogador
1 conhece o fato, se o jogador 1 sabe que o jogador 2 conhece o fato, se o jogador 1 sabe que o jogador 2
sabe que o jogador 1 conhece o fato, se o jogador 1 sabe que o jogador 2 sabe que o jogador 1 sabe que o
jogador 2 conhece o fato, e assim vai ad infinitum, o mesmo racioćınio valendo para o jogador 2.
Essa hipótese é fundamental para a validade de certos procedimentos, tais como os procedimentos de elim-
inação de estratégias dominadas. Mais ainda, ela é fundamental para o conceito de equiĺıbrio de Nash
(existem artigos que relaxam a hipótese de conhecimento comum, sob certas condições).
Myerson (1991) argumenta que a hipótese de jogadores inteligentes implica supor que a estrutura do jogo é
de conhecimento comum desses jogadores.
2
2 Jogos na Forma Estratégica
2.1 Definições e Exemplos de Jogos
2.1.1 Jogo na Forma Estratégica
Definição: Jogo na Forma Estratégica (ou Forma Normal). Um jogo na forma estratégica é uma
coleção G = (Si, ui)
I
i=1, onde I é o número de jogadores, Si é o conjunto de estratégias dispońıveis ao
jogador i, para todo i ∈ I, e ui :
∏I
j=1 Sj → R é a função de payoff (a utilidade) do jogador i, que depende
das estratégias de todos os jogadores. Dizemos que um jogo na forma normal é finito se o conjunto das
estratégias Si é finito para todo i, i = 1, . . . , I.
Na forma normal não nos preocupamos com cada ação do jogador, mas apenas com cada estratégia do
jogador, o conjunto de todas as ações que podem ser tomadas no decorrer de uma partida do jogo, incluindo
ações para qualquer situação de jogo. Para certos jogos, como veremos a frente, a estratégia do jogador
pode condensar uma quantidade enorme de informação, descrevendo um número muito grande de ações a
serem tomadas ao longo do jogo.
Observe que a interdependência estratégica entre os agentes do modelo analisado aparece explicitamente
na hipótese de que o payoff de cada jogador depende das estratégias de todos os outros jogadores: ui :
S1 × S2 × · · · × Si × · · · × SI → R, ou seja, ui depende não apenas da estratégia si escolhida por i, mas
também das estratégias de todos os outros jogadores, ui(s1, s2, . . . , si, . . . , sI).
2.1.2 Exemplos
Exemplo 1: “Cara ou Coroa”. Neste jogo com duas pessoas, cada jogador escolhe o lado de uma moeda,
sem que o outro jogador tome conhecimento de sua escolha. Os dois jogadores revelam simultaneamente
o lado escolhido. Se os lados escolhidos forem iguais, o jogador 1 paga R$ 1,00 ao jogador 2. Se forem
distintos, o jogador 2 paga R$ 1,00 ao jogador 1. A matriz abaixo descreve este jogo.
1↓ / 2 → Cara Coroa
Cara −1, 1 1,−1
Coroa 1,−1 −1, 1
Notação: Vamos usar a seguinte convenção para todos os jogos representados na forma matricial: o primeiro
elemento em cada célula da matriz é o payoff do jogador 1 (“jogador-linha”) e o segundo elemento da célula
é o payoff do jogador 2 (“jogador-coluna”).
No jogo “Cara ou Coroa”, fica claro que cada jogador deve agir de modo impreviśıvel. Logo, quando os
jogadores decidem estrategicamente, pode ocorrer que a melhor forma de agir seja escolher de modo aleatório
ou de modo que o seu rival não saiba exatamente o que ele escolherá.
Para esse jogo, temos que:
Jogadores: I = {1, 2};
Estratégias: S1 = S2 = {Cara, Coroa};
Payoffs: u1(Cara,Coroa) = u1(Coroa,Cara) = 1;
u1(Cara,Cara) = u1(Coroa,Coroa) = −1;
u2(s1, s2) = −u1(s1, s2), ∀(s1, s2) ∈ S1 × S2.
Observe que esse é um jogo de soma zero: o ganho de um jogador é igual à perda do outro jogador. Para
jogos de soma zero com dois jogadores, os conceitos de solução usados envolvem os jogadores randomizarem
suas estratégias. Esse tipo de jogo foi extensivamente estudado von Neuman e Morgenstern, no livro “theory
of games and economic behavior”,publicado em 1944 e considerado um dos marcos da teoria dos jogos.
3
Exemplo 2: Dilema dos Prisioneiros. Luiz Alberto e Laelio foram presos e estão sendo interrogados
separadamente, acusados de um crime. Se ambos confessarem o crime, eles receberão uma pena de 3 anos
na cadeia. Se ambos não confessarem o crime, a pena será de apenas dois anos, por falta de evidência.
Porém, o promotor pode fazer uma acordo com um deles, dando uma pena de apenas um ano na prisão para
quem confessar e, para quem não confessar, de cinco anos na prisão, por não ter colaborado com a justiça.
A matriz abaixo descreve este jogo.
L.A.↓ / Laelio → Confessar Não Confessar
Confessar −3,−3 −1,−5
Não Confessar −5,−1 −2,−2
Exemplo 3: Problema de Coordenação. Suponha que duas pessoas estão viajando separadamente para
o Rio de Janeiro e combinaram de se encontrar para almoçar no dia seguinte. Porém esqueceram de marcar
o restaurante e não estão conseguindo se comunicar. Eles costumam almoçar sempre em dois restaurantes,
um no centro da cidade e outro na Barra da Tijuca. O almoço no restaurante da barra é mais agradável do
que o almoço no restaurante do centro. Porém, eles se desencontrarem é a pior situação posśıvel. A matriz
abaixo descreve este jogo.
1↓ / 2 → Barra Centro
Barra 3, 3 0, 0
Centro 0, 0 1, 1
Exemplo 4: Batalha dos Sexos. Nelson e Renata querem fazer um programa domingo à tarde. Con-
cordaram com duas opções: ir ao jogo do Corintians ou fazer compras. Os dois preferem estar juntos a
fazerem os passeios separados, mas Nelson prefere ir ao jogo e Renata prefere ir às compras. A matriz
abaixo descreve este jogo.
Nelson↓ / Renata → Futebol Compras
Futebol 2, 1 0, 0
Compras 0, 0 1, 2
A batalha dos sexos modela também um problema de coordenação, mas que envolve uma disputa de poder.
Veremos mais a frente que esse jogo tem dois equiĺıbrios, em que ambos os jogadores devem coordenar suas
estratégias para alcançar um dos equiĺıbrios. Porém, o equiĺıbrio que o jogador 1 prefere, (U,L), é diferente
do equiĺıbrio que o jogador 2 prefere, (D,R), (e ambos preferem estar em uma situação de equiĺıbrio do que
estar em uma situação de desequiĺıbrio, (U,R) ou (D,L)). Neste caso, podemos ter uma disputa de poder
entre os jogadores, onde cada um tenta implementar o seu equiĺıbrio preferido.
2.2 Conceitos de Dominância e Estratégias Racionalizáveis
2.2.1 Estratégias Estritamente Dominantes
Considere um jogo com I jogadores. Vamos representar em negrito um conjunto de estratégias de todos os
jogadores: s = (s1, s2, . . . , sI). Vamos usar a notação s−i = (s1, s2, . . . , si−1, si+1, . . . , sI) para representar
um conjunto de estratégias de todos os jogadores, exceto o jogador i. Porém, nas definições a seguir, vamos
supor dois jogadores apenas.
Definição: Estratégia Estritamente Dominante. A estratégia ŝ1 é estritamente dominante para o
jogador 1 em um dado jogo se para toda estratégia s1 6= ŝ1, s1 ∈ S1, onde S1 representa o conjunto de todas
as estratégias dispońıveis para o jogador 1, vale:
u1(ŝ1, s2) > u1(s1, s2), para todo s2 ∈ S2.
4
(de modo análogo podemos definir estratégia estritamente dominante para o jogador 2).
Logo, uma estratégia si é estritamente dominante para o jogador i, i = 1, 2, se ela for a única estratégia que
maximiza o payoff desse jogador, quaisquer que sejam as estratégias escolhidas pelos outros jogadores.
Para o jogo do dilema dos prisioneiros, é fácil verificar que Confessar é uma estratégia estritamente dominante
para os dois prisioneiros. Ela é a melhor estratégia para cada prisioneiro, independentemente do que o
outro prisioneiro escolha. Nesse caso, dizemos que (C,C) é um equiĺıbrio em estratégias estritamamente
dominantes.
Observe que o equiĺıbrio (C,C) é Pareto dominado pelo conjunto de estratégias (NC,NC), ou seja, cada
jogador obtém um payoff maior em (NC,NC) do que em (C,C). Temos, então, um caso onde o comporta-
mento individual maximizador dos agentes envolvidos resulta em um equiĺıbrio Pareto ineficiente. Logo, na
presença de interdependência estratégica, a interação de jogadores cujo objetivo é maximizar o seu próprio
bem-estar pode levar a situações Pareto-ineficientes.
Estratégias estritamente dominantes não são comuns. Existem várias situações, como no exemplo abaixo,
onde não existem estratégias dominantes para nenhum dos jogadores.
Exemplo: Considere o seguinte jogo:
1↓ / 2 → L M R
U 5, 2 4, 3 7, 2
C 1, 4 3, 2 8, 1
D 4, 3 3, 2 6, 5
Apesar de estratégias estritamente dominantes serem raras, podemos usar um conceito similar, de estratégia
estritamente dominada, para eliminarmos estratégias que nunca devem ser escolhidas pelo jogador.
2.2.2 Estratégia Estritamente Dominada
Definição: Estratégia Estritamente Dominada. Uma estratégia s̄1 é estritamente dominada para o
jogador 1 quando existe uma outra estratégia ŝ1 ∈ S1 tal que:
u1(ŝ1, s2) > u1(s̄1, s2), para todo s2 ∈ S2.
Dizemos que ŝ1 domina estritamente s̄1 (de modo análogo podemos definir estratégia estritamente dominada
para o jogador 2).
Portanto, uma estratégia estritamente dominante é uma estratégia que domina estritamente todas as outras
estratégias do jogador. Podemos dizer também que todas as outras estratégias são estritamente dominadas
pela estratégia estritamente dominante.
Vamos analisar o jogo acima, dado por:
1↓ / 2 → L M R
U 5, 2 4, 3 7, 2
C 1, 4 3, 2 8, 1
D 4, 3 3, 2 6, 5
Para o jogador 1, a estratégia D é estritamente dominada pela estratégia U . Essa é a única estratégia
estritamente dominada no jogo acima. Se eliminarmos essa estratégia do jogo, usando o argumento de que o
jogador 1 nunca a escolherá, já que U traz um payoff sempre maior, qualquer que seja a jogada de 2, então
obtemos o jogo reduzido, dado por:
5
1↓ / 2 → L M R
U 5, 2 4, 3 7, 2
C 1, 4 3, 2 8, 1
Para esse “subjogo”, a estratégia M domina estritamente R, para o jogador 2. Eliminando a estratégia R,
obtemos o seguinte jogo reduzido:
1↓ / 2 → L M
U 5, 2 4, 3
C 1, 4 3, 2
Observe que para este subjogo, a estratégia U domina estritamente C, para o jogador 1. Eliminando C,
obtemos:
1↓ / 2 → L M
U 5, 2 4, 3
Finalmente, a estratégia L é estritamente dominada por M , para o jogador 2. Por meio desse “procedimento
de eliminação de estratégias estritamente dominadas (PEEED)”, obtemos (U,M) (isto é, o jogador 1 escolhe
U , o jogador 2 escolhe M) como solução do jogo (dizemos que (U,M) é um equiĺıbrio obtido pela eliminação
de estratégias estritamente dominadas).
A ideia do procedimento é, portanto, simples. Ele usa implicitamente a hipótese de conhecimento comum
da racionalidade e da estrutura do jogo para todos os jogadores, pois, para encontrarmos a solução (U,M),
supomos implicitamente que o jogador 2 sabe que o jogador 1 é racional e nunca jogará a estratégia D.
Como o jogador 1 sabe que o jogador 2 é racional e também que 2 sabe que ele é racional e nunca jogará D,
então o jogador 1 infere que 2 nunca jogará R. É necessário continuar com esse racioćınio para podermos
concluir que (U,M) é a solução do jogo.
A formalização do PEEED pode ser feita do seguinte modo:
Procedimento de Eliminação de Estratégias Estritamente Dominadas (PEEED): Considere o
jogo G = (Si, ui)
I
i=1. Seja S
0
i = Si, para cada jogador i. Para n ≥ 1, seja Sni o conjunto das estratégias
do jogador i resultante da n-ésima etapa de eliminação, ou seja, si ∈ Sni se si ∈ Sn−1i não é estritamente
dominada em Sn−1i (no jogo dado por G
n−1 = (Sn−1i , ui)
I
i=1).
Definição: Estratégia Iterativamente Estritamente Não-Dominada. A estratégia si do jogador i é
iterativamente estritamente não dominada em S (ou sobrevive ao PEEED) se si ∈ Sni , para todo n ≥ 1.
O problema com o PEEED é que ele também nem sempre leva a alguma solução. No exemplo abaixo,
por exemplo, não existe nenhuma estratégia estritamente dominada e, portanto, não conseguimos eliminarnenhuma estratégia do jogo usando o PEEED. Logo, não conseguimos fazer qualquer predição mais acurada
sobre qual deve ser o seu resultado (ou, pelo menos, o que não pode ser resultado).
2.2.3 Estratégias Fracamente Dominantes
Exemplo: Considere o jogo:
1↓ / 2 → L R
U 1, 1 0, 0
D 0, 0 0, 0
6
Para esse jogo, não existem nem estratégias estritamente dominantes nem estratégias estritamente domi-
nadas.
Podemos enfraquecer as definições de dominância estrita, relaxando a exigência de que o payoff seja sempre
estritamente maior nas definições acima. Para o relaxamento da noção de dominância estrita, obtemos o
seguinte conceito.
Definição: Estratégia Fracamente Dominante. Uma estratégia ŝ1 ∈ S1 é fracamente dominante para
o jogador 1 se para toda s1 6= ŝ1, s1 ∈ S1, vale:
u1(ŝ1, s2) ≥ u1(s1, s2), para todo s2 ∈ S2,
com desigualdade estrita para pelo menos um s2 (de modo análogo podemos definir estratégia estritamente
dominada para o jogador 2).
Evidentemente, toda estratégia fortemente dominante é fracamente dominante, mas a volta não vale.
No jogo acima, as estratégias D de 1 e R de 2 são estratégias fracamente dominadas (por U e por L,
respectivamente). Eliminando as estratégias fracamente dominadas, obtemos (U,L) como solução (dizemos
que (U,L) é um equiĺıbrio formado por estratégias fracamente dominantes).
2.2.4 Estratégia Fracamente Dominada
Problema similar ao que ocorre com a noção de estratégias estritamente dominantes ocorre como o conceito
de estratégias fracamente dominantes: pode ser que não exista solução para o jogo em estratégias fracamente
dominantes, como o exemplo abaixo ilustra.
Exemplo. Considere o seguinte jogo:
L R
U (5, 1) (4, 0)
M (6, 0) (3, 1)
D (6, 4) (4, 4)
É fácil observar que não existe estratégia fracamente dominante para nenhum dos dois jogadores. Vamos
introduzir o seguinte conceito para analisar o jogo acima, um relaxamento da noção de estratégia estritamente
dominada.
Definição: Estratégia Fracamente Dominada. Uma estratégia s̄1 é fracamente dominada para o
jogador 1 quando existe uma outra estratégia ŝ1 ∈ S1 tal que:
u1(ŝ1, s2) ≥ u1(s̄1, s2), para todo s2 ∈ S2,
com desigualdade estrita para pelo menos um s2. Dizemos então que ŝ1 domina fracamente s̄1 (de modo
análogo podemos definir estratégia estritamente dominada para o jogador 2).
Vamos agora definir formalmente o processo de eliminação de estratégias fracamente dominadas (PEEFD):
PEEFD: Considere o jogo G = (Si, ui)
I
i=1. Seja S
0
i = Si, para cada jogador i. Para n ≥ 1, seja Sni o conjunto
das estratégias do jogador i resultante da n-ésima etapa de eliminação de estratégias fracamente dominadas,
ou seja, si ∈ Sni se si ∈ Sn−1i não é fracamente dominada em Sn−1i (no jogo dado por Gn−1 = (Sn−1i , ui)Ii=1).
Definição: Estratégia Iterativamente Fracamente Não-Dominada. A estratégia si do jogador i é
iterativamente fracamente não dominada em S (ou sobrevive ao PEEFD) se si ∈ W ni , para todo n ≥ 1.
7
Vamos aplicar o PEEFD ao jogo acima. Podemos proceder de dois modos:
1. Se eliminarmos primeiro U para o jogador 1, a estratégia L do jogador 2 se torna fracamente dominada
para o jogo resultante. Eliminando L, podemos eliminar M no jogo resultante, obtendo (D,R) (payoff
(4,4)) como solução.
2. Se eliminarmos primeiro M para o jogador 1, a estratégia R do jogador 2 se torna fracamente dominada
para o jogo resultante. Eliminando R, podemos eliminar U no jogo resultante, obtendo (D,L) (payoff
(6,4)) como solução.
O exemplo acima mostra que a ordem de eliminação das estratégias fracamente dominadas pode afetar
a solução obtida. Esta é uma caracteŕıstica ruim deste procedimento, pois a solução obtida pode mudar
conforme a ordem de eliminação das estratégias. Este problema não ocorre quando eliminamos estratégias
estritamente dominadas.
2.2.5 Estratégias Racionalizáveis
O PEEED e o PEEFD utilizam o conceito de conhecimento comum da racionalidade dos jogadores e da
estrutura do jogo. Porém, esses procedimentos não esgotam toda a força dessa hipotése. Usando essa
hipótese de conhecimento comum, podemos eliminar outras estratégias além das dominadas.
Definição: Melhor Resposta. Considere o jogo G = (Si, ui)
I
i=1. A estratégia ŝi é a melhor resposta do
jogador i à estratégia s−i dos seus rivais se:
ui(ŝi, s−i) ≥ ui(si, s−i), para todo si ∈ Si.
Portanto, a estratégia ŝi é a melhor resposta do jogador i para a estratégia s−i se ela for a escolha ótima de i
quando ele acredita que seus rivais escolherão a estratégia s−i. Um jogador não deve escolher uma estratégia
que nunca é uma melhor resposta, pois neste caso não existe forma de o jogador i justificar a escolha dessa
estratégia. Observe que estratégias estritamente dominadas nunca são a melhor resposta.
Podemos montar um procedimento de eliminação de estratégias que nunca são a melhor resposta, de modo
similar ao PEEED. Mais uma vez, estamos supondo a validade da hipótese de conhecimento comum da
racionalidade dos jogadores e da estrutura do jogo.
Definição: Estratégias Racionalizáveis. As estratégias em Si do jogador i que sobrevivem ao procedi-
mento de eliminação de estratégias que nunca são a melhor resposta são chamadas de racionalizáveis.
Uma estratégia racionalizável pode sempre ser “justificada”, ou seja, o jogador pode justificar a escolha
dessa estratégia com uma conjectura razoável sobre o comportamento dos outros jogadores (nenhum rival
escolherá uma estratégia não racionalizável).
É posśıvel mostrar que as seguintes afirmações são verdadeiras:
• A ordem de remoção das estratégias que nunca são a melhor resposta não altera o resultado obtido;
• Cada jogador tem pelo menos uma estratégia racionalizável, podendo ter mais de uma;
• O conjunto de estratégias racionalizáveis está contido no conjunto de estratégias que sobrevivem ao
PEEED;
• Para jogos com dois jogadores, o conjunto de estratégias racionalizáveis é igual ao conjunto de es-
tratégias que sobrevivem ao PEEED.
8
Porém, o conceito de estratégia racionalizável nem sempre fornece uma solução. Por exemplo, para a batalha
dos sexos, todas as estratégias são racionalizáveis, logo o conceito não diz nada sobre qual será a solução do
jogo.
Queremos tornar as predições sobre o resultado de um jogo mais precisas do que o que pode ser obtido
usando os conceitos vistos acima. A seguir veremos o conceito de equiĺıbrio de Nash (EN), que, satisfeitas
certas condições, sempre aponta pelo menos uma solução para o jogo. Esse é o mais importante conceito
em teoria dos jogos.
2.3 Equiĺıbrio de Nash
2.3.1 Equiĺıbrio de Nash em Estratégias Puras
O máximo que podemos obter usando a hipótese de conhecimento comum é o conceito de estratégias
racionalizáveis, que se assemelha ao conceito de estratégias que sobrevivem ao processo de eliminação de
estratégias dominadas. Para obtermos qualquer outro conceito mais robusto, temos que adicionar alguma
hipótese nova.
Definição: Equiĺıbrio de Nash em Estratégias Puras (Dois Jogadores). Um conjunto de estratégias
ŝ = (ŝ1, ŝ2) é um equiĺıbrio de Nash (EN) (em estratégias puras) para o jogo G = (Si, ui)i=1,2 se vale:
u1(ŝ1, ŝ2) ≥ u1(s1, ŝ2), para todo s1 ∈ S1, e
u2(ŝ1, ŝ2) ≥ u2(ŝ1, s2), para todo s2 ∈ S2.
Em um equiĺıbrio de Nash (EN), a estratégia de cada jogador é a melhor resposta para as estratégias que
são de fato escolhidas pelos outros jogadores. Portanto, um EN requer que os jogadores estejam certos sobre
suas conjecturas a respeito das estratégias escolhidas pelos seus rivais. Dizemos que os jogadores possuem
expectativas mutualmente corretas.
Resultados: Pode-se mostrar que todas as estratégias que fazem parte de um equiĺıbrio de Nash são
racionalizáveis. Mais ainda, todo equiĺıbrio formado por estratégias estritamente ou fracamente dominantes,
ou obtido pela eliminação de estratégias estritamenteou fracamente dominadas, é um equiĺıbrio de Nash.
Vamos discutir melhor esses resultados mais abaixo.
O conceito de EN traz uma predição mais precisa a respeito do resultado de um jogo do que o conceito de
racionabilidade. No problema de coordenação abaixo, todas as estratégias são racionalizáveis, mas apenas
(s1 = L, s2 = U) e (s1 = D, s2 = R) são EN em estratégias puras.
1↓ / 2 → L R
U 3, 3 0, 0
D 0, 0 1, 1
O jogo “Cara ou Coroa”, representado na matriz abaixo, não possui EN em estratégias puras. Logo, de
modo geral, não podemos garantir a existência de EN em estratégias puras.
1↓ / 2 → Cara Coroa
Cara −1, 1 1,−1
Coroa 1,−1 −1, 1
Intuitivamente, qualquer solução desse jogo envolve ambos os jogadores escolhendo suas estratégias de modo
impreviśıvel. Para formalizar essa ideia, vamos introduzir o conceito de estratégias mistas.
9
2.3.2 Estratégias Mistas
Definição: Estratégias Mistas. Seja Si o conjunto de estratégias puras do jogador i. Uma estratégia
mista do jogador i é uma distribuição de probabilidade sobre Si, ou seja, uma função σi : Si → [0, 1], que
associa uma probabilidade a cada estratégia pura do jogador i. Logo, temos que
σi(si) ≥ 0, ∀si e
∑
si∈Si
σi(si) = 1.
Notação: O simplex de Si, representado por ∆Si, é o conjunto das estratégias mistas do jogador i. Esse
conjunto também inclui as estratégias puras do jogador (estratégias mistas degeneradas).
Se os jogadores randomizam suas estratégias, então o resultado do jogo deixará de ser determińıstico. Neste
caso, calculamos o payoff dos jogadores usando utilidade esperada. Seja σ = (σ1, σ2) uma coleção de
estratégias mistas para os jogadores 1 e 2. A utilidade esperada do jogador 1 para a coleção de estratégias
mistas σ é calculada como:
UE1(σ) = Eσ(u1) =
∑
s1∈S1,s2∈S2
[σ1(s1)σ2(s2)]u1(s1, s2)
Podemos estender imediatamente os conceitos de: estratégias dominantes, estratégias dominadas, procedi-
mentos de eliminação e estratégias racionalizáveis, ao permitir que os jogadores possam escolher estratégias
mistas, além de estratégias puras.
2.3.3 Equiĺıbrio de Nash com Estratégias Mistas
Definição: Equiĺıbrio de Nash (dois jogadores). Um conjunto de estratégias σ̂ = (σ̂1, σ̂2) é um
equiĺıbrio de Nash para um certo jogo de dois jogadores se vale
u1(σ̂1, σ̂2) ≥ u1(σi, σ̂2), para todo σ1 ∈ ∆S1, e
u2(σ̂1, σ̂2) ≥ u2(σ̂i, σ2), para todo σ2 ∈ ∆S2
A definição acima permite que os jogadores randomizem entre as estratégias puras. Logo, eles podem não
somente escolher uma estratégia pura, mas também escolher uma estratégia que envolva várias estratégias
puras, cada uma escolhida com determinada probabilidade. Observe que no equiĺıbrio, cada jogador conhece
o modo em que os outros jogadores estão randomizando (as estratégias mistas escolhidas por seus rivais).
A definição diz que, para cada conjunto de estratégias dos jogadores candidato a equiĺıbrio, devemos verificar
se para cada jogador, a sua estratégia é de fato a melhor resposta para as estratégias dos outros jogadores que
fazem parte do conjunto de estratégias candidato a equiĺıbrio. Considerando estratégias mistas, existem um
número infinito de estratégias, o que torna este procedimento inviável. Como fazemos então para encontrar
todos os equiĺıbrios de Nash? O teorema abaixo fornece um algoritmo para encontrar equiĺıbrios de Nash
em estratégias mistas.
Teorema: Equivalência de Definições. As seguintes afirmativas são equivalentes:
1. (σ∗1, σ
∗
2) ∈ ∆(S1)×∆(S2) é um equiĺıbrio de Nash;
2. Para todo jogador i, ui(σ
∗
1, σ
∗
2) = ui(si, σ
∗
−i), para todo si jogado com probabilidade positiva; e
ui(σ
∗
1, σ
∗
2) ≥ ui(si, σ∗−i), para todo si que não é jogado com probabilidade positiva.
10
O teorema fornece um algoritmo para encontrar equiĺıbrios de Nash em estratégias mistas. Ele diz que
em um EN em estratégias mistas, duas estratégias puras de um jogador que podem ser escolhidas (que
possuem probabilidade positiva) devem necessariamente gerar o mesmo payoff para esse jogador, que será
igual ao payoff obtido no equiĺıbrio. Esse resultado é consequência de utilizarmos a utilidade esperada para
calcularmos o payoff de um conjunto de estratégias mistas. Caso existissem duas estratégias puras que o
jogador escolhesse com probabilidade positiva e em que uma delas gera um payoff maior do que o da outra,
o jogador não deveria atribuir probabilidade positiva à estratégia que lhe dá o payoff mais baixo, pois isso
reduziria o seu payoff de equiĺıbrio.
Ou seja, dadas as estratégias escolhidas em equiĺıbrio pelos outros jogadores, esse jogador é indiferente
entre qualquer estratégia pura que ele de fato possa vir a escolher (que tem probabilidade positiva), e estas
estratégias puras lhe dão um payoff igual ou maior do que qualquer outra estratégia que ele não escolhe.
Lembre-se que o que de fato determina as probabilidades de cada jogador é fazer (σ∗1, σ
∗
2) um equiĺıbrio.
Vamos usar o teorema para calcular o EN para o jogo “Cara ou Coroa”. Suponha que o jogador 1 decida
proceder do seguinte modo: com probabilidade α ele escolhe Ca e com probabilidade 1− α ele escolhe Co.
Similarmente, o jogador 2 decide proceder do seguinte modo: com probabilidade β ele escolhe Ca e com
probabilidade 1− β ele escolhe Co. Vamos representar na matriz abaixo essa situação.
1↓ / 2 → Cara (β) Coroa (1− β)
Cara (α) −1, 1 1,−1
Coroa (1− α) 1,−1 −1, 1
Pelo teorema de equivalência de definições acima, essas randomizações são um EN se:
u1(Ca, σ2) = u1(Co, σ2) e u2(σ1, Ca) = u2(σ1, Co),
onde σ1 e σ2 representam as estratégias mistas dos jogadores 1 e 2, respectivamente. Portanto:
u1(Ca, σ2) = u1(Co, σ2) ⇒ β = 0, 5
u2(σ1, Ca) = u2(σ1, Co) ⇒ α = 0, 5
Logo, σ1 = (1/2 ◦ Ca; 1/2 ◦ Co) e σ2 = (1/2 ◦ Ca; 1/2 ◦ Co) é um EN em estratégias mistas. Observe que:
u1(Ca, σ2) = u1(Co, σ2) = u1(σ1, σ2) = 0
u2(σ1, Ca) = u2(σ1, Co) = u2(σ1, σ2) = 0,
como esperado.
2.3.4 Teorema Nash e outros Resultados
Teorema de Existência de Equiĺıbrio de Nash. Considere o jogo G = (∆(Si), ui)
I
i=1, onde:
1. ∆(S1) é não-vazio, compacto e convexo para todo i; e
2. ui : ∆(S1)×∆(S2)→ R é cont́ınua e quasecôncava em ∆(Si).
Então sempre existe (pelo menos) um equiĺıbrio de Nash para esse jogo.
Corolário. Todo jogo finito na forma normal possui pelo menos um equiĺıbrio de Nash (considerando-se
estratégias mistas).
Vimos acima exemplos de equiĺıbrios com estratégias puramente mistas. O exemplo abaixo mostra que pode
existir um EN onde apenas um dos jogadores de fato randomize. Para que isso ocorra, é necessário que os
11
payoffs obtidos com as estratégias puras que fazem parte da randomização desse jogador sejam todos iguais,
já que o outro jogador não randomiza e escolhe uma estratégia pura. Além disso, cada estratégia pura do
jogador que de fato é randomizada forma um EN em estratégias puras junto com a estratégia pura escolhida
pelo outro jogador. O exemplo a seguir mostra esse ponto.
Exemplo: Considere o seguinte jogo com dois jogadores:
1↓ / 2 → L R
U 1, 1 0, 0
D 1, 0 0, 0
Esse jogo possui três EN em estratégias puras, (U,L), (D,L) e (D,R). Não existe equiĺıbrio em estratégias
estritamente mistas para os dois jogadores. Porém, (α ◦U, (1−α) ◦D;L) é um EN para todo α ∈ [0, 1], em
que o jogador 1 randomiza entre as estratégias U e D, escolhendo qualquer probabilidade. Isso ocorre porque
como U e D provêem o mesmo payoff para o jogador 1 quando 2 escolhe L, então qualquer randomização
entre essas duas estratégias será parte de um EN junto com a estratégia L de 2.
Um caso mais extremo e sem interesse seria o de um jogo em que os payoffs de cada jogador são todos iguais.
Nessa situação, “tudo” será EN, já que qualquer escolha de cada jogador gerará sempre o mesmo payoff. A
matriz abaixo ilustra esse caso.
1↓ / 2 → L R
U 1, 2 1, 2
D 1, 2 1, 2
A relação entre equiĺıbrio de Nash e os conceitos de equiĺıbrio com estratégiasdominantes é descrita pelos
seguintes resultados:
1. Se existir equiĺıbrio em estratégias estritamente dominantes, ele será único e será o único EN do jogo.
O mesmo vale para equiĺıbrios obtidos com o PEEED: se existir, será único e o único EN do jogo.
2. Se existir equiĺıbrio em estratégias fracamente dominantes, então ele será um EN. Neste caso, pode
ocorrer que exista outro EN, formado por estratégias fracamente dominadas. O exemplo abaixo mostra
esse caso.
3. Vimos em um exemplo acima, o PEEFD pode levar a diferentes resultados, dependendo da ordem de
eliminação das estratégias. De qualquer modo, se o PEEFD levar a algum resultado, qualquer que
seja esse resultado, ele será um EN.
Exemplo: Considere novamente o seguinte jogo:
1↓ / 2 → L R
U 1, 1 0, 0
D 0, 0 0, 0
Esse jogo possui dois EN, dados por (U,L) e (D,R). Não existe equiĺıbrio em estratégias estritamente
mistas. O EN (U,L) é também equiĺıbrio em estratégias fracamente dominantes (e pode ser obtido usando o
PEEFD). O EN (L,D) é um equiĺıbrio formado por estratégias fracamente dominadas e portanto não pode
ser encontrado usando o PEEFD.
O exemplo acima mostra que pode existir um equiĺıbrio formado por estratégias fracamente dominadas. O
resultado de um jogo ser um equiĺıbrio desse tipo é algo estranho, pois envolve cada jogador escolher uma
estratégia para a qual existe outra opção que dará sempre um payoff maior ou igual, independentemente
do que os outros jogadores façam. Existe um conceito de refinamento do EN para jogos na forma normal,
12
chamado refinamento da mão-trêmula (Selten, 1975; Myerson, 1978), que exclui a possibilidade desse tipo
de equiĺıbrio ocorrer.
O refinamento da mão-trêmula considera a possibilidade de que os jogadores possam cometer erros no
momento da escolha da sua estratégia a ser jogada. O EN então será chamado perfeito da mão-trêmula
caso satisfaça a condição imposta pelo refinamento. No exemplo acima, apenas o EN (U,L) é perfeito da
mão-trêmula.
Refinamentos do conceito de EN são direcionados para eliminar EN que por algum motivo não são consid-
erados razoáveis. Nesse caso, existirá algum ou alguns EN que satisfazem o refinamento e algum ou alguns
que não o satisfazem.
2.3.5 Discussão do Conceito de Equiĺıbrio de Nash
• Consequência da racionalidade quando o equiĺıbrio é único;
• Pontos focais (Schelling);
• Convenção social (um tipo de ponto focal);
• Forma de impor um acordo que seja “self-enforcing”.
2.3.6 QUESTÕES DA ANPEC
RESOLVER: Questão 7 - 2011; Questão 10 - 2010; Questão 11 - 2009; Questão 9 - 2008; Questão 13 -
2001; Questão 14 - 1999; Questão 13 - 1998.
13
3 Jogos na Forma Extensiva
3.1 Introdução
3.1.1 Forma Extensiva de um Jogo
Sabemos que para descrevermos um jogo são necessários três objetos:
• Os jogadores (inclusive natureza),
• A regra do jogo,
• O resultado (payoff) do jogo.
Um jogo na forma extensiva, definido a seguir, é a representação mais adequada para situações dinâmicas.
Definição Informal de Jogo na Forma Extensiva. Representamos um jogo finito na forma extensiva
em forma de árvore, onde em cada conjunto de decisão um jogador escolhe a ação que desenvolve o jogo.
Definição: Jogo de Informação Perfeita. Um jogo é chamado de informação perfeita se cada conjunto
de informação do jogo contém apenas um nó de decisão.
Logo, em um jogo de informação perfeita, cada jogador conhece todas as jogadas dos outros jogadores
escolhidas anteriormente. Se um jogo não é de informação perfeita, então existe pelo menos um ponto do
jogo em que algum jogador não sabe o que foi escolhido no momento anterior (um conjunto de informação que
contém mais de um nó). Nesse caso, unimos os nós que fazem parte de um mesmo conjunto de informação
por um retângulo pontilhado, como ilustra o jogo à direita na figura abaixo.
Jogo de Informação Perfeita
t1
�
�
�
�
��
E
@
@
@
@
@@
D
t2 2
�
�
�
�
��
r
A
A
A
A
AA
l
(
1
3
) (
0
0
)
�
�
�
�
��
l
A
A
A
A
AA
r
t
(
0
0
) (
3
1
)t t t t
Jogo de Informação Imperfeita
t1
�
�
�
�
��
E
@
@
@
@
@@
D
t 2
�
�
�
�
��
r
A
A
A
A
AA
l
(
1
3
) (
0
0
)
�
�
�
�
��
l
A
A
A
A
AA
r
t
(
0
0
) (
3
1
)t t t t
3.1.2 Estratégia de um Jogo na Forma Extensiva
A definição de estratégia para jogos simultâneos é simples e direta: a estratégia de cada participante é a
ação escolhida para o jogo todo. No caso de jogos sequênciais, a definição de estratégia é mais complicada.
Nesse caso, um determinado jogador pode ter vários pontos de escolha ao longo do jogo. Por exemplo, em
xadrez, as jogadas dos dois jogadores se alternam ao longo da partida.
Uma estratégia para jogos sequênciais é uma regra que determina a sua escolha de ação em TODOS os
conjuntos de informação do jogo. Logo, uma estratégia para o jogador i é então um plano CONTINGENTE
COMPLETO (uma regra de decisão completa) que especifica como o jogador i jogará em toda e qualquer
circunstância do jogo.
Dizer que uma estratégia é um plano contingente completo para o jogo significa dizer que uma estratégia
define ações para TODOS os conjuntos de informação do jogo, mesmo que esses conjuntos de informação
não sejam alcançados durante o jogo. Isso inclui definir ações para conjuntos de informações onde a própria
estratégia do jogador em questão torna essas ações irrelevantes.
14
3.1.3 Memória Perfeita
Um jogo é chamado de memória perfeita quando nenhum jogador esquece o que já sabia (inclusive ações que
já foram tomadas durante o desenrolar do jogo). O jogo ilustrado na figura abaixo não apresenta memória
perfeita. Nesse jogo, o jogador 1, na terceira rodada do jogo, após a sua escolha na primeira rodada e após
a escolha do jogador 2 na segunda rodada, não se lembra de sua escolha feita na primeira rodada do jogo.
t1�
���
���
�����
E
H
HHH
HHH
HHHHj
D
t2 �
�
�
�
��	
a
@
@
@
@
@@R
b
t
�
�
�
�
���
a
A
A
A
A
AAU
b
t1 �
�
�
�
���
A
A
A
A
AAU
l r l r l r l r
t
�
�
�
�
��	
@
@
@
@
@@Rt
�
�
�
�
���
A
A
A
A
AAU
t
�
�
�
�
���
A
A
A
A
AAU
3.1.4 Forma Extensiva e Forma Normal
Um jogo representado na forma normal pode ser representado na forma extensiva sem ambiguidades? O
contrário também é válido? Da forma extensiva para a forma normal sim, mas o contrário não é válido. A
mesma forma normal pode representar mais de um jogo na forma extensiva. A figura abaixo mostra dois
jogos diferentes que possuem a mesma representação na forma normal, que se resume a representação de
um jogo do tipo “Cara ou Coroa” discutido acima. Nos dois exemplos abaixo, o payoff na primeira linha é
do jogador 1 e na segunda linha, do jogador 2.
Jogador 1 escolhe primeiro
t1
�
�
�
�
��
Ca
@
@
@
@
@@
Co
t 2
�
�
�
�
��
Co
A
A
A
A
AA
Ca
(
−1
1
) (
1
−1
)
�
�
�
�
��
Ca
A
A
A
A
AA
Co
t
(
1
−1
) (
−1
1
)t t t t
Jogador 2 escolhe primeiro
t2
�
�
�
�
��
Ca
@
@
@
@
@@
Co
t 1
�
�
�
�
��
Co
A
A
A
A
AA
Ca
(
−1
1
) (
1
−1
)
�
�
�
�
��
Ca
A
A
A
A
AA
Co
t
(
1
−1
) (
−1
1
)t t t t
A forma normal é uma estrutura mais simples de se definir do que a forma extensiva. Ela envolve menos
objetos matemáticos do que a forma extensiva, porque a estratégia do jogador condensa uma quantidade
enorme de informação sobre o jogador. Podemos adaptar os conceitos definidos anteriormente para jogos
na forma estratégica (dominância, equiĺıbrio de Nash, etc) para jogos na forma extensiva, aplicando esses
conceitos para a representação na forma normal do jogo na forma extensiva.
15
Von-Newman e Morgenstern argumentaram que de um modo geral, só é necessário sabermos a forma normal
para analisarmos um jogo. Se os jogadores são inteligentes, cada jogador pode planejar toda a sua regra de
decisões para o jogo antes dele começar. Assim, ele monta a sua estratégia para o jogo.
Essa “suficiência” da forma normal de um jogo é uma das ideias mais importantes dateoria de jogos.
Para jogos simultâneos, isso é claro. Porém, para jogos dinâmicos, existe uma perda de informação quando
representamos o jogo na forma estratégica. No exemplo acima, vemos que a forma normal equivalente dos
dois jogos sequênciais é a mesma - logo a informação perdida na representação do jogo na forma normal é
apenas quem escolhe primeiro o lado da moeda. Essa perda de informação é irrelevante para a análise dos
dois jogos e não influencia os resultados obtidos. Porém, essa perda de informação será sempre irrelevante
ou existem casos em que ela é relevante? Essa é uma questão em aberto na teoria.
3.1.5 Estratégias Comportamentais
Existem dois modos de se definir randomização por parte dos jogadores em um jogo na forma extensiva:
1. Randomizar a estratégia usada. Esse modo de randomização é o mesmo usado em jogos estratégicos.
2. Randomizar em cada momento de jogar.
No primeiro modo, obtemos o conceito de estratégia mista visto anteriormente. No segundo modo, obtemos
o conceito de estratégia comportamental
O seguinte resultado garante a equivalência das duas formas de randomização, para jogos de memória
perfeita. Caso o jogo não seja de memória perfeita, então pode existir um estratégia comportamental para
a qual não exista estratégia mista equivalente, no sentido de levar a mesma distribuição sobre os payoffs.
Teorema de Kuhn I. Para jogos na forma extensiva de memória perfeita, estratégia mista e estratégia
comportamental são modos de randomização equivalentes.
Logo, para toda estratégia comportamental do jogador i podemos encontrar uma estratégia mista de i tal que
resulta na mesma distribuição sobre payoffs, quaisquer que sejam as estratégias, mistas ou comportamentais,
usadas pelos outros jogadores, e vice-versa. Nesse caso, o tipo de estratégia, mista ou comportamental, usada,
é indiferente para análise do jogo.
Porém, vários tipos de jogos possuem um dinâmica de ações escolhidas em tempos diferentes. Em alguns
desses jogos, representá-los na forma normal e dáı encontrarmos os EN pode não ser adequado. Quando
derivamos a representção na forma normal de um jogo sequêncial, para encontrarmos os EN do jogo, alguns
equiĺıbrios podem não ser cŕıveis, ou seja, baseados em ameaças de um dos jogadores que não será cumprida.
Portanto, o principal problema na resolução de jogos dinâmicos por meio de encontrar os EN da sua repre-
sentação na forma normal diz respeito à credibilidade de uma estratégia que faz parte de um EN do jogo na
forma normal.
Exemplo: Monopolista e Firma Entrante. Considere um mercado monopolista. O monopolista
mantém o mercado ameaçando firmas entrantes de uma guerra de preços. Desse modo, o monopólio mantém
seu lucro. Porém, se alguma firma de fato entrar, a melhor estratégia para o monopolista é formar um cartel
e dividir o lucro de monopólio, já que a guerra de preços traria prejúızos não somente para a firma entrante,
mas também para o incumbente. Essa situação estratégica é representada pelo seguinte jogo na forma
extensiva.
16
tEntrante
�
�
�
�
��	
Não Entra
@
@
@
@
@@R
Entra
(
0
2
) t Monopolista
(
−1
−1
) (
1
1
)
�
�
�
�
��	
Briga
@
@
@
@
@@R
Acomoda
A forma normal equivalente do jogo acima é:
Entrante/Monopolista Briga, se E entrou Acomoda, se E entrou
Não entra 0,2 0,2
Entra -1,-1 1,1
Existem dois EN em estratégias puras para o jogo:
1. firma entrante (E) entrar, monopolista (M) acomoda, se E entrou, e
2. firma entrante não entra, monopolista briga se E entrar.
O segundo EN é baseado em uma ameaça vazia, não-cŕıvel : M faz uma ameaça, que se for levada a sério,
não precisa ser cumprida, pois nesse caso E escolhe não entrar. Porém, uma vez que E entrar, o melhor
para M é se acomodar. O refinamento de perfeição em subjogos, que veremos a seguir, tenta eliminar EN
baseados em ameaças não cŕıveis.
3.2 Equiĺıbrio de Nash Perfeito em Subjogos (ENPS)
3.2.1 Jogos de Informação Perfeita
Vamos primeiro analisar jogos de informação perfeita, onde os jogadores estão perfeitamente informados de
todas as ações previamente escolhidas quando for o seu momento de jogar. Jogos como damas, xadrez, etc
são jogos de informação perfeita.
O objetivo é desenvolver um conceito de equiĺıbrio que elimine equiĺıbrios baseados em estratégias não-
cŕıveis, como no exemplo acima, onde o ideal seria acharmos (Entra,Ac se E entrou) como único equiĺıbrio.
Portanto, queremos refinar o conceito de EN - queremos que as soluções do jogo ainda sejam EN, mas
queremos eliminar os EN baseados em estratégias que envolvem ameaças não-cŕıveis. O seguinte conceito é
fundamental para obtermos esse conceito de equiĺıbrio.
Prinćıpio da Racionalidade Sequencial (PRS): A estratégia de um jogador qualquer deve especificar
ações que são ótimas em cada ponto do jogo.
Esse prinćıpio é implementado em um jogo de informação perfeita por um Algoritmo de Indução Reversa
(“backward induction algorithm”):
1. Comece pelos nós de decisão finais da árvore (“nós penúltimos” - nós cujos sucessores são todos nós
terminais);
17
2. Determine a escolha ótima dos jogadores que jogam nesses nós (problema de maximização individual,
sem interação estratégica);
3. Redesenhe a árvore, substituindo os nós de decisão final por um nó terminal, com payoff definido pela
escolha ótima no passo 2);
4. Repita passos 1), 2) e 3) para esse jogo reduzido, até chegar ao fim.
A solução de indução reversa para jogos com informação perfeita se resume a que todos os jogadores façam
escolhas que maximizem o seu payoff sempre que for a sua vez de jogar. Na prática, o jogo é resolvido do
fim para o começo. No exemplo anterior, o único EN que satisfaz o prinćıpio da racionalidade sequêncial é
(entrar,acomodar se E entrou).
Definição: Estratégias de Indução Reversa. O conjunto de estratégias puras s = (s1, s2, . . . , sI) é uma
estratégia de indução reversa para o jogo na forma extensiva Γ se é obtido de acordo com o algoritmo de
indução reversa. O seguinte teorema garante que o conjunto de estratégias obtido resolvendo o jogo por
indução reversa é um EN.
Teorema de Kuhn II. Se s = (s1, s2, . . . , sI) é uma estratégia de indução reversa do jogo na forma
extensiva Γ finito e de informação perfeita, então s é um EN desse jogo.
Corolário: Existência de Equiĺıbrio. Todo jogo na forma extensiva finito de informação perfeita Γ tem
um EN em estratégias puras, que pode ser encontrado usando indução reversa. Se os payoffs de cada jogador
são diferentes nos nós terminais, para todos jogadores, então existe um único EN que pode ser encontrado
usando indução reversa.
Corolário. Todo jogo finito de informação perfeita tem (pelo menos) um EN em estratégias puras.
Exemplo: Monopolista e Firma Entrante (continuação). No jogo Monopolista/Entrante, existem
dois EN em estratégias puras, mas apenas um EN obtido usando o algoritmo de indução reversa. O algoritmo
elimina exatamente o EN baseado em uma ameaça não-cŕıvel, o monopolista abrir uma guerra de preços
caso o entrante de fato entre. Esta ameaça não é cŕıvel pois uma vez que o entrante entrou no mercado, se
o monopolista fizer uma guerra de preços, ele próprio se prejudicará sem nenhum ganho.
3.3 Jogos de Informação Imperfeita
3.3.1 Subjogos
O algoritmo de indução reversa acima só se aplica para jogos de informação perfeita. Porém a ideia de
racionalidade sequêncial pode ser usada também para jogos de informação incompleta, por meio de um
algoritmo similar de indução reversa.
A ideia central é definir subjogos do jogo principal (Selten, 1965, 1975). Cada subjogo pode ser visto como
um jogo por si só. Racionalidade sequêncial exige que um EN seja EN para cada subjogo.
Definição: Subjogo. Um subjogo de um jogo Γ na forma extensiva é um subconjunto do jogo tal que:
(i) Se inicia emum conjunto de informação que contém apenas um único nó de decisão, e contém todos
os nós sucessores desse nó inicial;
(ii) Se o nó de decisão y pertence ao subjogo, então todo nó z que pertence ao conjunto de informação de
y também pertence ao subjogo.
O jogo abaixo possui um único subjogo, o próprio jogo. Logo, podemos garantir que todo jogo possui pelo
menos um subjogo.
18
u1
�
�
�
�
�
�
E
@
@
@
@
@
@
D
u 2
�
�
�
�
�
�
r
A
A
A
A
A
A
l
(
1
3
) (
0
0
)
�
�
�
�
�
�
l
A
A
A
A
A
A
r
u
(
0
0
) (
3
1
)u u u u
3.3.2 Equiĺıbrio de Nash Perfeito em Subjogos
Definição: ENPS em Estratégias Puras. O conjunto de estratégias s = (s1, s2, . . . , sI) do jogo Γ é um
equiĺıbrio de Nash perfeito em subjogos (ENPS) se s = (s1, s2, . . . , sI) induz um equiĺıbrio de Nash em todo
subjogo de Γ.
ENPS é um refinamento de EN: todo ENPS é um EN, já que o próprio jogo é um subjogo seu. O contrário
não é válido: existem EN que não são perfeitos em subjogos.
Teorema. Para todo jogo na forma extensiva finito de informação perfeita, o conjunto de estratégias de
indução reversa é igual ao conjunto de ENPS em estratégias puras.
Logo, em jogos de informação perfeita, o conjunto de ENPS coincide com o conjunto de EN obtido usando
o algoritmo de indução reversa visto acima. Porém, considerando jogos de informação imperfeita, nem todo
jogo possui um ENPS em estratégias puras. O teorema a seguir garante a existência de ENPS para jogos
de memória perfeita.
Teorema: Existência de ENPS (Selten). Todo jogo na forma extensiva finito com memória perfeita
possui um ENPS.
A hipótese de memória perfeita é necessária. Existem exemplos de jogos que não são de memória perfeita,
que não possuem ENPS.
O seguinte algoritmo geral de indução reversa para jogos na forma extensiva, sejam de informação completa
ou não, é válido para encontrar os ENPS:
1. Comece pelo término da árvore, ache os EN para todos os subjogos finais (subjogos que não possuem
nenhum subjogo estrito);
2. Substitua cada subjogo pelo payoff de um de seus EN;
3. Repita os passos 1) e 2) para o jogo reduzido, continue até não restar nenhum subjogo;
4. Repita 1), 2) e 3) para todos os EN encontrados (no caso de algum subjogo ter mais de um EN).
Para jogos de informação perfeita, esse algoritmo é igual ao algoritmo anterior.
3.3.3 QUESTÕES DA ANPEC
RESOLVER: Questão 11 - 2011; Questão 11 - 2007; Questão 10 - 2006; Questão 11 - 2006; Questão 11
- 2006; Questão 11 - 2005; Questão 12 - 2005; Questão 11 - 2004; Questão 12 - 2003; Questão 13 - 2002;
Questão 14 - 2001; Questão 15 - 2000.
19
3.4 Jogos Repetidos
Em um jogo do tipo dilema dos prisioneiros, seria posśıvel obter cooperação se repet́ıssemos o jogo diversas
vezes? Com a repetição, o número de estratégias de cada jogador aumenta. Nesse caso, é posśıvel criar
estratégias onde o jogador pune o outro caso ele não coopere.
Exemplo: Dilema dos Prisioneiros.
1↓ / 2 → Confessar Não Confessar
Confessar −3,−3 −1,−5
Não Confessar −5,−1 −2,−2
Suponha que o jogador 1 adota a seguinte estratégia: na primeira interação ele joga NC (cooperar). Nos
peŕıodos seguintes, se o outro jogador escolheu NC (cooperar) no peŕıodo anterior, ele coopera hoje. Caso
contrário, o jogador 1 escolhe C (não cooperar). Essa estratégia pode levar a algum tipo de cooperação?
Mais especificamente, existe algum equiĺıbrio tal que os jogadores venham a adotar estratégias cooperativas?
Para jogos finitos, a resposta é negativa. Para jogos infinitos ou sem data certa para terminarem, a resposta
é positiva.
3.4.1 Repetição Finita
O teorema abaixo mostra que se o dilema dos prisioneiros é repetido um número fixo (finito) de vezes, o
único equiĺıbrio de Nash perfeito em subjogos será formado pelo EN do jogo em cada peŕıodo sendo jogado.
Logo, não é posśıvel obter o resultado eficiente com a repetição finita do jogo.
Teorema Seja Γ dado por sucessivos Gt = (M ti , u
t
i(·))II=1 (ou seja, um jogo onde em cada peŕıodo t se
joga um jogo simultâneo), t = 1, 2, . . . , T < +∞. Suponha que os jogadores observam as estratégias puras
jogadas em cada jogo, imediatamente após a conlusão do jogo, e que o payoff de cada jogador é dado pela
soma dos payoffs obtidos em todos os Gt. Se existe um único EN st para cada Gt, então existe um único
ENPS para Γ, que consiste em cada jogador jogando sti em cada jogo G
t, independente do que foi feito antes.
O teorema acima tem uma consequência forte, eliminar qualquer dependência histórica nas estratégias atuais.
Ou seja, tudo o que ocorreu antes é irrelevante para decidir o que fazer hoje. Para jogos que satisfaçam as
condições da proposição, um ENPS não depende da história ocorrida no jogo em nenhum momento.
Por exemplo, o teorema acima tem como consequência o fato que vimos de que o dilema dos prisioneiros
jogado repetidamente, por um peŕıodo determinado, continua sempre tendo a mesma solução não cooperativa
entre os jogadores em cada rodada do jogo. Esse resultado é consequência da racionalidade sequêncial. Por
indução reversa, na última rodada, é melhor não cooperar. Resolvendo de traz para diante, obtemos não-
cooperação para todas as rodadas do jogo.
Intuitivamente, esse resultado é consequência do jogo ter uma data de término conhecida pelos jogadores.
Resolvendo o jogo por indução reversa, cada jogador percebe que o seu rival irá descumprir o acordo
de cooperação na última vez que interagirem. Eles se adiantam a isso e não cooperam na última rodada.
Sabendo disso, os jogadores também não irão cooperar na penúltima rodada do jogo. Usando esse argumento,
obtemos que os jogadores não cooperam em nenhuma rodada do jogo. O teorema, consequência da definição
de ENPS, leva a resultados considerados pouco razoáveis, como mostra o exemplo abaixo.
Exemplo: Jogo da Centópeia. Considere o seguinte jogo.
sI C
P(
1
1
)
sII C
P(
0
3
)
I C
P
s
(
2
2
)
sII C
P(
1
4
)
. . . . . . . . . . . . ...s sII C
P(
97
100
)(
99
99
)
s sI C
P
II C
P(
98
101
)
(100 100)
20
3.4.2 Repetição Infinita
Porém, se o jogo é repetido infinitamente (ou se ele não tem uma data fixa para terminar), pode-se mostrar
que o resultado eficiente em cada rodada do jogo pode ser obtido como equiĺıbrio, dependendo do quanto
os jogadores descontem o futuro.
As estratégias que levam a esse tipo de equiĺıbrio são chamadas estratégias gatilho (trigger ou tit-for-tat ou
grim strategies, Nash-reversion strategies). Um exemplo é a estratégia “olho-por-olho”, onde a estratégia
de hoje do jogador é igual à estratégia usada pelo seu adversário ontem.
Considere novamente a seguinte estratégia para o i, i = 1, 2: na primeira interação ele joga NC (cooperar).
Nos peŕıodos seguintes, se o outro jogador escolheu NC (cooperar) no peŕıodo anterior, ele coopera hoje.
Caso contrário, o jogador i escolhe C (não cooperar). Suponha que a taxa de desconto intertemporal é
0 < δ < 1.
Temos que o jogador 2 cooperará se:
∞∑
t=0
−2δt ≥ −1 +
∞∑
t=1
−3δt ⇒ −2
1− δ
≥ −1 + −3δ
1− δ
Logo, se
δ ≥ 1
2
= 50%,
então o resultado cooperativo ((NC,NC) todo peŕıodo) é obtido como equiĺıbrio (é um equiĺıbrio de Nash
perfeito em subjogos).
Portanto, dependendo da taxa de desconto intertemporal e dos payoffs obtidos desviando do equiĺıbrio
cooperativo e seguindo o equiĺıbrio cooperativo, podem existir equiĺıbrios em que os jogadores adotem
estratégias que envolvem cooperação. Esse resultado é conhecido como “Folk Theorem.”
Observação: Usualmente, a taxa de desconto intertemporal δ é determinada pela taxa de juros r, do
seguinte modo:
δ =
1
1 + r
Logo, se encontrarmos a taxa de desconto intertemporal, podemos também encontrar a taxa de juros asso-
ciada. No exemplo acima, obtemos que:
r ≥ 1
3.4.3 QUESTÕES DA ANPEC
RESOLVER: Questão 12 - 2009; Questão 15 - 2008; Questão 11 - 2003; Questão 11 - 2002; Questão14 -
2000.
Leitura sugerida:
• Varian, caṕıtulos 28 (A Teoria dos Jogos) e 29 (Aplicações da Teoria dos Jogos).
21