JOGOS DINÂMICOS

8/17/2019 JOGOS DINÂMICOS

1/51

JOGOS DINÂMICOS COM INFORMAÇÃO PERFEITA

Jogos dinâmicos são aqueles em que os movimentos (ou tomadas de decisão) dos

jogadores se sucedem em determinada ordem. Exemplo: no jogo de xadrez o jogador

das peças brancas inicia a partida com um movimento e é sucedido por um movimento

do jogador de peças pretas, em seguida o jogo continua com um novo movimento do

jogador de peças brancas e assim por diante até que se estabeleça uma vitória ou um

empate.

Em jogos dinâmicos estratégias e movimentos não necessariamente se confundirão

como nos jogos estáticos. Assim, seguiremos a convenção de escrever uma estratégia

em itálico com a primeira letra em maiúsculo e uma tomada de decisão em itálico com

a primeira letra em minúsculo.

A apresentação de um jogo dinâmico ocorre pelo uso de Árvores de Jogo. Uma árvore

de jogo é uma representação composta de nós e ramos. Um nó de decisão é um ponto


2/51

de decisão de um jogador e, assim, cada nó de decisão pertence a um único jogador.

O ramo é a ligação entre dois nós.

Um nó que não é terminal é um nó de decisão.

Jogador A

Jogador B•

movimento

de A

movimento de B

nó terminal

nó inicial ou

nó raiz

nóramo

ramo


3/51

Uma árvore de jogos possui uma orientação que é definida pelas setas dos ramos.

Nesse caso a orientação é da esquerda para a direita. Também são comuns

orientações de cima para baixo, mas nada impede uma orientação da esquerda para a

direita ou de baixo para cima. O importante é manter a clareza na apresentação.

Um caminho é uma sucessão possível de nós e ramos.

Regras para a construção de árvores de jogos

Regra 1: todo nó é precedido por, no máximo, outro nó.

O único nó que não é precedido por outro é o nó inicial ou raiz.

Regra 2: nenhum caminho em uma árvore liga um nó de decisão a si mesmo.

Regra 3: todo nó é sucessor de um único nó inicial .Regra 4: toda árvore de jogo tem exatamente um nó inicial (o nó raiz).


4/51

Todo jogo pode ser representado na forma de uma árvore de jogo, mesmo um jogo

simultâneo. Isso demanda uma definição da informação em um jogo.

Um jogador possui informação perfeita se ele sempre souber onde ele se localiza na

árvore de jogo quando for fazer o seu movimento. Exemplos: um jogador de xadrez

possui o histórico completo das movimentações e da ordem destas, portanto, possui

informação perfeita; em um jogo de duopólio de Cournot cada jogador faz o seu

movimento sem saber do movimento do outro, portanto, cada empresa possui

informação imperfeita.

Um jogo será de informação perfeita sempre que todos os jogadores possuírem

informação perfeita. Um jogo será de informação imperfeita se ao menos um dos jogadores possuir informação imperfeita.


5/51

Empresa A

Empresa B

Empresa B

•

•

•

•

coopera

coopera

coopera

não coopera

não coopera

não coopera


6/51

Empresa A

Empresa B

Empresa B

•

•

•

•

coopera

coopera

cooperanão coopera

não coopera

não coopera


7/51

Exemplo: A Microsoft desenvolveu um jogo e deve escolher o tipo de campanha

publicitária que irá utilizar. Se escolher Elegante irá contratar uma grande empresa de

publicidade e realizará muitas vendas no primeiro ano e poucas no segundo, porque o

mercado se satura em um prazo de dois anos. Se escolher Simples o lançamento será

apenas através dos meios tradicionais da empresa (site da empresa, anúncio oficial à

imprensa especializada e redes sociais), as vendas no primeiro ano serão menores,

mas o efeito boca a boca levará a grandes vendas no segundo ano de modo que o

mercado se satura também no segundo ano. Os resultados são apresentados na

tabela abaixo.


8/51

Lucros da Microsoft se não há concorrência

Elegante Simples

Lucro bruto no ano 1 $900000 $200000


Lucro bruto total $1000000 $1000000

Custo da propaganda - $570000 - $200000

