Teoria dos Jogos: Soma não constante

Prévia do material em texto

Universidade Federal Fluminense 
Profª. Lídia 1 
DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO – VEP 
PESQUISA OPERACIONAL II 
PROFª. LÍDIA 
 
 Dominância 
 
Em termos da Teoria dos Jogos, dizemos que dois jogadores possuem uma estratégia 
dominante quando todas menos uma estratégia é estritamente dominada, e o jogo é 
resolúvel por dominância estrita iterada. O jogo termina em uma solução que é um 
equilíbrio de estratégia dominante. Estes conceitos serão definidos a seguir. 
 
 
 
Considere o jogo: 
 
 
Neste jogo, para o jogador g2, a estratégia s21 é estritamente dominada pela estratégia 
s24, assim, a primeira coluna da matriz pode ser eliminada. 
 
 
 
Agora, nesta matriz reduzida, para o jogador g1, as estratégias s11 e s14 são estritamente 
dominadas pelas estratégias s12 e s13, respectivamente. Portanto, as linhas 1 e 4 podem 
 Universidade Federal Fluminense 
Profª. Lídia 2 
ser eliminadas. Além disso, a estratégia s23 do jogador g2 é estritamente dominada pela 
estratégia s22. Assim, a coluna 2 também pode ser eliminada. Obtemos então uma matriz 
reduzida 2 × 2. 
 
 
Finalmente, a estratégia s24 do jogador g2 é estritamente dominada pela estratégia s22 e, 
na matriz 2 × 1 resultante, a estratégia s13 do jogador g1 é estritamente dominada pela 
estratégia s12. Vemos então que o resultado do jogo é (3, 2), isto é, o jogador g1 escolhe 
a estratégia s12 e o jogador g2 escolhe a estratégia s22. 
 
 
O Equilíbrio de Nash 
 
 
 
É uma jogada para a qual uma estratégia é a melhor resposta à outra, 
Ou, 
Cada estratégia é a melhor resposta possível às estratégias dos demais jogadores e isso é 
verdade para todos os jogadores. 
 
Num Jogo estável, temos um Equilíbrio de Nash determinístico (Estratégias puras). 
Nestes tipos de jogos, os jogadores repetem as estratégias. Neste caso, os dois jogadores 
“concordam” com a solução: minimax = maximin = Equilíbrio de Nash, ponto de sela. 
 
No caso de Jogos instáveis, um jogador muda a estratégia como resposta à estratégia do 
outro. Eles não têm Equilíbrio de Nash se for jogado uma só vez. O jogo é resolvido em 
termos de probabilidades. 
O jogo tem que ser jogado várias vezes para se obter um Equilíbrio de Nash em 
estratégias mistas, isto é, com alternância aleatória de estratégias, segundo uma 
determinada distribuição de probabilidade. 
 
 
Jogos de Soma Não Constante 
 
 
 Universidade Federal Fluminense 
Profª. Lídia 3 
Exemplo 1.1: O dilema do prisioneiro 
 
Ele foi formulado por Albert W. Tucker, em 1950, em um seminário para psicólogos na 
Universidade de Stanford, para ilustrar a dificuldade de se analisar certos tipos de jogos. 
A situação é a seguinte: dois ladrões, Al e Bob, são capturados e acusados de um 
mesmo crime. Presos em selas separadas e sem poder se comunicar entre si, o delegado 
de plantão faz a seguinte proposta: cada um pode escolher entre confessar ou negar o 
crime. Se nenhum deles confessar, ambos serão submetidos a uma pena de 1 ano. Se os 
dois confessarem, então ambos terão pena de 5 anos. Mas se um confessar e o outro 
negar, então o que confessou será libertado e o outro será condenado a 10 anos de 
prisão. 
 
 
 
Matriz de ganhos em que cada célula contém os ganhos de Al e Bob para as estratégias 
correspondentes. 
Observe que não importa o que Al escolher: a melhor resposta de Bob será sempre 
Confessar, assim Confessar é a estratégia dominante para Bob. 
Da mesma forma, não importa o que Bob escolher: a melhor resposta de Al será sempre 
Confessar. 
Então o único Equilíbrio de Nash para este jogo é (Confessar, Confessar), muito embora 
(Negar, Negar) traga melhores recompensas para os dois jogadores. 
O único Equilíbrio de Nash é ineficiente. 
O Dilema dos prisioneiros: Jogo que exemplifica o fato de que resultados Pareto-
preferíveis não necessariamente vão ocorrer. 
Decisão pessimista. 
 
 
Exemplo 1.2: A batalha dos sexos 
 
