Elementos da Teoria dos Jogos e Aplicações Aula 5 Maio, 2005

Elementos da Teoria dos Jogos e Aplicações

Aula 5

Maio, 2005

Revisão

Principais conceitos e definições

Revisão Jogo estático

“Common knowledge” Eliminação de estratégias estritamente

dominadas Equilíbrio de Nash Estratégias mistas

Jogo Dinâmico Estratégia Subjogo Equilíbrio de Nash Perfeito em Subjogos

Jogos Repetidos

Horizonte finito e infinitoReputação e credibilidade

Punições

Dilema dos Prisioneiros Considere a seguinte versão do dilema

dos prisioneiros.

Pergunta: há meios de implementar cooperação em relações duradouras?

2

1

C NC

C 1,1 5,0

NC 0,5 4,4

Horizonte Finito

Dilema dos prisioneiros em 2 períodos Taxa de desconto: =1.

Expansão da árvore é exponencial: 1o período: 4 resultados possíveis 2o período: 16 resultados possíveis

Estratégia: deve estabelecer o que será feito por cada jogador, em cada história possível do jogo.

Indução retroativa

Menor subjogo: é o próprio jogo constituinte; independente da história pregressa.

EN do menor subjogo: (C,C).

1o período Considerando que no segundo período

será jogado (C,C), o primeiro período é representado por:

2

1

C NC

C 2,2 6,1

NC 1,6 5,5

Equilíbrio de Nash Perfeito em Subjogos

Jogador i: (C; C,C,C,C)

O ENPS é único.

Não há como implementar cooperação.

Caso houvesse N períodos, o resultado seria análogo.

Proposição

Caso o jogo constituinte tenha um único equilíbrio de Nash, o jogo repetido N vezes também terá um único equilíbrio de Nash perfeito em subjogos.

Esse ENPS corresponde à repetição dos equilíbrios do jogo constituinte.

Cooperação em jogos com horizonte finito

Suponha que, por alguma razão, haja uma nova possibilidade no jogo constituinte, representada por X.

2

1

C NC X

C 1,1 5,0 0,0

NC 0,5 4,4 0,0

X 0,0 0,0 3,3

Sustentando cooperação

Considere o seguinte par de estratégias: Primeiro período: NC Segundo período: X caso tenha ocorrido

(NC,NC); C caso contrário.

Objetivo: ao invés de caracterizar o conjunto de todos os equilíbrios, iremos mostrar que as estratégias acima constituem um ENPS.

Indução retroativa

2o período:

As estratégias determinam que ambos escolham C ou ambos escolham X.

Como (C,C) e (X,X) são EN do jogo constituinte, não há problema.

1o período

2

1

C NC X

C 2,2 6,1 1,1

NC 1,6 7,7 1,1

X 1,1 1,1 4,4

Características

Só é possível implementar cooperação em jogos repetidos com horizonte finito se o jogo constituinte apresentar equilíbrios múltiplos.

apenas as ameaças críveis de punições futuras podem afetar o comportamento corrente.

Caso haja um único EN no jogo constituinte, será jogado em cada repetição.

Horizonte Infinito

Estrutura Jogo constituinte G.

Infinitas repetições – se aplica para relações duradouras que não possuem prazo de validade.

Taxa de desconto: 0<<1. Impaciência. Probabilidade do jogo se repetir por mais 1

período.

Dilema dos prisioneiros

Estratégia do gatilho: Joga NC no 1o período; Joga NC se observou (NC,NC) em todos os

períodos anteriores e C caso contrário.

2

1

C NC

C 1,1 5,0

NC 0,5 4,4

Teste A estratégia do gatilho constitui um

equilíbrio de Nash perfeito em subjogos?

2 tipos relevantes de subjogos: subjogos de “cooperação”; subjogos de “não-cooperação”.

Naqueles subjogos de não-cooperação, a estratégia prevê um equilíbrio de Nash do jogo constituinte.

Subjogos de cooperação

Nos subjogos de cooperação, as estratégias constituem equilíbrio se:

4+4+42+... ≥ 5++2...

4/(1-) ≥ 5+/(1-)

≥ 1/4.

Implementando o que é possível O que acontece se <1/4 ?

Considere uma versão modificada do dilema dos prisioneiros, em que:

2

1

C NC

C 1,1 5,0

NC 0,5 M,M

Continuação Estratégia do gatilho:

Joga NC no 1o período; Joga NC se observou (NC,NC) em todos os períodos

anteriores e C caso contrário. Nos subjogos de cooperação, as estratégias

constituem equilíbrio se:M+M+M2+... ≥ 5++2...

M/(1-) ≥ 5+/(1-)

M ≥ 5-4.

Lições

Como os jogadores descontam muito o futuro, torna-se necessária uma compensação maior para que a cooperação ocorra.

No jogo analisado, existem apenas duas estratégias. Não há possibilidade de implementar uma cooperação que envolva menos incentivos ao desvio.

Implementando cooperação com punições mais brandas A estratégia do gatilho envolve punições

muito agressivas que, diante de um desvio, penaliza os jogadores indefinidamente.

Considere o seguinte par de estratégias (“stick and carrot”): Joga NC no 1o período; Joga NC se observou (NC,NC) ou (C,C) no período

anterior; Joga C caso contrário.

Estratégia

Diante de um desvio em k+1, a punição tem duração de apenas 1 período.

t ação de 1 ação de 2

k NC NC

k+1 NC C

k+2 C C

k+3 NC NC

Equilíbrio de Nash Perfeito em Subjogos Nos subjogos de punição, a análise é a mesma

da estratégia do gatilho.

Nos subjogos de cooperação, as estratégias constituem equilíbrio se:

4+4+42+... ≥ 5++42...

4+4 ≥ 5+

≥ 1/3.

Lição

Punições mais brandas requerem uma taxa de desconto mínima maior para a implementação da cooperação.

Definições Ganho médio: 1, 2, 3,...

(1-) t t-1t.

Ganhos factíveis:

(0,5)

(4,4)

(1,1) (5,0)

Teorema Folk Friedman, 1971

Seja G um jogo estratégico com informação completa e (e1,...,eN) os ganhos de um equilíbrio de Nash de G. Seja (x1,...,xN) um vetor de ganhos factíveis de G.

Se xi > ei para todo i e for suficientemente próximo de 1, existe um ENPS do jogo repetido com horizonte infinito que atinge (x1,...,xN) como ganho médio.

Teorema Folk

(0,5)

(4,4)

(1,1) (5,0)

Ganhos atingíveis em ENPS