Lucro líquido total $430000 $800000

Caso não haja concorrência o comportamento maximizador levará a Microsoft a optar

pela estratégia Simples. Porém, existe uma empresa, a Micorcorp, capaz de fazer um

clone legal (uma versão similar do jogo, mas legal, pois possui código fonte próprio) um

ano após o lançamento do jogo pela Microsoft a um custo de $300000. O clone é


9/51

considerado substituto perfeito pelos consumidores de modo que não é possível uma

diferenciação no mercado.

Lucros da Microsoft se a Microcorp oferta o clone no segundo ano

Elegante Simples



Lucro bruto total $950000 $600000Custo da propaganda - $570000 - $200000

Lucro líquido total $380000 $400000


10/51

Lucros da Microcorp se a Microcorp oferta o clone no segundo ano

Microsoft escolhe Elegante Microsoft escolhe Simples



Lucro bruto total $50000 $400000

Custo da propaganda - $300000 - $ 300000

Lucro líquido total - $250000 $100000


11/51

As estratégias da Microsoft são Elegante e Simples. As estratégias da Microcorp são

(entrar, entrar ), (entrar, ficar fora), (ficar fora, entrar ) e (ficar fora, ficar fora).

Microsoft

Microcorp

Microcorp

•

•

•

•

elegante

entrar

entrar simples

ficar

fora

ficar

fora

($380000, - $250000)

($430000, $0)

($400000, $100000)

($800000, $0)


12/51

Lembre-se que uma estratégia é um conjunto detalhado (completo) de planos para um

jogador. Como a Microsoft faz um único e inicial movimento, o seu movimento se

confunde com a estratégia. Já a Microcorp deve incorporar os dois possíveis

movimentos da Microsoft em suas estratégias. Por exemplo, a estratégia (entrar, ficar

fora) da Microcorp deve ser entendida da seguinte maneira: escolher o movimento

entrar se a Microsoft escolheu Elegante e escolher o movimento ficar fora se a

Microsoft escolheu Simples. Os possíveis perfis de estratégias desse jogo são:

{Elegante, (entrar, entrar )}

{Elegante, (entrar, ficar fora)}

{Elegante, (ficar fora, entrar )}

{Elegante, (ficar fora, ficar fora)}

{Simples, (entrar, entrar )}


13/51

{Simples, (entrar, ficar fora)}

{Simples, (ficar fora, entrar )}

{Simples, (ficar fora, ficar fora)}

Uma estratégia especifica o movimento em cada um dos nós de decisão do jogador.

Como Microsoft possui apenas um nó de decisão a sua estratégia possui apenas uma

tomada de decisão. Já a Microcorp que possui dois nós tem que especificar a sua

estratégia com dois movimentos.


14/51


15/51

Se considerarmos a dinâmica do jogo:

Macrosoft

Elegante Simples

Microcorp

(entrar, entrar ) -$250000, $380000 *$100000, $400000*

(entrar, ficar fora) - $250000, $380000 $0, $800000*

(ficar fora, entrar ) *$0, $430000* *$100000, $400000

(ficar fora, ficar fora) *$0, $430000 $0, $800000*

nesse caso temos dois equilíbrios de Nash, dois possíveis resultados que são

racionais. Há alguma forma de determinar qual será o escolhido?

Não há na teoria dos jogos nenhum conceito de solução entre dois ou mais equilíbriosde Nash com a mesma aceitação virtualmente universal que o equilíbrio de Nash


16/51

possui. O equilíbrio de Nash evidencia uma situação que é racional segundo a teoria

da tomada de decisão e a racionalidade é um fenômeno que pode ocorrer em mais de

uma situação. Situações onde não ocorre racionalidade podem ser oriundas não

apenas de dificuldade de processamento e computação dos dados (em problemas

extensos ou complicados) e de violações dos pressupostos de racionalidade (como

ações instintivas, por exemplo), um resultado não racional pode ocorrer por azar e isso

nenhuma racionalidade pode evitar. Em jogos dinâmicos como o apresentado, porém,

existem alguns procedimentos para tentar simplificar o jogo e evidenciar um equilíbrio

em particular. Tomemos o caso da indução retroativa ou indução reversa.

