Aula 2 - Teoria dos jogos - Processos estocásticos

Prévia do material em texto

TEORIA DOS JOGOS
Prof.: Me. Octávio Torres
O QUE É
• A teoria dos jogos é uma teoria matemática que trata das 
características gerais de situações competitivas, de maneira formal e 
abstrata.
• Tem aplicação em grande variedade de áreas, entre elas engenharia, 
administração e economia.
JOHN NASH
Em 1994 John Nash, John 
Harsanyi e Reinhard Selton 
ganharam o premio Nobel de 
Ciências Econômicas. Eles 
realizaram a análise dos 
equilíbrios na teoria dos 
jogos não cooperativos.
(A história é recontada no filme Uma 
mente Brilhante)
NESTA AULA VAMOS APRENDER
1. Formulação de jogos de dois participantes
2. Resolução de jogos pelo critério das estratégias dominadas
3. Resolução de jogos pelo critério do Minimax
4. Resolução de jogos pelo critério das Estratégias Mistas
CARACTERÍSTICAS BÁSICAS DE UM JOGO
• Todo jogo entre dois participantes é caracterizado por:
1. As estratégias do jogador 1
2. As estratégias do jogador II
3. A tabela de prêmios
CRITÉRIOS RACIONAIS
• Um objetivo primário da teoria dos jogos é o desenvolvimento de 
critérios racionais para a seleção de uma estratégia. Duas hipóteses 
fundamentais são feitas:
1. Ambos os jogadores são racionais
2. Ambos os jogadores escolhem suas estratégias única e 
exclusivamente para promover seu próprio bem estar 
(sem compaixão pelo oponente)
PAR OU IMPAR
• Para ilustrar as características básicas dos jogos de dois participantes 
considere o jogo par ou impar. Este jogo consiste simplesmente em 
cada um dos participantes mostrar simultaneamente um ou dois dedos. 
Se o número de dedos for igual (soma par) o jogador 1 ganha a aposta 
e, se for diferente (soma impar) o jogador 2 ganha a aposta. Suponha 
que quem perder deve pagar R$1 ao ganhador.
CARACTERÍSTICAS DO PAR OU IMPAR
• Neste jogo, ambos os jogadores têm as mesmas estratégias: mostrar 
um ou dois dedos. E a tabela de prêmios é a que segue:
• Observe que a tabela de prêmios mostra apenas o ganho (positivo ou 
negativo) para o jogador 1, pois a tabela para o jogador 2 é exatamente 
o negativo desta.
Jogador 2
Jogador 1
1 2
1 1 -1
2 -1 1
RESOLUÇÃO DE JOGOS
EXEMPLO PROTÓTIPO
Dois políticos disputam entre si uma cadeira no Senado. Os planos de •
campanha precisam ser feitos agora para os dois dias finais, que devem ser 
cruciais em razão do fechamento da campanha eleitoral. Consequentemente, 
ambos os políticos querem gastar esses dias fazendo campanha em duas 
cidades-chave, Bigtown e Megalo ́polis. Para evitar desperdício de tempo de 
campanha, eles pretendem viajar a ̀ noite e passar um dia inteiro em cada 
cidade ou, então, dois dias inteiros em apenas uma das cidades. Entretanto, 
já ́ que os preparativos necessários precisam ser feitos com antecedência, 
nenhum dos políticos saberá ́ da programação de campanha de seu oponente 
ate ́ ele ter terminado sua própria programação. 
EXEMPLO PROTÓTIPO
Consequentemente, cada politico solicitou a seus coordenadores de •
campanha em cada uma dessas duas cidades para avaliar qual seria o 
impacto (em termos de votos ganhos ou perdidos) das diversas 
combinações possíveis de dias passados lá́ por ele próprio e por seu 
oponente. Depois disso, ele deseja usar essas informações para 
escolher a melhor estratégia sobre o emprego desses dois dias.
CARACTERÍSTICA DO JOGO
• Neste jogo podemos identificar:
a) Os jogadores são Político 1 (P1) e Político 2 (P2)
b) Cada um dispõe de três estratégias:
1. Passar um dia em cada cidade
2. Passar ambos os dias em Bigtown
3. Passar ambos os dias em Megalópolis
TABELA DE PRÊMIOS
Considere que os coordenadores de campanha realizaram uma •
pesquisa e estimara qual seria a quantidade de votos ganhos ou 
perdidos para cada combinação de estratégias. Os resultados são 
apresentados na tabela de prêmios abaixo:
Estratégia
Jogador 2
1 2 3
Jogador 1
1 1 2 4
2 1 0 5
3 0 1 -1
ESTRATÉGIAS DOMINADAS
É a maneira mais simples de resolver jogos de dois participantes, •
entretanto, nem sempre pode ser aplicada.
Consiste em descartar uma sucessão de estratégias inferiores até que •
reste somente uma escolha.
Dizemos que: • “Uma estratégia é dominada por uma segunda estratégia se 
esta sempre for pelo menos tão boa quanto a primeira (e algumas vezes 
melhor), independente do que faz o oponente. Uma estratégia dominada 
pode ser eliminada imediatamente.”
EXEMPLO
Estratégia
Jogador 2
1 2 3
Jogador 1
1 1 2 4
2 1 0 5
3 0 1 -1
Ou seja, a melhor combinação de estratégias para este jogo seria P1 E1 e P2 
E1. Ambos devem passar um dia em cada cidade e, o político 2 perderá 1.000 
votos para o político 1.
TABELA DE PRÊMIOS 2
• Para prosseguirmos considere que a tabela de prêmios fosse a seguinte:
• Observe que este jogo não pode ser resolvido pelo método das 
estratégias dominadas (nenhuma estratégia é dominada).
Estratégia
Jogador 2
1 2 3
Jogador 1
1 -3 -2 6
2 2 0 2
3 5 -2 -4
MINIMAX
O critério do • Minimax, é um critério padrão proposto pela teoria dos 
jogos para a seleção de uma estratégia. 
De acordo com este critério • cada jogador deve jogar de tal maneira a 
minimizar suas perdas máximas toda vez que a escolha da estratégia 
resultante não puder ser explorada pelo oponente para então 
melhorar sua própria posição.
MINIMAX
Em termos de tabela de prêmios, isso implica que o • jogador 1 deveria 
selecionar uma estratégia cujo prêmio mínimo seja o maior, ao passo 
que o jogador 2 deveria escolher aquela cujo prêmio máximo para o 
jogador 1 fosse o menor possível.
EXEMPLO: MINIMAX
Máximo 5 0 6
Estratégia
Jogador 2
1 2 3
Jogador 1
1 -3 -2 6
2 2 0 2
3 5 -2 -4
Mínimo
-3
0
-4
Valor 
Minimax
Valor 
Maximin
OBSERVAÇÕES SOBRE O RESULTADO
• Do resultado anterior podemos conservar que:
1. O premio resultante da melhor estratégia é 0, logo o valor do jogo é 
0.
2. Isto implica que este pode ser considerado um jogo limpo
3. A solução do jogo é considerada Estável, dado que apresentou um 
ponto de sela. Quer dizer, quando o Minimax e o Maximin se 
encontram dizemos que o jogo apresenta uma solução de equilíbrio
TABELA DE PRÊMIOS 3
• Para prosseguirmos considere que a tabela de prêmios fosse a seguinte:
Estratégia
Jogador 2
1 2 3
Jogador 1
1 0 -2 2
2 5 4 -3
3 2 3 -4
TABELA DE PRÊMIOS 3
• Observe que a tabela não apresenta estratégias dominadas e, que os 
valores Minimax e Maximin não se encontram.
Estratégia
Jogador 2
1 2 3
Jogador 1
1 0 -2 2
2 5 4 -3
3 2 3 -4
Máximo 5 4 2
Mínimo
-2
-3
-4
Valor Minimax
Valor 
Maximin
OBSERVAÇÕES SOBRE O RESULTADO
• Do resultado anterior concluímos que:
1. Não existe ponto de sela
2. A solução obtida pelo Minimax é uma solução instável
3. É necessário encontrar uma nova solução para este jogo.
Veremos que a melhor solução para este jogo é escolher as estratégias 
de maneira aleatória, se tornando imprevisível para seu oponente.
PAR OU IMPAR
• Observe pela tabela de prêmios do jogo de par ou impar que, este jogo 
não apresenta solução pelo critério das estratégias dominadas e nem 
pelo critério do Minimax.
• Neste caso, a melhor opção para solucionar este jogo é escolher as 
estratégias de maneira aleatória, sendo imprevisível ao seu oponente.
(para tornar aleatórias as escolhas das estratégias você poderia lançar uma moeda e dependendo 
do resultado mostra um dedo ou dois)
EXERCÍCIOS
Q1
Para um jogo com a seguinte tabela de prêmios, determine a estratégia •
ótima para cada jogador eliminando sucessivamente as estratégias 
dominadas. Indique a ordem na qual você eliminou as estratégias.Qual 
é o valor do Jogo? O Jogo pode ser considerado um jogo limpo?
ESTRATÉGIA
JOGADOR 2
1 2 3
JOGADOR 1
1 -3 1 2
2 1 2 1
3 1 0 -2
Q2
Considere um jogo com a seguinte tabela de prêmios. Determine a 
estratégia ótima para cada jogador eliminando sucessivamente estratégias 
dominadas. Forneça uma lista das estratégias dominadas (e as estratégias 
dominantes correspondentes) na ordem em que você foi capaz de 
eliminá-las. Qual o valor do Jogo? O jogo pode ser considerado um Jogo 
Limpo? 
ESTRATÉGIA
JOGADOR 2
1 2 3 4
JOGADOR 1
1 5 -7 -2 2
2 -2 2 -5 5
3 -2 5 -2 7
Q3
Considere um jogo com a seguinte tabela de prêmios. Determine a •
estratégia ótima para cada jogador utilizando o critério do minimax. 
Este jogo possui um ponto de sela? Este jogo é estável? Qual é o valor 
do jogo? O jogo pode ser considerado um jogo limpo?
ESTRATÉGIA
JOGADOR 2
1 2 3
JOGADOR 1
1 3 -1 3
2 -3 1 7
3 7 3 5
Q4
Considere um jogo com a seguinte tabela de prêmios. Determine a •
estratégia ótima para cada jogador utilizando o critério do minimax. 
Este jogo possui um ponto de sela? Este jogo é estável? Qual é o valor 
do jogo? O jogo pode ser considerado um jogo limpo?
ESTRATÉGIA
JOGADOR 2
1 2 3 4
JOGADOR 
1
1 3 -3 -2 -4
2 -4 -2 -1 1
3 1 -1 2 0
Q5
Para o jogo representado na tabela abaixo responda: a) é possível •
resolvê-lo pelo método das estratégias dominadas? Por quê? b) é 
possível resolvê-lo pelo critério do minimax? Por quê? Caso as 
respostas anteriores for “não”, qual seria então o método adequado 
para resolver este problema? Por quê? Apresente a solução.
ESTRATÉGIA
JOGADOR 2
1 2 3
JOGADOR 1
1 4 3 1
2 0 1 2
Q6
• Duas empresas compartilham a maior parte do mercado para determinado tipo de 
produto. Cada uma delas está elaborando seus novos planos de marketing para o próximo 
ano na tentativa de tirar parte das vendas do concorrente. As vendas totais para o produto 
são relativamente fixas, de modo que uma empresa possa aumentar suas vendas somente 
tirando-as da outra. Cada empresa considera três POSSIBILIDADES: 1) embalagens 
melhores para o produto, 2) aumento na propaganda e, 3) uma ligeira redução de preço. 
Os custos das três alternativas são bastante comparáveis e suficientemente grandes para 
que cada empresa selecione apenas uma. O efeito estimado de cada combinação de 
alternativas sobre o aumento percentual nas vendas para a empresa 1 é apresentado na 
tabela abaixo. Qual a melhor estratégia? Por que? 
Empresa 2
1 2 3
Empresa 1
1 2 3 1
2 1 4 0
3 3 -2 -1
ESTRATÉGIAS MISTAS
SOLUÇÃO ALTERNATIVA
Identificar as estratégias aceitáveis e escolher aleatoriamente qual será usada, •
evitando então que o seu oponente preveja qual estratégia você irá adotar.
No exemplo apresentado suponha que o político • 1 atribua as probabilidades 
x1, x2 e x3 respectivamente para as estratégias 1, 2 e 3. Esse conjunto de 
probabilidades recebe o nome de Estratégias Mistas. Enquanto as 
estratégias originais (1, 2 e 3) são chamadas Estratégias Puras.
TEOREMA DO MINIMAX:
Se forem permitidas estratégias mistas, o par de estratégias mistas que •
é ótimo de acordo com o critério do Minimax fornece uma solução 
estável com 𝑣 = 𝑣 = 𝑣(𝑣𝑎𝑙𝑜𝑟 𝑑𝑜 𝑗𝑜𝑔𝑜), de maneira que nenhum dos 
jogadores pode se dar melhor mudando unilateralmente sua estratégia.
OBJETIVO
• Encontrar a distribuição de probabilidades que maximiza o valor do 
prêmio esperado mínimo (𝑣), garantindo que 𝑣 = ҧ𝑣 = 𝑣 (𝑣𝑎𝑙𝑜𝑟 𝑑𝑜 𝐽𝑜𝑔𝑜).
• O método para encontrar a estratégia mista ótima é a Programação Linear. 
A estratégia mista será ótima se:
RESOLVENDO COM SOLVER
RESOLVENDO O EXEMPLO DA ELEIÇÃO
Como vimos anteriormente a situação • 3 do exemplo da campanha 
eleitoral não pode ser resolvido por Estratégias Dominadas nem por 
Minimax, vamos resolver por estratégias mistas.
Estratégia
Jogador 2
1 2 3
Jogador 1
1 0 -2 2
2 5 4 -3
3 2 3 -4
RESULTADO COM SOLVER
Estratégia
Jogador 2
1 2 3 xi
Jogador 1
1 0 -2 2 0,6
2 5 4 -3 0,4
3 2 3 -4 0
soma pij*xi 1,8 0,2 0,2 1
Valor do jogo 0,18182
CAMPANHA ELEITORAL
• Encontrar a Estratégia mista ótima para o jogo abaixo:
EXERCÍCIO 2
• Encontrar a Estratégia mista ótima para o jogo abaixo:
EXERCÍCIO 3
• Encontrar a Estratégia mista ótima para o jogo abaixo: