Teoria dos Jogos
Profa Ana Carla Bittencourt Reis
1
TEORIA DOS JOGOS
“A teoria dos jogos é uma teoria matemática que trata das características
gerais de situações competitivas de maneira formal e abstrata”
Fonte: Hillier e Lieberman, 2010
Jogos entre dois participantes de soma zero: um jogador ganha,
independentemente de quanto o outro perca, de forma que as somas de suas
vitórias líquidas seja zero
Um jogo entre dois participantes é caracterizado por:
1. As estratégias do jogador 1
2. As estratégias do jogador 2
3. A tabela de prêmios
Maio/2010
Profa Ana Carla Bittencourt Reis
2
TEORIA DOS JOGOS
JOGADOR 2
ESTRATÉGIA 1
ESTRATÉGIA 2
ESTRATÉGIA 1
1
-1
ESTRATÉGIA 2
-1
1
JOGADOR 1
 Antes de começas o jogo, cada jogador conhece as estratégias de que
dispõe, as do oponente, e a tabela de prêmios;
 O jogo em si consiste em cada jogador escolher sua estratégia sem
conhecer a escolha do oponente;
Maio/2010
Profa Ana Carla Bittencourt Reis
3
TEORIA DOS JOGOS
 Em jogos mais complexos (envolvendo uma série de jogadas), uma
estratégia é uma regra pré-determinada que especifica completamente
como alguém pretende responder a cada possível circunstância em cada
estágio do jogo;
 A tabela de prêmios mostra o ganho (positivo ou negativo) para o jogador
1 que resultaria de cada combinação de estratégias para os dois
jogadores;

Maio/2010
Profa Ana Carla Bittencourt Reis
4
TEORIA DOS JOGOS
Hipóteses fundamentais:
1) Os jogadores são racionais
2) Os jogadores escolhem suas estratégias única e exclusivamente para seu
próprio benefício
Teoria dos jogos X Análise de decisão
Oponente passivo (estados da natureza)
Oponente ativo
Maio/2010
Profa Ana Carla Bittencourt Reis
5
TEORIA DOS JOGOS
Dois políticos estão disputando entre si uma cadeira no senado. Os planos de
campanha precisam ser feitos agora para os dois dias finais, cruciais para o
fechamento a eleição. Consequentemente, ambos os políticos querem gastar estes
dias fazendo campanha em duas cidades-chave, B e M. Para evitar desperdício de
tempo de campanha, eles pretendem viajar à 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 da campanha do seu oponente até ele ter
terminado sua própria programação. Consequentemente, cada político solicitou aos
seus coordenadores de campanha, em cada uma destas 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 pelo seu oponente.
Depois disso ele deseja usar estas informações para escolher a melhor estratégia
sobre o emprego destes dois dias.
Maio/2010
Profa Ana Carla Bittencourt Reis
6
TEORIA DOS JOGOS
Formulação na forma de um jogo entre dois participantes de soma zero
Cada jogador tem 3 estratégias:
Estratégia 1: passar um dia em cada cidade
Estratégia 2: passar ambos os dias em B
Estratégia 3: passar ambos os dias em M
Jogador 2
Maio/2010
Estratégia 1
Estratégia 2
Estratégia 3
Estratégia 1
1
2
4
Jogador 1 Estratégia 2
1
0
5
Estratégia 3
0
1
-1
Profa Ana Carla Bittencourt Reis
7
TEORIA DOS JOGOS
CONCEITO DE ESTRATÉGIAS DOMINADAS: uma estratégia é dominada por
outra se esta sempre for pelo menos tão boa quanto a primeira (e algumas vezes
melhor), independentemente do que faz o oponente. Uma estratégia dominada
pode ser eliminada imediatamente de considerações ulteriores.
Jogador 2
Estratégia 1
Jogador 1 Estratégia 2
Estratégia 3
Estratégia 1
Estratégia 2
Estratégia 3
1
2
4
1
0
5
0
1
-1
O jogador 2
não possui
estratégia
dominada!
Jogador 2
Jogador 1
Maio/2010
Estratégia 1
Estratégia 2
Estratégia 3
Estratégia 1
1
2
4
Estratégia 2
1
0
5
Profa Ana Carla Bittencourt Reis
8
TEORIA DOS JOGOS
Jogador 2
Jogador 1
Estratégia 1
Estratégia 2
Estratégia 3
Estratégia 1
1
2
4
Estratégia 2
1
0
5
As estratégias
1e2
representam
menores
perdas para o
jogador 2
Jogador 2
Jogador 1
Maio/2010
Estratégia 1
Estratégia 2
Estratégia 1
1
2
Estratégia 2
1
0
Profa Ana Carla Bittencourt Reis
9
TEORIA DOS JOGOS
Jogador 2
Jogador 1
Estratégia 1
Estratégia 2
Estratégia 1
1
2
Estratégia 2
1
0
Jogador 2
Jogador 1
Estratégia 1
Estratégia 1
Estratégia 2
1
2
Jogador 2
Jogador 1
Maio/2010
Estratégia 1
Estratégia 1
Estratégia 2
1
2
Profa Ana Carla Bittencourt Reis
10
TEORIA DOS JOGOS
Jogador 2
Jogador 1
Estratégia 1
Estratégia 1
Estratégia 2
1
2
Jogador 2
Jogador 1
Estratégia 1
Estratégia 1
Estratégia 2
1
2
Jogador 2
Estratégia 1
Jogador 1
Estratégia 1
1
Ambos os jogadores devem selecionar suas estratégias 1.
O jogador 1 receberá um prêmio igual a 1 do jogador 2, isto é, o político 1 ganhará
1000 votos do político 2.
O PRÊMIO PARA O JOGADOR 1 QDO AMBOS JOGAM DE FORMA ÓTIMA É O CHAMADO
VALOR DO JOGO
Maio/2010
Profa Ana Carla Bittencourt Reis
11
TEORIA DOS JOGOS
Variante 2 do Exemplo:
Este jogo não possui estratégias dominadas. O que fazer?
Ponto de sela:
-min na linha
-max na coluna
Minimizar suas perdas máximas
Jogador 2
Mínimo:
Estratégia 1
Estratégia 2
Estratégia 3
Estratégia 1
-3
-2
6
-3
Jogador 1 Estratégia 2
2
0
2
0
Estratégia 3
5
-2
-4
-4
Máximo:
5
0
6
Minmax
Solução estável
Estas escolhas partem do
pressuposto de que os
jogadores sejam avessos a
grandes perdas
Maio/2010
Maxmin
Profa Ana Carla Bittencourt Reis
O prêmio resultante tem
valor igual a zero, portanto,
este é um jogo limpo
12
TEORIA DOS JOGOS
Variante 3 do Exemplo:
Este jogo não possui ponto de sela. O que fazer?
É necessário escolher entre as estratégias aceitáveis, considerando algum
tipo de aleatoriedade
Jogador 2
Estratégia 3* Mínimo:
Estratégia 1
Estratégia 2
Estratégia 1
0
-2
2
-2
Jogador 1 Estratégia 2
5
4
-3
-3
Estratégia 3
2
3
-4
-4
Máximo:
5
4
Minmax
2
Solução instável
Maxmin
Maio/2010
Profa Ana Carla Bittencourt Reis
13