Siga o seguinte algoritmo:

1) Comece pelos nós terminais do jogo e trace o caminho de cada um até o seu nó

predecessor imediato, que será um nó de decisão de algum jogador. Esses nós de

decisão podem ser triviais não básicos, triviais básicos ou complexos. Um nó


17/51

básico é aquele em que cada um dos ramos leva a exatamente um nó terminal.

Um nó básico com apenas um ramo é trivial e o nó que não é básico é complexo.

Se você alcançar um nó de decisão trivial, continue a subir a árvore até alcançar

um nó de decisão complexo ou um básico não trivial ou não poder mais seguir

adiante.

2) Determine o movimento ótimo em cada nó de decisão básico alcançado na etapa

1 comparando as recompensas que o jogador obtém em cada nó terminal

alcançado a partir desse nó de decisão. Observe que cada caminho entre um nó

de decisão básico A e um nó terminal B começa em um único ramo de A. O ramo

que leva à recompensa mais alta para o jogador é o movimento ótimo a fazer

naquele nó.

3) Apague todos os ramos não ótimos que se originaram de cada um dos nós dedecisão básicos que você examinou na etapa 2. Cada um deles torna-se trivial.


18/51

4) Agora você tem uma árvore de jogo mais simples do que a original. Se na etapa 1

você chegou à raiz da árvore, então o seu trabalho acabou.

5) Se você ainda não chegou à raiz, volte à etapa 1 e comece tudo de novo. Desse

modo você avança etapa por etapa em direção à raiz.

6) Para cada jogador, reúna as decisões ótimas em cada um dos nós de decisão

dele. Essa coleção de decisões constitui a estratégia ótima desse jogador para o

jogo.

TEOREMA: em um jogo com informação perfeita, o perfil de estratégias

selecionado pelo processo de indução retroativa é sempre um equilíbrio de Nash.


19/51

jogador X •

nó básico trivial

nó básico não trivial

jogador X

•

•

•

nó complexo

jogador X

•

•

jogador Y

•

•


20/51

Microsoft

Microcorp

Microcorp

•

•

•

•

elegante

entrar

entrar simples

ficar

fora

ficar

fora

($380000, - $250000)

($430000, $0)

($400000, $100000)

($800000, $0)

nó de decisão básico

não trivial

nó de decisão básico

não trivial


21/51

Microsoft

Microcorp

Microcorp

•

•

•

•

elegante

entrar

entrar simples

ficar

fora

ficar

fora

($380000, - $250000)

($430000, $0)

($400000, $100000)

($800000, $0)


22/51

Microsoft

Microcorp

Microcorp

•

•

elegante

entrar simples

ficar

fora

($430000, $0)

($400000, $100000)

nó básico trivial

nó básico trivial

nó básico nãotrivial


23/51

Microsoft

Microcorp

Microcorp

•

•

elegante

entrar simples

ficar

fora

($430000, $0)

($400000, $100000)

Microsoft Microcorp •

elegante

ficar

fora

($430000, $0)


24/51

Microsoft

Microcorp

Microcorp

•

•

•

•

elegante

entrar

entrar simples

ficar

fora

ficar

fora

($380000, - $250000)

($430000, $0)

($400000, $100000)

($800000, $0)


25/51

Relembrando a matriz de recompensas:

Macrosoft

Elegante Simples

Microcorp

(entrar, entrar ) -$250000, $380000 *$100000, $400000*




nós temos que o perfil de estratégias que representa a escolha ótima é {Elegante,

(ficar fora, entrar )}


26/51

jogador A

jogador B

jogador B

jogador A

(10, 100)

(12, 200)

(10, 200)

(15, 25)

(0, 50)

rápido

devagar

acima

acima

abaixo

abaixo frear

acelerar

•

•

•

•

•


27/51

jogador A

jogador B

jogador B

jogador A

(10, 100)

(12, 200)

(10, 200)

(15, 25)

rápido

devagar

acima

acima

abaixo

abaixo frear

•

•

•

•


28/51

jogador A

jogador B

jogador B

(12, 200)

(10, 200)

rápido

devagar

acima

abaixo •

•

jogador A