Um homem e a sua mulher desejam sair para passear. O homem prefere assistir a um 
jogo de futebol enquanto que sua mulher prefere ir ao cinema. Se eles forem juntos para 
o futebol, então o homem tem satisfação maior do que a mulher. Por outro lado, se eles 
forem juntos ao cinema, então a mulher tem satisfação maior do que o homem. 
Finalmente, se eles saírem sozinhos, então ambos ficam igualmente insatisfeitos. Esta 
situação também pode ser modelada como um jogo estratégico. 
 
 
 Universidade Federal Fluminense 
Profª. Lídia 4 
(a) No dilema do prisioneiro (Exemplo 1.1), o perfil de estratégia (Confessar, 
Confessar) é um Equilíbrio de Nash. De fato: se um prisioneiro confessar e o outro não, 
aquele que não confessou fica preso na cadeia 10 anos, ao invés de 5 anos, se tivesse 
confessado. Além desse perfil, não existem outros Equilíbrios de Nash. 
(b) Na batalha dos sexos (Exemplo 1.2), os perfis de estratégia (Futebol, Futebol) e 
(Cinema, Cinema) são os únicos Equilíbrios de Nash do jogo. 
(c) No Exemplo 1, o único Equilíbrio de Nash do jogo é o perfil de estratégia (s12, s22). 
(d) Existem jogos que não possuem Equilíbrios de Nash em estratégias puras. 
 
Este é o caso do jogo de combinar moedas (matching pennies). Nesse jogo, dois 
jogadores exibem, ao mesmo tempo, a moeda que cada um esconde em sua mão. Se 
ambas as moedas apresentam cara ou coroa, o segundo jogador dá sua moeda para o 
primeiro. Se uma das moedas apresenta cara, enquanto a outra apresenta coroa, é a vez 
do primeiro jogador dar sua moeda para o segundo. Esse jogo se encontra representado 
por sua matriz de ganhos dada a seguir. 
 
 
 
 
Outro exemplo: 
 
A e B são dois jogadores de tênis. O jogador A tem duas estratégias: “Alto” e “Baixo”. 
Já o jogador B tem duas estratégias: “Esquerda” e “Direita”. A tabela que mostra as 
recompensas, para cada jogador, de cada uma das quatro possíveis combinações 
estratégicas, é a matriz de ganhos (payoffs) a seguir. 
 
Jogador B
Jogador A
E D
A
B
(3,9)
(0,0)
(1,8)
(2,1)
Jogador B
Jogador A
E D
A
B
(3,9)
(0,0)
(1,8)
(2,1)
E D
A
B
(3,9)
(0,0)
(1,8)
(2,1)
E D
A
B
(3,9)
(0,0)
(1,8)
(2,1)
 
 
Os ganhos do jogador A são apresentados à esquerda das vírgulas, os ganhos do jogador 
B são apresentados à direita das vírgulas. Se A jogar Alto e B jogar Direita, então o 
ganho de A é 1 e o ganho de B é 8. 
Se o jogador B jogar Direita, então a melhor resposta do jogador A é Baixo, porque isto 
melhora o ganho de A de 1 para 2. Logo, (A,D) não ocorreria. 
 
Se o jogador B jogar Direita, então a melhor resposta do jogador A é Baixo. Se o 
jogador A jogar Baixo, então a melhor resposta do jogador B é Direita. Logo, (B,D) é 
uma jogada provável. 
 
 Universidade Federal Fluminense 
Profª. Lídia 5 
Neste exemplo, tem-se dois Equilíbrios de Nash: (A,E) e (B,D). Mas qual de fato 
ocorrerá? Note que (A,E) é preferível a (B,D) para os dois jogadores. Deverá então 
ocorrer apenas (A,E)? 
 
Voltando ao exemplo do jogo de tênis: o resultado do jogo é de estratégia pura. Assim, 
(A,E) e (B,D) são Equilíbrios de Nash com estratégias puras. 
 
 
Outro exemplo 
 
(1,2) (0,4)
(0,5) (3,2)
A
B
E D
Jogador A
(1,2) (0,4)
(0,5) (3,2)
A
B
E D
Jogador A
 
 
(A,E) é um Equilíbrio de Nash? Não. 
(A,D) é um Equilíbrio de Nash? Não. 
(B,E) é um Equilíbrio de Nash? Não. 
(B,D) é um Equilíbrio de Nash? Não. 
Este jogo não tem Equilíbrio de Nash com estratégias puras, mas tem com estratégias 
mistas. 
 
