Upload
phungduong
View
214
Download
0
Embed Size (px)
Citation preview
CAPÍTULO IV
TEORIA DE JOGOS
TEORIA DE JOGOS
Dalila Fontes ANÁLISE DE DECISÃO Faculdade de Economia.
66
66
Teoria de Jogos
• Caracterização:
i. Cenário determinístico
ii. Um conjunto de agentes de decisão (jogadores)
iii. Um conjunto de estratégias (acções) puras
iv. Uma função utilidade para cada jogador que permite determinar
os ganhos associados a cada estratégia.
Jogos de Soma Nula
• Os jogadores são oponentes
• A soma das utilidades dos os jogadores é constante (nula)
• Se tivermos dois jogadores, o que um ganha é igual ao que o
outro perde.
TEORIA DE JOGOS
Dalila Fontes ANÁLISE DE DECISÃO Faculdade de Economia.
67
67
Exemplo 1
1 2 3 4
1 3,-3 1,-1 5,-5 2,-2
2 5,-5 3,-3 2,-2 10,-10
3 4,-4 0,0 1,-1 4,-4
• O que é ganho pelo jogador A é perdido pelo
jogador B
• É natural admitir que o resultado é o mais
favorável
• Repetições do jogo conduziriam a ciclos
� Não estável
TEORIA DE JOGOS
Dalila Fontes ANÁLISE DE DECISÃO Faculdade de Economia.
68
68
Exemplo 2
1 2 3 4
1 3,-3 1,-1 5,-5 2,-2
2 5,-5 3,-3 4,-4 10,-10
3 4,-4 0,0 1,-1 4,-4
• Nem sempre é possível encontrar uma estratégia
pura estável (ponto sela)
• Nestes casos tem de se recorrer a estratégias
mistas
• Uma estratégia mista é uma distribuição de
probabilidades
• das estratégias puras.
TEORIA DE JOGOS
Dalila Fontes ANÁLISE DE DECISÃO Faculdade de Economia.
69
69
Exemplo 3
1 2 3
1 4 3 1
2 -1 4 2
3 1 2 0
Estratégia Mista:
Jogador A (1/2,1/2,0)
Jogador B (1/6,0,5/6)
TEORIA DE JOGOS
Dalila Fontes ANÁLISE DE DECISÃO Faculdade de Economia.
70
70
• Seja pi (qi) a probabilidade do jogador A (B) optar
pela estratégia pura i.
• O vector p=[p1,p2,...,pN] (q=[q1,q2,...,qN]) definirá
a estratégia do jogador A (B).
• A solução que procuramos corresponde a optimizar
as seguintes funções:
�� =���
���
���
��� ×
ii
iiji
jppup
i
1 com minmax
e
�� =���
���
���
��� ×−
jj
jijj
iqquq
j
1 com minmax
TEORIA DE JOGOS
Dalila Fontes ANÁLISE DE DECISÃO Faculdade de Economia.
71
71
A resolução dos seguintes problemas de PL
corresponde à solução pretendida.
10
1
:a Sujeito
Maximizar
≤≤
=
≥×
�
�
i
ii
iiji
p
p
xup
x
10
1
:a Sujeito
Minimizar
≤≤
=
≤×
�
�
j
jj
jijj
q
q
yuq
y
A solução óptima corresponde a um ponto sela uma vez que
nenhum dos jogadores pode melhorar o seu resultado por
alteração somente da sua estratégia.
TEORIA DE JOGOS
Dalila Fontes ANÁLISE DE DECISÃO Faculdade de Economia.
72
72
Jogo de Soma Nula – Estratégias Mistas
Resolução gráfica:
• Apenas se pode usar com dois jogadores;
• Um deles não pode ter mais de duas/três estratégias;
• Sejam x1 e (1-x1) as probabilidades das estratégias do A;
• Sejam y1, y2,..., y3 as probabilidades das estratégias do B.
Ganhos do jogador B associados a cada estratégia:
Estratégia 1: 2111 )1( upup ×−+×
Estratégia 2: 2212 )1( upup ×−+×
�
Estratégia M: MM upup 21 )1( ×−+×
O ponto máximo da função linear por segmentos obtida minimizando os
ganhos corresponde à solução óptima.
TEORIA DE JOGOS
Dalila Fontes ANÁLISE DE DECISÃO Faculdade de Economia.
73
73
Exemplo 5
1 2 3 4
1 3 1 5 2
2 5 3 2 10
3 4 0 1 4
TEORIA DE JOGOS
Dalila Fontes ANÁLISE DE DECISÃO Faculdade de Economia.
74
74
Jogo de Soma Nula – Estratégias Mistas
• Isto faz sentido se o jogo for jogado repetitivamente.
• Mas se for jogado uma só vez qual é a lógica?
• Há uma e uma s só estratégia simples a ser jogada!
� • Nenhuma estratégia é melhor que outra sem a
influência do oponente.
• Importante é garantir que o adversário não sabe qual
a nossa opção nem quais as nossas probabilidades.
• Assim, a melhor estratégia é escolher aleatoriamente
uma estratégia pura a partir da distribuição de
probabilidades da estratégia mista óptima.
TEORIA DE JOGOS
Dalila Fontes ANÁLISE DE DECISÃO Faculdade de Economia.
75
75
Jogo de Soma não Nula
• Situações de conflito, mas nem sempre se verifica.
• Este tipo de jogos divide-se em:
i. Conflito – não há comunicação antes do jogo ii. Cooperação – há comunicação antes do jogo
Dilema do prisioneiro (Ball 1985)
Dois prisioneiros foram apanhados na posse de dinheiro
falso. A este delito corresponde uma pena dee 2 anos de
prisão. Apesar das autoridades desconfiarem que os dois
prisioneiros também são responsáveis pela produção do
referido dinheiro falso, não têm provas. A este segundo
crime corresponde uma pena de 8 anos.
A polícia oferece a cada prisioneiro a possibilidade de
confessar em troca do anulamento da sua pena se o outro
prisioneiro não confessar. Se ambos confessarem a pena é
reduzida para 5 anos.
TEORIA DE JOGOS
Dalila Fontes ANÁLISE DE DECISÃO Faculdade de Economia.
76
76
O ponto de Sela é generalizado para de Equilíbrio (Nash, 1950).
A escolha feita pelos jogadores é um ponto de equilibro se
nenhum jogador puder melhorar o seu resultado por alteração
somente da sua decisão.
Exemplo 6
C1 C2
R1 10,4 1,5
R2 9,9 0,3
Exemplo 7
C1 C2 C3
R1 10,4 1,5 98,4
R2 9,9 0,3 99,8
R3 1,98 0,100 100,98
Exemplo 8
C1 C2 C3 C4
R1 5,10 0,11 1,20 10,10
R2 4,0 1,1 2,0 20,0
R3 3,2 0,4 4,3 50,1
R4 2,93 0,92 0,91 100,90
Exemplo 9
C1 C2 C3 C4
R1 5,10 0,11 1,10 10,20
R2 4,0 1,1 2,0 20,1
R3 3,2 0,4 4,3 50,1
R4 2,93 0,92 0,91 100,90
TEORIA DE JOGOS
Dalila Fontes ANÁLISE DE DECISÃO Faculdade de Economia.
77
77
Negociação -- Cooperação
Divisão da Tarte
Sejam A e B 2 jogadores e θA e θB as suas porções.
Os ganhos serão:
Se θA+θB≤1 πA= θA e πB = θB.
Se θA+θB>1 πA= πB = 0.
Qualquer estratégia (θA,θB): θA+θB =1 é equilíbrio de Nash.
1
θ
1
Equilíbrio de Nash
Ganhos Possíveis
X
θ A
Β
X
U A
U B
Fronteira de Pareto
U A
U B U
Axiomas
Simetria a ordem dos jogadores não afecta a solução óptima
Eficiência a solução satisfaz a optimalidade de Pareto
Invariância a solução está na fronteira
Independência se eliminarmos soluções a óptima mantém-se
TEORIA DE JOGOS
Dalila Fontes ANÁLISE DE DECISÃO Faculdade de Economia.
78
78
Solução de Nash
A solução óptima corresponde a
( )( )BBAA
UUXU
UUUUU −−=≥∈
max*
Para o caso da divisão da tarte
( ) ( )0 0 max1
−−≤+ BA
BA
θθθθ
ou equivalentemente
( )( ) 1max AA θθ −
e a solução é obtida quando
( )2
10 d 2
=⇔=−A
A
AA
dθ
θθθ
TEORIA DE JOGOS
Dalila Fontes ANÁLISE DE DECISÃO Faculdade de Economia.
79
79
Negociação – Partilha de Risco
Nenhum dos indivíduos está interessado neste jogo.
E conjuntamente?
Como o poderiam dividir?
TEORIA DE JOGOS
Dalila Fontes ANÁLISE DE DECISÃO Faculdade de Economia.
80
80
Negociação – Partilha de risco
Seja (x0,y0) não pertencente a A1 nem a A2.
Se for possível encontrar (x1,y1), (x2,y2) tal que:
x1+x2=x0
y1+y2=y0
y1≤g(x1) e y2 ≤g(x2)
Então o jogo é colectivamente aceitável.
Jogo partilhado x1k e x2k
Cada partição corresponde a uma matriz de m×2 e a soma da linha k é xk. A utilidade de cada jogador é ui=p1u(x1i)+p2u(x2i)+...+pnu(xin).
Todas as soluções que satisfaçam a optimalidade de pareto são soluções
interessantes.
TEORIA DE JOGOS
Dalila Fontes ANÁLISE DE DECISÃO Faculdade de Economia.
81
81
Negociação – Partilha de risco
Fronteira de Pareto
.Para cada ponto na fronteira existe uma tangente descrita por
kuu =+ 2211 λλ , onde 121 =+ λλ e 0, 21 ≥λλ
Para cada par ),( 21 λλ encontra-se o par ),( 21 uu que
( )2211 max uu λλ +
e que se obtém fazendo
)(')(' 222111 xuxu λλ =
A fronteira é obtida variando 1λ e 2λ entre 0 e 1, tal que
121 =+ λλ
De entre estas soluções escolhe-se a que maximiza o produto
dos ganhos dos indivíduos (solução de Nash)
( ) ( ){ }0222
0111 max xxuxxu −×−
TEORIA DE JOGOS
Dalila Fontes ANÁLISE DE DECISÃO Faculdade de Economia.
82
82
Dois empresários têm a hipótese de fazer um negócio conjunto
que requer um investimento de 100 mil euros. Se este for bem
sucedido proporcionará um retorno de 60%, enquanto que se
fracassar 20% do capital investido é perdido. Os empresários
estimam as probabilidades de sucesso e fracasso em 80% e
20%, respectivamente. Caso os empresários não cheguem a
acordo, ou seja o negócio não se faça, ambos têm já prevista
uma alternativa de investimento. Neste último caso o
empresário 1 obteria um rendimento de 7% enquanto para o
empresário 2 este seria de 5%.
a) Sabendo que a função utilidade da riqueza adicional para cada
empresário é 3)( xxu = , determine e represente graficamente
todas as partilhas do referido negócio com interesse para ambos
os empresários.
b) Indique no gráfico da alínea anterior qual a partilha a escolher
recorrendo ao critério de Nash. (Dado que se pretende uma
aproximação da solução de Nash e não propriamente a solução
de Nash, pode indicar uma parte da curva em vez de um ponto.)
Notas
i) Use x para a quantidade de riqueza adicional e em milhares de euros.
ii) Se o negócio não se fizer há uma alternativa de investimento.
3)( xxu = 3 2
'
3
1)(
xxu =
TEORIA DE JOGOS
Dalila Fontes ANÁLISE DE DECISÃO Faculdade de Economia.
83
83
Resolução
As partilhas com interesse para ambos satisfazem Pareto.
⇔=⇔=3 2
2
2
3 21
12
'221
'11
33)()(
kkkk
xxxuxu
λλλλ
kk xx 22/3
211 )( λλ=⇔
Como kkkkkk xxxxxx 1221 −=⇔=+ logo
kk xx 2/32
2/31
2/31
1 λλλ
+=
Variando o valor de λ1 entre 0 e 1 (λ2=1-λ1) obtêm-se todos os
valores de x1k (x11 e x12) e x2k (x21 e x22).
Os valores de utilidade serão então calculados como
)(2.0)(8.0
)(2.0)(8.0
22212
12111
xuxuU
xuxuU
×+×=
×+×=
TEORIA DE JOGOS
Dalila Fontes ANÁLISE DE DECISÃO Faculdade de Economia.
84
84
λ1 x11 x12 U1 x21 x22 U2 0.00 0.00 0.00 0.00 60.00 -20.00 2.59 0.10 2.14 -0.71 0.85 57.86 -19.29 2.56 0.20 6.67 -2.22 1.24 53.33 -17.78 2.49 0.30 13.15 -4.38 1.56 46.85 -15.62 2.38 0.40 21.15 -7.05 1.83 38.85 -12.95 2.24 0.50 30.00 -10.00 2.05 30.00 -10.00 2.05 0.60 38.85 -12.95 2.24 21.15 -7.05 1.83 0.70 46.85 -15.62 2.38 13.15 -4.38 1.56 0.80 53.33 -17.78 2.49 6.67 -2.22 1.24 0.90 57.86 -19.29 2.56 2.14 -0.71 0.85 1.00 60.00 -20.00 2.59 0.00 -0.00 0.00
TEORIA DE JOGOS
Dalila Fontes ANÁLISE DE DECISÃO Faculdade de Economia.
85
85
Negociação – Não Cooperação
Vejamos o exemplo da divisão da tarte, mas onde existe
a possibilidade de fazer ofertas e contra ofertas.
Neste caso as estratégias não são apenas acções mas sim
regras de escolha de acções baseadas em acções
escolhidas em períodos anteriores (decisões encadeads).
Problema:
Jogadores: A e B.
Acções: oferta, aceitação e rejeição.
Ganhos: se �A for aceite ao fim de m períodos
�A = �m �Am,
�B = �m (1 - �Am,
� =1/(+r) < 1 é um factor de desconto
(incentivo para negociar mais cedo).
TEORIA DE JOGOS
Dalila Fontes ANÁLISE DE DECISÃO Faculdade de Economia.
86
86
Negociação – Não Cooperação
Primeiro, sem descontar: � =1
Suponhamos que o jogador A é o primeiro a propor �A e
o jogador B o último a aceita ou recusar.
Suponhamos também que em caso de indiferença, o
jogador em causa aceita a proposta.
���� O jogador A só está interessado na solução �A =1.
Neste caso o jogador B é indiferente pois se rejeitar
ambos recebem zero, �A = �B = 0.
Se aceitar �A =1 e �B = 0.
A vantagem do jogador A reside no facto de ser o
último a propor (oferecer), logo recebe toda a tarte.
TEORIA DE JOGOS
Dalila Fontes ANÁLISE DE DECISÃO Faculdade de Economia.
87
87
Negociação – Não Cooperação
Factor de desconto: � =0.9
Suponhamos que o jogador A é o primeiro a propor �A e
o jogador B o último a aceita ou recusar.
Análise temporal do fim para o início.
Período �A �B � iππππ Oferece
T 1 0 �T=�. �T-1 A
T-1 � 1- � �T-1= �. �T-2
B
T-2 1-�(1-�) �(1-�) �T-2= �. �T-3
A
T-3 �(1-�(1-�)) 1-�(1-�(1-�)) �T-3= �. �T-4 B
A/B obtém uma maior fatia quando propõe oferta.
Considerando só os períodos em que A propõe (ou B) o
ganho diminui com o tempo.
Continuando a parte de A tende para 1/(1+�) (=0.526)
TEORIA DE JOGOS
Dalila Fontes ANÁLISE DE DECISÃO Faculdade de Economia.
88
88
Negociação – Não Cooperação
Factor de desconto diferentes, i.e. �A e �B
Quaisquer que sejam os factores de desconto, a parte de
A é dada por:
BA
BA γγγγγγγγ
γγγγθθθθ−
−=
11
Considerando os factores de desconto forem iguais
podemos concluir que:
• Se � for baixo então há incentivo a chegar a
acordo cedo logo a importância do primeiro
período é muito grande. (�=0.1 então �A=0.909)
• Se � for elevado então não há incentivo a chegar a
acordo cedo. (�=0.99 então �A=0.503)
TEORIA DE JOGOS
Dalila Fontes ANÁLISE DE DECISÃO Faculdade de Economia.
89
89
Negociação – Não Cooperação
Com custo de negociação (sem desconto) e tendo
B um custo de “atraso” maior.
Análise temporal.
Período �A �B Oferece
T x 1-x B
T+1 x+CB 1-x-CB A
T+2 x+CB-CA 1-x-CB+CA B
T+3 x+2CB-CA 1-x-2CB+CA A
T+4 x+2CB-2CA 1-x-2CB+2CA B
Como o custo do B é maior do que o custo de A, o A
recebe cada vez mais (e B cada vez menos), ou seja, B
estaria disposto a desistir e ganhar zero.
A fica com tudo, pois o B tem mais a perder.
TEORIA DE JOGOS
Dalila Fontes ANÁLISE DE DECISÃO Faculdade de Economia.
90
90
Negociação – Não Cooperação
Com custo de negociação (sem desconto) e tendo
A um custo de “atraso” maior.
O A recebe cB e o B recebe 1-cB .
O A sabe que o B vai oferecer (0,1) no segundo período.
Do primeiro para o segundo período o B vai perder cB
então está disposto a aceitar 1- cB no primeiro período.
Com custos de negociação iguais (sem desconto).
Qualquer divisão onde cada um dos intervenientes
receba pelo menos c=cA=cB corresponde a um ponto de
equilíbrio.
TEORIA DE JOGOS
Dalila Fontes ANÁLISE DE DECISÃO Faculdade de Economia.
91
91
Jogos com n-pessoas
Função característica
{ }nN ,,2,1 �= --conjunto de jogadores.
NS ⊆ -- é uma coligação de |S| jogadores.
)(SV --função característica.
Exemplo 1:
O José Silva desenvolveu um medicamento novo que
não consegue produzir e comercializar sozinho. No
entanto pode vender a fórmula a uma de duas empresas
farmacêuticas. O José e a empresa por ele seleccionada
dividirão o lucro de 1 milhão de euros.
1}),({0})({})({
,0({})
===
=
empresaJoséV
empresaVJoséV
V
TEORIA DE JOGOS
Dalila Fontes ANÁLISE DE DECISÃO Faculdade de Economia.
92
92
Exemplo 2:
O Sr. António é dono de um terreno que vale 1 milhão
de euros. O terreno pode ser urbanizado e como tal o seu
valor comercial aumentará.
Se a urbanização for feita pela empresa SC o seu valor
passará para 2 milhões de euros, enquanto que se esta for
feita pela ME este valor será de 3 milhões de euros.
Encontre a função característica para cada um destes
exemplos.
TEORIA DE JOGOS
Dalila Fontes ANÁLISE DE DECISÃO Faculdade de Economia.
93
93
Propriedades da Função Característica
Superaditividade
Sejam A e B dois subconjuntos de jogadores
{}. e , =∩⊆ BANBA
Então
)()()( BVAVBAV +≥∪
Racionalidade
Seja },,,{ 21 nxxxX �= o vector dos ganhos.
X é solução candidata se
Nii
n
ii
iVx
xNV
∈
=
∀≥
= �
}),({
)(1
Determine as soluções do exemplo 2.
TEORIA DE JOGOS
Dalila Fontes ANÁLISE DE DECISÃO Faculdade de Economia.
94
94
Dominância
Dados dois vectores de ganhos },,,{ 21 nxxxX �=
e },,,{ 21 nyyyY �= diz-se que Y domina X com
uma coligação S, Y >S X se:
Siiiji
Sii
xyxySj
SVy
∈
∈
∀≥>∈∃
≤�
, e :
)(
1
A solução X pode ser eliminada, pois nunca será
escolhida, já que os jogadores em S se podem juntar em
coligação e como tal receber os ganhos em Y.
TEORIA DE JOGOS
Dalila Fontes ANÁLISE DE DECISÃO Faculdade de Economia.
95
95
Exemplo 3:
Considere um jogo com 3 pessoas, com a seguinte
função característica.
0({}) =V
0})3({})2({})1({ === VVV
2.0})3,2({2.0})3,1({1.0})2,1({
===
V
V
V
1})3,2,1({ =V
Sejam X e Y as soluções dadas a seguir:
)05.0,09.0,05.0(=X e )1.0,8.0,1.0(=X .
Mostre que XY }3,1{> .
TEORIA DE JOGOS
Dalila Fontes ANÁLISE DE DECISÃO Faculdade de Economia.
96
96
Encontrar Soluções Não Dominadas
Exemplo 1:
},,,{ 21 nxxxX �= é solução sse:
3,2,1}),({ =≥ iiVxi e 11
=�=
n
iix
X é não dominada sse:
NSSi
i SVx ⊆∈
∀≥� )(
Exemplo 2:
TEORIA DE JOGOS
Dalila Fontes ANÁLISE DE DECISÃO Faculdade de Economia.
97
97
Valor de Shappley
As soluções não dominadas nem sempre proporcionam
ganhos equitativos.
No exemplo 1, o inventor do medicamento é o jogador
mais importante. Mas faz sentido receber todo o lucro?
Lloyd Shappely desenvolveu uma forma alternativa de
distribuir os ganhos, baseada nos seguintes axiomas.
Axioma 1: alterar a ordem dos jogadores conduz á troca
dos respectivos ganhos.
Axioma 2: )(1
NVxn
ii =�
=
Axioma 3: Um jogador que não acrescente valor a
nenhuma coligação recebe 0.
TEORIA DE JOGOS
Dalila Fontes ANÁLISE DE DECISÃO Faculdade de Economia.
98
98
Axioma 4: Se x e y são os valores de shappley para os
jogos V eV , respectivamente. Então x+y é o valor de
shappley para o VV +
Valor de Shappley
Se os axiomas forem aceites então
�⊆∀∉
−∪=NSSini SViSVSPx
:))(}){()((
onde
n!
SnSSPn
)!1( ! )(
−−=