jogador B

(12, 200)

rápido

abaixo •


29/51

As estratégias do jogador A são (uma tomada de decisão para cada nó de

decisão):

(rápido, acelerar ); (rápido, frear); (devagar, acelerar ); (devagar, frear ).

As estratégias do jogador B são (uma tomada de decisão para cada nó de

decisão):

(acima, acima); (acima, abaixo); (abaixo, acima); (abaixo, abaixo).

A matriz de resultados é dada por:

Jogador B

(acima, acima) (acima, abaixo) (abaixo, acima) (abaixo, abaixo)

J o g a

d o r A

(rápido, acelerar ) *10, 100 10, 100 *12, 200* 12, 200*

(rápido, frear ) *10, 100 10, 100 [*12, 200*] 12, 200*

(devagar, acelerar ) *10, 200* 0, 50 10, 200* 0, 50(devagar, frear ) *10, 200* 0,50 10, 200* 0, 50


30/51

Ameaças:

Jogadores podem tentar influenciar o comportamento do jogador que antecede a

as tomada de decisão através de uma ameaça. Uma ameaça pode ser crível ou

ser uma conversa fiada.

Uma ameaça crível existe somente se for do interesse do próprio jogador levar a

cabo a ameaça dada a opção. Ameaças que não são críveis (conversa fiada) são

ignoradas por todos os jogadores racionais.

Outra forma de ameaça é a ameaça vinculadora. Nesse caso uma vez feita a

ameaça não é possível voltar atrás, como em um contrato, por exemplo.


31/51

Microcorp

Microsoft

Microsoft

Microsoft

Microsoft

(-250, 380)

(100, 400)

(-250, 380)

(0, 800)

(0, 430)

(100, 400)

(0, 430)

(0, 800)

●

●

●

●

●

●

●

●


32/51

Microcorp

Microsoft

Microsoft

Microsoft

Microsoft

(-250, 380)

(100, 400)

(-250, 380)

(0, 800)

(0, 430)

(100, 400)

(0, 430)

(0, 800)

●

●

●

●

●

●

●

●


33/51

Microcorp

Microsoft

Microsoft

Microsoft

Microsoft

(0, 800)

(0, 430)

(100, 400)

(0, 800)

elegante

simples

simples

simples

●

●

●

●


34/51

Microcorp

Microsoft

Microsoft

Microsoft

Microsoft

(0, 800)

(0, 430)

(100, 400)

(0, 800)

elegante

simples

simples

simples

●

●

●

●

Microcorpentrar, entrar

Microsoft (100, 400)simples

●


35/51

Note que o resultado era diferente quando a Micorsoft era a primeira a se mover:

Macrosoft

Elegante Simples

Microcorp

(entrar, entrar ) -$250000, $380000 *$100000, $400000*




O novo resultado, do perfil de estratégias {(entrar, entrar ), (simples, simples,

elegante, simples)} é melhor para a Microcorp do que o original, neste caso

dizemos que existe uma vantagem do primeiro a se mover .


36/51

Subjogos e equilíbrio perfeito de subjogos

Subjogo:

1) tem os mesmo jogadores que , embora alguns deles possam não fazernenhum movimento em ;

2) O nó inicial de é uma sub-raiz de e a árvore do jogo de é composta poressa sub-raiz, todos os seus nós sucessores e os ramos entre eles;

3) As recompensas de cada jogador nos nós terminais de

são idênticas àquelas

em nos mesmo nós terminais.


37/51

Microsoft

Microcorp

Microcorp

•

•

•

•

elegante

entrar

entrar simples

ficar

fora

ficar

fora

($380000, - $250000)

($430000, $0)

($400000, $100000)

($800000, $0)

D1

D2

D3

Subjogo que

começa na

sub-raiz D2


38/51

Definição: um perfil de estratégia é um equilíbrio perfeito em subjogos de um

jogo, G, se esse perfil de estratégias for também um equilíbrio de Nash para

todo subjogo próprio de G.

Teorema: um perfil de estratégias é um equilíbrio perfeito em subjogos de um

jogo dinâmico, G, com informação perfeita, se e somente se for um equilíbrio de

