LISTA DE EXERCÍCIOS 3

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Profº Túlio de Almeida 
Pesquisa Operacional II 
 
LISTA DE EXERCÍCIOS 3 – TEORIA DOS JOGOS 
 
QUESTÕES PARA DISCUSSÃO 
 
 
Q1 O que é um jogo? Quais variáveis estão incluídas? 
 
Q2 Quais são os tipos mais comuns de jogos? 
Conceitue e cite exemplos. 
 
Q3 O que deve ser feito quando um jogo de soma 
zero não possui ponto de sela? 
 
Q4 Descreva as etapas de resolução de um jogo 
instável ou de estratégia mista. 
 
Q5 Apresente os PPL capazes de solucionar um jogo 
e explique o porque para o jogador A é usada a 
estratégia MAXIMIN e para o jogador B é usada a 
estratégia MINIMAX. 
 
Q6 Explique o Dilema dos Prisioneiros, trazendo para 
um cenário atual de “Delações Premiadas”. 
 
Q7 Quais as diferenças entre um Jogo de Soma Zero 
e um Jogo de Soma Não-Constante? 
 
Q8 Explique o Equilíbrio de Nash por meio de cada 
situação: 
a. Jogos de Estratégia Pura 
b. Jogos de Estratégia Mista 
c. O Exemplo da Guerra dos Sexos 
 
 
 
EXERCÍCIOS DE FIXAÇÃO 
 
E1 Determine a solução de ponto de equilíbrio, as 
estratégias puras associadas e o valor do jogo 
para cada um dos seguintes jogos. Caso o jogo 
não tenha ponto de equilíbrio encontre os intervalos 
de variação do valor dos jogos. Os ganhos são para o 
jogador A. 
a. 
 B1 B2 B3 B4 
A1 8 6 2 8 
A2 8 9 4 5 
A3 7 5 3 5 
b. 
 B1 B2 B3 B4 
A1 4 -4 -5 6 
A2 -3 -4 -9 -2 
A3 6 7 -8 -9 
A4 7 3 -9 5 
c. 
 B1 B2 B3 B4 
A1 1 9 6 0 
A2 2 3 8 4 
A3 -5 -2 10 -3 
A4 7 4 2 -5 
d. 
 B1 B2 B3 B4 
A1 -1 9 6 8 
A2 -2 10 4 6 
A3 5 3 0 7 
A4 7 -2 8 4 
 
E2 Determine as estratégias ótimas para os 
jogadores dos jogos a seguir considerando que os 
ganhos correspondem ao jogador A. 
a. 
 B1 B2 B3 
A1 1 -3 7 
A2 2 4 -6 
b. 
 B1 B2 
A1 5 8 
A2 6 5 
A3 5 7 
c. 
 B1 B2 B3 
A1 3 -1 3 
A2 -2 -4 -1 
A3 -5 6 2 
 
E3 Determine um ponto de equilíbrio (se existir 
um de estratégias puras) os jogos de soma não 
constante apresentados nas tabelas a seguir. 
a. 
 B1 B2 
A1 (9,-1) (-2,3) 
A2 (8,7) (-9,11) 
b. 
 B1 B2 
A1 (9,9) (-10,10) 
A2 (10,-10) (-1,1) 
 
