Upload
phunghanh
View
419
Download
0
Embed Size (px)
Citation preview
77
CAPÍTULO 6*
JOGOS NA FORMA ESTRATÉGICA COM INFORMAÇÃO COMPLETA
Objetivos: Definir a forma normal ou estratégica para representação de jogos estáticos
com informação completa e desenvolver os conceitos básicos de solução.
6.10-EXERCÍCIOS
Exercício 6.1-Suponha que cada jogador i num jogo J=(n; S1,…, Sn; u1,…, un) possui
uma estratégia estritamente dominante si. Mostre diretamente da definição de estratégias
estritamente dominantes que s=( si)i=1,...,n é o único equilíbrio de Nash do jogo.
Resolução:
Mostremos em primeiro lugar que s é um equilíbrio de Nash.
Suponha, por contradição, que s não é um equilíbrio de Nash. Então, existem um
jogador i e uma estratégia siʹ′∈Si disponível para o jogador i, tais que:
ui(siʹ′, s−i) > ui(si, s−i) (i)
Mas então, necessariamente, siʹ′ ≠ si. Como si é uma estratégia estritamente
dominante,
ui(si, s−i) > ui(siʹ′, s−i) (ii)
Mas (i) e (ii) são incompatíveis. Portanto, s é um equilíbrio de Nash do jogo.
Mostremos agora que não existe outro equilíbrio de Nash nesse jogo.
Suponha, por contradição, que existe um EN do jogo sʹ′=( siʹ′)i=1,...,n distinto de s.
Então existem um jogador i e uma estratégia siʹ′∈Si, disponível para o jogador i, siʹ′ ≠ si,
tais que:
ui(siʹ′, sʹ′−i) ≥ ui(si, sʹ′−i) (i)
No entanto, como si é uma estratégia estritamente dominante do jogador i,
ui(si, sʹ′−i) > ui(siʹ′, sʹ′−i) (ii)
Novamente, as condições (i) e (ii) levam a uma contradição, o que garante a
unicidade do equilíbrio de Nash s. * © Marilda Sotomayor e Maurício Bugarin, 2001, 2002, 2003, 2004, 2005, 2013.
78
Exercício 6.2*-Mostre que o processo de eliminação iterativa de estratégias
estritamente dominadas leva ao mesmo resultado independentemente da ordem
escolhida para a eliminação de estratégias.
Resolução:
Suponha, por contradição, que aplicando o processo de EIED seguindo uma
ordem o1 leva a um resultado s e que aplicando-o seguindo outra ordem o2 leva a outro
resultado sʹ′≠s. Então siʹ′ ≠ si para pelo menos um jogador i. Portanto, alguma estratégia
no perfil sʹ′ é eliminada durante o processo o1. Seja siʹ′ a primeira estratégia no perfil sʹ′
eliminada durante esse processo o1. Então existe siʺ″∈Si tal que:
ui(siʺ″, sʹ′−i) > ui(siʹ′, sʹ′−i) (i)
No entanto, como o processo o2 também levou a um equilíbrio de Nash, temos:
ui(siʹ′, sʹ′−i) ≥ ui(siʺ″, sʹ′−i) (ii)
Mas as condições (i) e (ii) levam a uma contradição, o conclui a demonstração.
Exercício 6.3-Mostre, por meio de um contra-exemplo, que o processo de eliminação
iterativa de estratégias fracamente dominadas pode levar a resultados diferentes
dependendo da ordem de eliminação escolhida.
Resolução:
Considere o jogo a seguir.
2
t1 t2 t3
1 s1 14, 12 18, 6 20, 12
s2 15, 2 20, 2 16, 1
Observe que a estratégia t1 domina fracamente ambas as estratégias t2 e t3.
Se iniciarmos eliminando a estratégia t2, não há mais nenhuma estratégia
estritamente dominada. Eliminando então a estratégia fracamente dominada t3 obtemos
79
um jogo em que 2 tem apenas a jogada t1 e a melhor resposta para 1 é s2, resultando no
equilíbrio de Nash (s2, t1).
Por outro lado, se iniciarmos eliminando a estratégia t3, então s2 passa a dominar
estritamente s1 no jogo reduzido. Portanto, s1 pode ser eliminada. Já no jogo resultante 2
é indiferente entre t1 e t2 e o processo de eliminação pára, indicando a existência de mais
um equilíbrio de Nash não encontrado quando usada a outra ordenação: (s2, t2).
Exercício 6.4-Mostre que se o processo de eliminação iterativa de estratégias
estritamente dominadas levar a uma única solução, então o jogo possui um único
equilíbrio de Nash.
Resolução:
Suponha que o processo de EIED leva a um resultado único s, que é então um
equilíbrio de Nash do jogo, e suponha ainda, por contradição, que existe outro equilíbrio
de Nash sʹ′≠s. Então siʹ′ ≠ si para pelo menos um jogador i. Portanto, alguma estratégia
no perfil sʹ′ é eliminada durante o processo de EIED. Seja siʹ′ a primeira estratégia no
perfil sʹ′ eliminada durante esse processo. Então existe siʺ″∈Si tal que:
ui(siʺ″, sʹ′−i) > ui(siʹ′, sʹ′−i) (i)
No entanto, como sʹ′ é um equilíbrio de Nash, temos:
ui(siʹ′, sʹ′−i) ≥ ui(siʺ″, sʹ′−i) (ii)
Mas as condições (i) e (ii) levam a uma contradição, o conclui a demonstração.
Exercício 6.5-Encontre todos os equilíbrios de Nash em estratégias puras do jogo
batalha dos sexos e do jogo do banana.
Resolução:
Batalha dos Sexos:
2
T S
1 T 3, 2 1, 1
S 0, 0 2, 3
80
1: T ⇒ MR2: T ⇒ MR1: T: EN: (T, T)
1: S ⇒ MR2: S ⇒ MR1: S: EN: (S, S)
Jogo do Banana:
2
d m
1 D 0, 0 10, 50
M 50, 10 –100, –100
1: D ⇒ MR2: m ⇒ MR1: D: EN: (D, m)
1: M ⇒ MR2: d ⇒ MR1: M: EN: (M, d)
Exercício 6.6-Sejam J=(n; S1,…, Sn; u1,…, un) um jogo na forma normal e σ=(σ1,…,σn)
um equilíbrio de Nash em estratégias mistas do jogo. Suponha que, para algum jogador
i, existem duas estratégias si, siʹ′∈Si tais que σi(si)σi(siʹ′)>0. Prove que:
Eui(si, σ−i) = Eui(siʹ′, σ−i).
Resolução:
Suponha, por contradição, que Eui(si, σ−i) ≠ Eui(siʹ′, σ−i). Então podemos supor, sem
perda de generalidade, que Eui(si, σ−i) > Eui(siʹ′, σ−i). Considere então a estratégia mista
µi para o jogador i que escolhe cada uma das estratégias puras outras que si e siʹ′ com a
mesma probabilidade de que σi, que escolhe si com a probabilidade σi(si)+σi(siʹ′), e que
escolhe siʹ′ com a probabilidade 0:
µi(si)=σi(si)+σi(siʹ′)
µi(siʹ′)=0
µi(ri)=σi(ri), ∀ri∈Si, ri ≠ si, siʹ′
Então, por construção, Eui(µi, σ−i)>Eui(σ), o que contradiz a hipótese de que σ é
um equilíbrio de Nash do jogo.
81
Exercício 6.7-Encontre todos os equilíbrios de Nash do jogo pedra, papel ou tesoura.
Atenção: analise todos os casos possíveis.
Resolução:
Verifica-se imediatamente que não existe equilíbrio de Nash em estratégias
puras. Suponha que o jogador 1 seleciona uma estratégia mista envolvendo apenas PE e
PA. Então qualquer melhor resposta de 2 escolherá pe com probabilidade zero. Mas
então, qualquer melhor resposta de 1 escolherá TE no lugar de PA, uma contradição.
Argumento semelhante aplica-se sempre que qualquer jogador escolher uma estratégia
mista envolvendo apenas duas estratégias puras. Portanto em qualquer equilíbrio de
Nash todos os jogadores escolhem cada uma de suas três opções com probabilidade
positiva.
Suponha que o jogador 1 escolhe PE com probabilidade α, PA com
probabilidade β e TE com probabilidade γ=1−α−β, com α.β.γ≠0. Então, se denotarmos
a estratégia de 1 por ( )γβασ ,,1 = , pelo exercício anterior,
Eu2(pe, σ1) = Eu2(pa, σ1)= Eu2(te, σ1).
2
pe pa te
PE 0, 0 −1, 1 1, −1
1 PA 1, −1 0, 0 −1, 1
TE −1, 1 1, −1 0, 0
Mas, Eu2(pe, σ1) =−β+γ; Eu2(pa, σ1)=α−γ, Eu2(te, σ1)=−α+β.
Portanto, 2γβ
α+
= , 2βα
γ+
= , 2γα
β+
= . Donde, 31
=== γβα . De forma
semelhante mostra-se que 2 joga cada uma de suas estratégias puras com a mesma
probabilidade 1/3. Portanto, o único equilíbrio e Nash do jogo á:
( ) .31,
31,
31,
31,
31,
31, 21 ⎟⎟
⎠
⎞⎜⎜⎝
⎛⎟⎠
⎞⎜⎝
⎛⎟⎠
⎞⎜⎝
⎛== σσσ
82
Exercício 6.8-Considere o duopólio de Cournot com conjuntos de estratégias contínuos
apresentado no exemplo 6.2.
(i) Encontre o equilíbrio de Nash do jogo, justificando o método de resolução usado.
(ii) Suponha agora que o jogo tem n jogadores idênticos. Usando o mesmo método
desenvolvido em (i), encontre o EN desse jogo, como função do número de
jogadores n.
(iii) Calcule o preço de mercado correspondente e determine o limite, quando n→+∞ do
preço de mercado e compare com o equilíbrio que seria obtido em concorrência
perfeita.
Exercício 6.9-Considere uma variação do duopólio de Cournot estudado no exemplo
6.2 no qual as duas empresas possuem custos diferenciados, dados por c1(x1)=6x1 e
c2(x2)=3x2. Os demais parâmetros do jogo permanecem inalterados.
(i) Determine o EN desse novo jogo e compare que com EN do jogo anterior.
(ii) Determine a produção de cada jogador se ambos se juntarem e decidirem produzir
de forma a maximizar o lucro conjunto.
Exercício 6.10-Considere uma outra variação do duopólio de Cournot na qual as duas
empresas não apenas possuem custos diferenciados, mas também produzem bens
diferenciados. Apesar de diferenciados, os bens produzidos pelas duas empresas são
substitutos parciais, de forma que a oferta de um tipo de bem afeta a demanda pelo
outro tipo. As curvas respectivas de demanda inversa são dadas por:
p1(x1, x2)= A−ax1−bx2
p2(x1, x2)= B−cx1−dx2
Na expressão acima, A, B, a, b, c e d são parâmetros positivos tais que A> a+b,
B> c+d, a>b e d>c. Observe que o parâmetro b mede o efeito da produção do bem 2 na
demanda pelo bem 1 enquanto o parâmetro c mede o efeito da produção do bem 1 na
demanda do bem 2. Os custos de produção respectivos são dados pelas expressões
abaixo em que α e β são parâmetros positivos.
c1(x1)=α x1
83
c2(x2)= β x2
(i) Determine o equilíbrio de Nash ( )21 ˆ,ˆ xx desse novo jogo.
(ii) Determine o lucro πi de cada firma i=1,2 e mostre que ( ) ( )21211 ˆˆ,ˆ xaxx =π e
( ) ( )22212 ˆˆ,ˆ xdxx =π .
(iii) Desenvolva uma análise de estática comparada para determinar o efeito de cada um
dos parâmetros no equilíbrio.
(iv) Determine a produção de cada jogador se ambos se juntarem e decidirem produzir
de forma a maximizar o lucro conjunto. Compare com os resultados anteriores.
Exercício 6.11-Considere o duopólio de Bertrand analisado no texto. Suponha agora
que os preços são discretos, podendo variar no máximo de centavo em centavo: p=0;
0,01; 0,02;...; 5,99; 6,00; 6,01; 6,02;... . Determine o(s) equilíbrio(s) desse novo jogo.
Exercício 6.12-Considere novamente o duopólio de Bertrand analisado no texto.
Suponha agora que as firmas têm custos de produção diferenciados, dados por
c1(x1)=6x1 e c2(x2)= 4x2. Determine o equilíbrio de Bertrand do jogo quando os possíveis
preços são discretos como no exercício anterior. O que acontece se os preços forem
variáveis contínuas?
Exercício 6.13-Considere novamente o duopólio de Bertrand analisado no texto.
Suponha agora que existem n empresas, todas determinando simultaneamente seus
preços. Que efeito essa hipótese tem sobre o equilíbrio? Compare com o análogo para o
jogo de Cournot.
Exercício 6.14-Considere outra variação do duopólio de Bertrand na qual as duas
empresas não apenas possuem custos diferenciados, mas também produzem bens
diferenciados. Apesar de diferenciados, os bens produzidos pelas duas empresas são
84
substitutos parciais, de forma que a oferta de um tipo de bem afeta a demanda pelo
outro tipo. As curvas de demanda respectivas são dadas por:
x1(p1, p2)= A−ap1+bp2
x2(p1, p2)= B+cp1−dp2
Na expressão acima, A, B, a, b, c e d são parâmetros positivos tais que A> a, B>
d, a>b e d>c. Observe que o parâmetro b mede o efeito da produção do bem 2 na
demanda pelo bem 1 enquanto o parâmetro c mede o efeito da produção do bem 1 na
demanda do bem 2. Os custos de produção respectivos são dados pelas expressões
abaixo em que α e β são parâmetros positivos.
c1(x1)=α x1
c2(x2)= β x2
(i) Determine o equilíbrio de Nash desse novo jogo.
(ii) Determine o lucro de cada firma.
(iii) Desenvolva uma análise de estática comparada para determinar o efeito de cada um
dos parâmetros no equilíbrio.
(iv) Determine a produção de cada jogador se ambos se juntarem e decidirem produzir
de forma a maximizar o lucro conjunto. Compare com os resultados anteriores.
Exercício 6.15-Mostre que num jogo entre duas pessoas toda estratégia dominante é
uma estratégia maximin. Conclua que se o jogo é solúvel por estratégias dominantes, ele
também é solúvel por estratégias prudentes. O que você pode dizer de um jogo solúvel
por eliminação iterativa de estratégias dominantes?
Exercício 6.16-Considere a seguinte variação da “Guerra de Nervos”. Dois jogadores 1
e 2 devem decidir simultaneamente quanto tempo passar participando do jogo, t1 e t2
respectivamente. O jogo termina quando pelo menos um dos jogadores conclui sua
participação. O jogador que permanecer mais tempo no jogo receberá um prêmio em
valor monetário igual ao tempo de duração do jogo. Caso os dois jogadores decidam
sair do jogo no mesmo momento, cada um recebe um prêmio em valor monetário
85
equivalente à metade do tempo de duração do jogo. Não existe custo de participação no
jogo. Modele essa situação como um jogo estático e determine seus equilíbrios de Nash.
Exercício 6.17-Considere um jogo de soma zero entre duas pessoas em que o conjunto
de estratégias do jogador 1 é um conjunto C1⊆Rm e o conjunto de estratégias do jogador
2 é um conjunto C2 ⊆ Rn, sendo C1 e C2 dois conjuntos compactos. Seja F(x,y) o
payoff do jogador 1, isto é, a quantia que o jogador 2 terá que pagar a 1 se as
estratégias escolhidas forem x e y. A função F: C1× C2 → R é suposta contínua.
Defina:
( ) ( )yxFxfCy
,min2∈
= , ( ) ( )yxFygCx
,max1∈
= ,
( ) ( )xfyxFvCx 1
max,minmax1∈
== , ( ) ( )ygyxFvCy 2
min,maxmin2∈
==− .
Verifique que f, g, v1 e v2 estão bem definidos e mostre que:
(i) v1≤ −v2.
(ii) Se (x*,y*) é um perfil de estratégias satisfazendo:
( ) ( ) ( ) .,,*,**,*, 21 CyCxyxFyxFyxF ∈∈∀≥≥
Então (x*,y*) é um equilíbrio de Nash do jogo.
(iii) Se existe um equilíbrio de Nash então v1=−v2 e, reciprocamente, se v1=−v2 então
existe pelo menos um equilíbrio de Nash no jogo.
(iv) Quaisquer dois equilíbrios de Nash do jogo correspondem ao mesmo valor do
payoff para os jogadores.
(v) Se (x,y) e (xʹ′,yʹ′) são equilíbrios de Nash então (x,yʹ′) e (xʹ′,y) também o são.
Exercício 6.18-Encontre todos os equilíbrios de Nash do jogo representado pela matriz
a seguir.
2
86
e c d
1 a 1, 2 2, 4 6, 8
b 2, 8 4, 6 4, 0
Exercício 6.19-Considere um jogo com três jogadores com o mesmo conjunto de
estratégias S={1, 2, 3}. Os payoffs do jogo são calculados da seguinte forma: cada
jogador recebe 4 vezes o menor número selecionado pelos demais jogadores, menos o
número por ele selecionado. Represente o jogo na forma matricial e encontre todos seus
equilíbrios de Nash.
Exercício 6.20-Considere o seguinte método de eliminação de estratégias: se existir
uma estratégia si para um jogador i tal que, para cada escolha dos outros jogadores,
existe uma estratégia siʹ′ estritamente melhor que si, então si pode ser eliminada pois
nunca fará parte de um equilíbrio de Nash do jogo. Assim, si será eliminada se:
(P) ∀s–i∈S–i, ∃ siʹ′∈Si | ui(s–i, siʹ′) > ui(s–i, si)
A diferença entre a propriedade (P) e a propriedade de dominância é que agora
não é necessária a existência de uma única estratégia que domine si para que ela seja
eliminada: basta que exista sempre uma alternativa melhor que si para o jogador i, para
cada escolha dos outros jogadores.
(i) Prove que se si satisfizer a propriedade (P), então si não pode fazer parte de nenhum
equilíbrio de Nash em estratégias puras.
(ii) Encontre todos os equilíbrios de Nash do jogo abaixo e conclua a respeito da
validade do método de eliminação proposto.
2
e c d
1 a 4, 2 2, 8 3, 6
b 2, 8 4, 2 3, 6
87
Exercício 6.21-Dois indivíduos formam uma parceria produtiva. Quando o parceiro i
trabalha xi horas por dia, i=1,2, eles produzem um resultado cujo valor é de
80(x1+x2)1/2. O custo do trabalho de cada indivíduo é de 10 reais por hora e os parceiros
dividem igualmente o resultado do trabalho conjunto. Considere o jogo estático com
informação completa no qual os agentes escolhem simultaneamente seus esforços.
(i) Descreva a forma normal desse jogo.
(ii) Encontre todos os seus equilíbrios de Nash.
(iii) Determine um perfil de estratégias eficiente e verifique se ele pode ser obtido como
um equilíbrio de Nash. Interprete sua resposta.
(iv) Esse jogo se assemelha a algum dos exemplos vistos estudados?
Exercício 6.22-O exemplo 6.16 estudou equilíbrios de Nash num leilão de primeiro
preço. Considere a seguinte alteração naquele modelo: o vencedor continua sendo o
jogador que fizer o maior lance, mas agora ele paga pelo objeto apenas o segundo maior
lance. Trata-se de um leilão de segundo preço ou ainda leilão de Vickrey.
(i) Suponha que existem apenas dois jogadores, 1 e 2, com v1>v2. Encontre um EN no
qual 2 ganha o objeto.
(ii) Generalize o resultado obtido acima para um número qualquer de jogadores. O
equilíbrio encontrado é eficiente?
(iii) Mostre que existe um equilíbrio de Nash desse jogo em que cada jogador escolhe
um lance igual a seu verdadeiro valor pelo objeto: li=vi, para todo jogador i.
Exercício 6.23-Considere o seguinte jogo na forma normal.
2
A B C
88
a −1, 1 2, −2 5, 0
1 b 0, 3 −1, 2 4, 3
c 2, −2 −1, 1 6, −3
d −2, 2 1, 3 4, −1
(i) Usando eliminação iterativa de estratégias estritamente dominadas, reduza o jogo
acima a um jogo 2×2.
(ii) Encontre todos os equilíbrios de Nash (em estratégias puras e mistas) do jogo
resultante.
(iii) Identifique o jogo resultante como uma variação de algum jogo clássico conhecido
e comente.
Exercício 6.24-Considere o seguinte jogo na forma normal.
2
A B C D
1 a 5, 3 2, 1 0, 2 1, 0
b 0, 0 3, 4 5, 3 2, 3
c 2, 4 2, 6 1, 7 1, 8
(i) Mostre que a estratégia c é estritamente dominada por uma combinação linear
λa+(1−λ)b das estratégias a e b, e elimine-a.
(ii) No jogo resultante existe uma estratégia estritamente dominada. Determine essa
estratégia e elimine-a.
(iii) Encontre todos os equilíbrios de Nash do jogo resultante.
Exercício 6.25- Considere o jogo na forma normal apresentado a seguir.
2
89
t1 t2 t3 t4 t5
s1 40,0 0,10 1,6 10,8 20,7
1 s2 5,−5 −1,−2 2,4 20,−3 0,0
s3 0,−10 3,1 1,−1 10,0 30,−1
s4 20,10 −1,20 0,0 5,40 10,5
(i) Aplique o processo de eliminação iterativa de estratégias dominadas, usando
estratégias puras para eliminar três estratégias que não serão jogadas em nenhum
equilíbrio de Nash, reduzindo o jogo acima a um jogo 3x3.
Resolução:
s1 domina estritamente s4, portanto, s4 pode ser excluída.
No jogo reduzido (e mesmo no original) t2 domina estritamente t1, portanto, t1
pode ser excluída. Além disso, t2 também domina estritamente t4, portanto, t4
pode ser excluída.
O jogo resultante é:
t2 t3 t5
s1 0,10 1,6 20,7
1 s2 −1,−2 2,4 0,0
s3 3,1 1,−1 30,−1
(ii) Continue aplicando o processo de eliminação iterativa de estratégias dominadas,
usando agora estratégias mistas simples para eliminar mais duas estratégias que não
serão jogadas em nenhum equilíbrio de Nash, reduzindo o jogo agora a um jogo
2x2.
!!𝑡! +
!!𝑡! s1 domina estritamente 𝑡!, portanto, 𝑡! pode ser excluída.
!!𝑠! +
!!𝑠! s1 domina estritamente 𝑠!, portanto, 𝑠! pode ser excluída.
O jogo resultante é:
90
t2 t3
1 s2 −1,−2 2,4
s3 3,1 1,−1
(iii) Encontre todos os equilíbrios de Nash do jogo reduzido 2x2, em estratégias mistas.
Estratégias puras: 𝑠!, 𝑡! , 𝑠!, 𝑡! .
Estratégia mista: !!𝑠! +
!!𝑠!,
!!𝑡! +
!!𝑡! .
Exercício 6.26-Seja ϕ o mecanismo de leilão de primeiro preço e seja b um equilíbrio
de Nash do jogo associado. Mostre que ϕ(b) é um equilíbrio competitivo para o
mercado M=(P, Q, a).