Nash se lecionado pelo processo de indução retroativa.

Exemplo: Jogo de Software II


39/51

Microsoft

Microcorp Microcorp

●●Microsoft Microsoft

combater combater compartilhar compartilhar

(400, 0) (500, 0)

●● ● ●

(170, -50) (150, 50) (250, 150) (230, 90)

D1

D2 D3

D4 D5


40/51

Estratégias para a Microcorp (uma tomada de decisão para cada um de seus

nós de decisão)

(entrar, entrar ), (entrar, ficar fora), (ficar fora, entrar ), (ficar fora, ficar fora).

Estratégias para a Macrosoft (uma tomada de decisão para cada um de seus

nós de decisão)

(quarentena, combater, combater ), (quarentena, compartilhar, combater ), (sem

restrição, combater, combater ), (sem restrição, combater, compartilhar ),

(quarentena, combater, compartilhar ), (quarentena, compartilhar, compartilhar ),

(sem restrição, compartilhar, combater ), (sem restrição, compartilhar,

compartilhar )


41/51

Microsoft

Microcorp Microcorp

●●

Microsoft Microsoft

combater combater

compartilhar compartilhar

(400, 0) (500, 0)

●● ● ●

(170, -50) (150, 50) (250, 150) (230, 90)

D1

D2 D3

D4 D5


42/51

Microsoft

Microcorp Microcorp


combater combater


(400, 0) (500, 0)

●● ● ●

(170, -50) (150, 50) (250, 150) (230, 90)

D1

D2 D3

D4 D5


43/51

Microsoft

Microcorp Microcorp


combater combater


(400, 0) (500, 0)

●● ● ●

(170, -50) (150, 50) (250, 150) (230, 90)

D1

D2 D3

D4 D5


44/51

Microsoft

Microcorp Microcorp


combater combater


(400, 0) (500, 0)

●● ● ●

(170, -50) (150, 50) (250, 150) (230, 90)

D1

D2 D3

D4 D5


45/51

Microsoft

Microcorp Microcorp


combater compartilhar

(400, 0) (500, 0)

● ●

(170, -50) (250, 150)

D1

D2 D3

D4 D5


46/51


47/51

O perfil de estratégias para esse equilíbrio é {(quarentena, combater,

compartilhar ), (ficar fora, entrar )}

Microsoft

Microcorp

●

(400, 0)

D1

D2


48/51

Duopólio de Stackelberg

O que aconteceria se um duopólio de Cournot fosse modificado de modo que ao

invés de considerarmos que as duas empresas tomam a decisão de quantoproduzir ao mesmo tempo uma das empresas decidisse antes. Podemos

modelar esta situação como um jogo sequencial, mas esta estrutura de

mercados foi proposta antes da gênese da teoria dos jogos por Stackelberg em

1934.

Vejamos um exemplo com a linguagem da teoria dos jogos:

Temos duas empresas que ofertam um produto homogêneo, garrafas de água

mineral sem gás de 500 ml. A empresa SW possui uma gerência mais eficiente

de modo que ela consegue determinar antes a quantidade a produzir. SW é

chamada de empresa líder . A empresa CW é a empresa seguidora e toma a sua

decisão de quanto produzir observando a tomada de decisão de SW.

A função de demanda inversa é dada por:


49/51

A estrutura de custos é a mesma para as duas empresas: .Portanto, a função lucro para cada firma será:

Note que não importa a produção da outra firma, produzir uma quantidade

acima de 7 é uma estratégia estritamente dominada por não produzir nada, pois

produzir acima de 7 sempre gera prejuízos.


50/51

A racionalização de Stackelberg é a seguinte. A empresa seguidora maximizará

o seu lucro observando a quantidade que a empresa líder escolher ofertar,

portanto, , em equilíbrio de Nash .Se o nível de produção é positivo:

Essa função de melhor resposta é a estratégias de CW, ela informa todas as suas

tomadas de decisão para todos as tomadas de decisão de SW (lembrando sempre que

zero domina estritamente quantidades negativas e acima de 7).

SW toma a sua decisão considerando a estratégia ótima de CW (por indução

retroativa).


51/51

Documents

JOGOS DINÂMICOS