E4 Simplifique usando o método da dominância a fim 
de chegar na matriz/jogo mais simples. 
Profº Túlio de Almeida 
Pesquisa Operacional II 
 
 
24232221 ssss
 
 












)24,12()4,0()9,3()10,18(
)3,15()4,4()6,6()5,14(
)3,3()4,8()6,9()0,5(
)12,0()16,4()18,6()4,10(
s
s
s
s
14
13
12
11
 
 
E5 Obtenha a matriz de payoff para as seguintes 
situações. 
Observação: Considere um jogo de soma zero. 
a. Jogo de par ou ímpar, onde o jogador A opta pela 
opção par e o jogador B opta pela opção ímpar, ou 
seja, se der valor par a vitória é de A e se der ímpar a 
vitória é de B. As decisões são os números que eles 
jogam (número par, número ímpar ou zero). 
b. Em uma disputa de pênaltis, uma atacante possui 6 
opções de cobrança. 
 
 
1 
 
 
2 
3 
 
4 
 
 
5 6 
 
Observação: Sabe-se que o goleiro é de alto nível e 
que ele sempre agarra a bola quando acerta o local do 
chute do atacante. 
 
 
PROBLEMAS E APLICAÇÕES 
 
P1 Duas equipes, A e B, estão preparando as 
suas estratégias para um campeonato de 
basquete. Eles estão tentando determinar as suas 
bancas durante o jogo e definiram quatro formas 
de rotar seus jogadores baseados na habilidade 
de marcar 2 pontos, 3 pontos e tiros livres. A 
tabela a seguir resume os pontos que A marcará 
como função das diferentes estratégias 
contempladas por cada equipe. 
 B1 B2 B3 B4 
A1 3 -2 1 2 
A2 2 3 -3 0 
A3 -1 2 -2 2 
A4 -1 -2 4 1 
 
a. Resolver o jogo com programação linear e 
determine uma estratégia pra o jogo do 
campeonato. 
b. Baseado na informação anterior, qual das duas 
equipes ganhará o campeonato? 
 
P2 Construa uma matriz de ganhos para o 
seguinte jogo: cada uma de duas redes de 
supermercados propõe construir uma loja em uma 
região rural que é composta por três cidades. As 
distancias entre as cidades são mostradas na 
figura a seguir. 
 
Aproximadamente 45% da população da região 
vive próxima à cidade A, 35% próxima à cidade B 
e 20% próxima à cidade C. dado que a rede I é 
maior e tem uma melhor reputação que a rede II, 
ela controlará a maior parte dos negócios, sempre 
que suas situações forem idênticas. Cada rede está 
ciente do interesse da outra na região, e ambas 
fizeram pesquisas de mercado que dão projeções 
idênticas. Se ambas as redes se localizarem na 
mesma cidade ou eqüidistantes de uma cidade, a rede 
I controlará 65% dos negócios dessa cidade. Se a 
rede I ficar mais perto de uma cidade que a rede 
II, a rede I controlara 90% dos negócios dessa 
cidade. Se a rede I ficar mais distante de uma 
cidade que a rede II, ela controlará ainda 40% 
dos negócios desta cidade. O resto dos negócios 
irá sempre para a rede II. Além disso, ambas as 
redes sabem que a rede I não localizará em 
cidades muito pequenas e a cidade C pertence a esta 
categoria. 
 
P3 O exército azul e o exército vermelho estão 
disputando dois locais de aterragem, de valores 
iguais a 20 e 8 milhões de u.m. os quais estão 
ambos sob controle do exercito vermelho. O 
exército azul pretende atacar um ou ambos os 
campos e provocar o máximo de prejuízos 
(medidos em u.m.) nas instalações. O objetivo do 
exército vermelho é minimizar estes prejuízos. Para 
conseguir os seus respectivos objetivos, cada 
exercito pode aplicar a sua força total em um dos 
dois locais de aterragem ou pode dividi-la ao meio 
e cobrir ambos locais de aterragem com capacidade 
reduzida. 
Uma instalação terá 25% de danos se ela for 
atacada e defendida com a totalidade das forças, 
mas apenas 10% de danos se ela for atacada e 
Profº Túlio de Almeida 
Pesquisa Operacional II 
 
defendida a media força. Se uma instalação for 
atacada com a totalidade das forças e defendida 
a media força sofrerá 50% de danos. Qualquer 
instalação atacada a meia força ou força total, mas 
não defendida, terá completa destruição. Uma 
instalação não atacada ou uma que é atacada a 
media força, mas defendida com a totalidade das 
forças, não terá danos. Determine as estratégias 
ótimas para ambos os exércitos. 
 
P4 O exército A pretende carregar mantimentos 
para um posto de fronteira, o qual pode ser 
atacado pelo exército B dentro de algumas horas. 
O depósito de mantimentos mais próximo está 
ligado ao posto de fronteira por duas estradas 
separadas, uma passando através da floresta e 
outra numa planície. Um comboio de mantimentos 
move-se mais rapidamente pela planície, mas 
consegue uma melhor camuflagem na rota da 
floresta. O comboio deve tomar uma ou outra rota. 
O exército B previu o envio do reforço de 
mantimentos ao longo de uma das rotas e planeia 
impedi-lo com ataques aéreos. Tem disponível um 
único esquadrão de aviões, o qual não pode ser 
dividido. Se o exército B enviar os seus aviões sobre a 
rota da floresta e encontrar o exército A, o exército B 
tem tempo para quatro ataques contra
o comboio. Se 
o exército B enviar os seus aviões sobre a rota 
de planície e o exercito A está usando esta rota, 
o exercito B terá tempo para três ataques. Se o 
exército B envia seus aviões sobre a rota errada, é 
perdido um tempo valioso. Uma vez ocorrido um erro 
e localizado o comboio na outra rota, o exército B 
terá tempo para dois ataques na rota de planície, 
mas só terá tempo para um ataque na rota da 
floresta (dada a dificuldade em encontrar o 
comboio entre as árvores). Determine as estratégias 
ótimas dos dois exércitos. 
 
P5 Os Vulcanos e os Klingons estão no meio de 
uma carreira armamentista na qual supõe-se que 
cada uma das nações tem duas estratégias 
possíveis: criar um novo míssil ou manter o status 
quo. Supõe-se que a matriz de ganhos é a que 
se encontra na tabela a seguir. 
Esta matriz de ganhos está baseada na suposição 
de que se somente uma nação cria um míssil 
novo, a nação que o tiver vencerá a outra nação. 
Neste caso, a nação vencedora ganha uma 
recompensa de 20 unidades y a nação 
conquistada perde 100 unidades. 
Supõe-se também que o custo de criar um novo míssil 
é de 10 unidades 
 Klingons 
Vulcanos Criar um Manter o 
novo míssil status quo 
Criar um novo 
míssil 
(-10,-10) (10,100) 
Manter o status 
quo 
(-100,10) (0,0) 
 
 
P6 Dois restaurantes Hot Dog King e Hot Dog 
Chef pretendem determinar seus orçamentos para 
publicidade para o próximo ano. Os dois 
restaurantes terão vendas conjuntas 240 milhões 
de dólares e podem gastar 6 ou 10 milhões em 
publicidade. Se um restaurante gastar mais 
dinheiro que o outro, então o restaurante que 
gasta mais dinheiro era vendas de 190 milhões de 
dólares. Se ambos os restaurantes gastam a 
mesma quantidade em publicidades, então terão 
vendas iguais. Cada dólar em vendas produz 10 
centavos em ganhos. Suponha que cada restaurante 
está interessado em maximizar os lucros. Encontre 
o ponto de equilíbrio para este jogo.
 
P7 Um estudo realizado em 1986 no mercado 
norte-americano de refrigerantes sabor cola 
identificou curvas de elasticidade-demanda e 
custos-marginais para a Coca-Cola e a 
Pepsi-Cola. Para q a quantidade vendida (em milhões 
de caixas) e p o preço praticado (em US$ de 1986), o 
estudo identificou as seguintes relações entre os 
produtos: 
pepsicocacoca p2p463q 
 
cocapepsicoca pp550q 
 
Além disso, o estudo sugeriu que o custo marginal da 
Coca é de U$5/caixa e da Pepsi é de US$4/caixa. 
Construa a matriz de ganhos e resolva o problema 
para as duas empresas. 
 
P8 Dois jogadores de tênis são A e B. O jogador A 
tem duas estratégias: “Alto” e “Baixo”. Já o jogador B 
tem duas estratégias: “Esquerda” e “Direita”. A 
tabela a seguir mostra as recompensas, para cada 
jogador, de cada uma das quatro possíveis 
combinações estratégicas é a matriz de ganhos. 
Quais as estratégias a serem utilizados pelos 
jogadores? 
 Jogador B 
J
o
g
a
d
o
r 
A
 
 Esquerda Direita 
Alto 
 
(3,9) (1,8) 
 
Baixo 
(0,0) (2,1) 
 
 
P9 O chefe de uma empresa de computação 
desconfia que seu operador de computadores está 
Profº Túlio de Almeida 
Pesquisa Operacional II 
 
usando o tempo de serviço para “bater papo” na 
internet. Se o operador trabalha corretamente, ele 
gasta g em esforço e produz um lucro bruto de v 
unidades. O chefe, por sua vez, pode fiscalizar ou não 
o trabalho do operador. Fiscalizar custa h unidades 
para a empresa. 
Se o operador for pego “batendo papo” na internet, ele 
perde o seu salário de w unidades. Para limitar o 
número de casos a considerar, vamos assumir que v > 
w > g > h > 0. Os dois jogadores escolhem suas 
estratégias simultaneamente. 
 
P10 O governo deseja vacinar seus cidadãos contra 
um certo vírus da gripe. Este vírus possui dois 
sorotipos, sendo que é desconhecida a proporção na 
qual os dois sorotipos ocorrem na população do vírus. 
Foram desenvolvidas duas vacinas onde a eficácia da 
vacina 1 é de 85% contra o sorotipo 1 e de 70% contra 
o sorotipo 2. A eficácia da vacina 2 é de 60% contra o 
sorotipo 1 e de 90% contra o sorotipo 2. Qual política 
de vacinação deveria ser tomada pelo governo?
 
DESAFIOS 
 
D1 Considere uma vila, onde cada um dos n fazendeiros tem a opção de manter ou não sua ovelha no pasto. A 
utilidade do leite e da lã de uma ovelha pastando é igual a 1, por outro lado, esta ovelha no pasto contribui com um 
dano ambiental (compartilhado por todos os fazendeiros) de 5 unidades. 
Cada fazendeiro tem duas estratégias: manter ou não manter sua ovelha no pasto. Defina 
 




pasto no ovelha sua mantém não fazendeiro ésimo-i o se 0,
pasto no ovelha sua mantém fazendeiro ésimo-i o se , 1
x i
 
Em termos destas variáveis, é fácil de ver que a utilidade ui do i-ésimo fazendeiro é dada por 
n
)x...x(
.5x)x,...,x(u n1in1i


 
Se n>5, manter todas as ovelhas no pasto, isto ´e, tomar x1 = ··· = xn =1,é o único equilíbrio de Nash do jogo. De fato: 
se todas as ovelhas estão no pasto e um fazendeiro resolve tirar sua ovelha, ele deixa de ganhar 1 (proveniente da 
utilidade da lã e do leite) e deixa de perder 5/n < 1(proveniente do dano ambiental), isto é, ele acaba ganhando 
menos do que se tivesse mantido sua ovelha no pasto. Assim, todos terminar˜ ao mantendo sua ovelha e a utilidade 
final de cada fazendeiro será igual −4, com prejuízo ambiental máximo. 
Para amenizar esta situação, a teoria dos jogos sugere a cobrança de um imposto por danos ambientais. Se o i-
ésimo fazendeiro deve pagar um imposto de t unidades por manter sua ovelha no pasto, então sua utilidade final será 
dada por 
n
)x...x(
.5txx)x,...,x(u n1iin1i


 
Para o problema em questão, faça: 
a. A matriz para a tragédia dos comuns para n = 6 e t = 0 
b. A matriz para a tragédia dos comuns para n = 6 e t = 5 
c. A matriz para a tragédia dos comuns para n = 6 e t = 1/6