Em vez de jogar puramente Alto ou Baixo, o jogador A pode escolher jogar Alto com 
probabilidade pA ou jogar Baixo com probabilidade 1- pA. Ou seja, ele pode selecionar 
uma distribuição de probabilidade (pA, 1- pA). Como A está misturando as estratégias 
puras Alto e Baixo, a distribuição de probabilidade(pA, 1- pA) é a sua estratégia mista. 
 
Similarmente, o jogador B escolhe jogar Esquerda com probabilidade pE ou jogar 
Direita com probabilidade 1- pE. Ou seja, ele escolhe a distribuição de probabilidade 
(pE,1- pE). Como ele está misturando as estratégias puras Esquerda e Direita, a 
distribuição de probabilidade (pE,1- pE) é a sua estratégia mista. 
 
(1,2) (0,4)
(0,5) (3,2)
Jogador B
Jogador A
E,pipipipiE D,1−−−−pipipipiE
A,pipipipiA
B,1−−−−pipipipiA
(1,2) (0,4)
(0,5) (3,2)
Jogador B
Jogador A
E,pipipipiE D,1−−−−pipipipiE
A,pipipipiA
B,1−−−−pipipipiA
 
 
Se B jogar Esquerda, seu ganho esperado é 2 pA+ 5(1- pA). 
 
5
16
5
10
5
6
5
25
5
32 =+=�
�
�
�
�
�
×+�
�
�
�
�
�
× 
 
Se B jogar Direita, seu ganho esperado é 4 pA + 2(1- pA). 
 
 Universidade Federal Fluminense 
Profª. Lídia 6 
5
16
5
4
5
12
5
22
5
34 =+=�
�
�
�
�
�
×+�
�
�
�
�
�
× 
 
Se 2 pA+ 5(1- pA) > 4 pA + 2(1- pA), então B jogará apenas Esquerda. Mas não existe 
Equilíbrio de Nash com B jogando apenas Esquerda. 
Se 2 pA+ 5(1- pA) < 4 pA + 2(1- pA), então B jogará apenas Direita. Mas não existe 
Equilíbrio de Nash com B jogando apenas Direita. 
Então, somente existirá Equilíbrio de Nash quando B for indiferente entre jogar 
Esquerda ou Direita, o que ocorre quando 2 pA+ 5(1- pA) = 4 pA + 2(1- pA) então pA = 
3/5. 
Para A: Se A jogar Alto, seu ganho esperado é 1 pE + 0(1- pE) = pE. 
Se A jogar Baixo, seu ganho esperado é 0 pE + 3(1 - pE) = 3(1 - pE). 
Para existir Equilíbrio de Nash, A precisa ser indiferente entre jogar Alto ou Baixo, ou 
seja, pE = 3(1 - pE). Então pE = ¾. 
Logo, para este jogo, o Equilíbrio de Nash é A adotar a estratégia mista (3/5, 2/5) e B 
adotar a estratégia mista (3/4, 1/4). 
Os ganhos serão (1,2) com probabilidade 3 5 3 4 9 20× = e (0,4) com probabilidade 
3 5 1 4 3 20× = , e (0,5) com probabilidade 2 5 3 4 6 20× = e (3,2) com probabilidade 
2 5 1 4 2 20× = . 
 
Para A, o payoff esperado do Equilíbrio de Nash é: 
 
9 3 6 2 31 0 0 3 .
20 20 20 20 4
× + × + × + × = 
 
Este também pode ser calculado substituindo pE = ¾ em 3(1 - pE). Nesse caso, também 
poderia ser percebido sem esforço que o payoff de A era igual ao valor da probabilidade 
pE. 
 
Para B, o payoff esperado do equilíbrio de Nash é 
 
9 3 6 2 162 4 5 2 .
20 20 20 20 5
× + × + × + × = 
 
Este também pode ser calculado substituindo pA = 3/5 em 2 pA+ 5(1- pA) ou em 4 pA + 
2(1- pA). 
 
Nos dois exemplos, os jogadores escolhem suas estratégias simultaneamente. Estes são 
chamados jogos simultâneos. Mas há jogos em que um jogador joga antes do outro. 
Estes são os jogos seqüenciais. O jogador que joga primeiro é o líder e o jogador que 
joga depois é o seguidor.