03 TEORIA DOS JOGOS

Prévia do material em texto

Profº Túlio de Almeida 
Pesquisa Operacional II 
 
3. TEORIA DOS JOGOS 
A vida é repleta de conflitos e competição. Pode-se citar vários exemplos onde há adversários em conflito, como 
jogos de tabuleiro, batalhas/operações militares, campanhas políticas, merchandising entre outras coisas. 
Garrincha: O senhor já combinou com os russos? 
Ele não sabia, mas estava raciocinando com a Teoria dos Jogos 
Conta a lenda que na Copa de 1958, durante a preleção antes do jogo contra a antiga União Soviética, o técnico 
brasileiro Vicente Feola reuniu os jogadores e combinou a estratégia da partida. Segundo Nelson Correa, foi algo 
assim: 
 
No meio de campo, Nilson Santos, Zito 
e Didi trocariam passes curtos para 
atrair a atenção dos russos… Vavá 
puxaria a marcação da defesa deles 
caindo para o lado esquerdo do 
campo… Depois da troca de passes no 
meio do campo, repentinamente a bola 
seria lançada por Nilton Santos nas costas do marcador de 
Garrincha. Garrincha venceria facilmente seu marcador na 
corrida e com a bola dominada iria até à área do adversário, 
sempre pela direita, e ao chegar à linha de fundo cruzaria a 
bola na direção da marca de pênalti; Mazzola viria de frente 
em grande velocidade já sabendo onde a bola seria 
lançada… e faria o gol! Garrincha com a camisa jogada no 
ombro, ouvia sem muito interesse a preleção, e em sua 
natural simplicidade perguntou ao técnico: Tá legal, seu 
Feola… mas o senhor já combinou tudo isso com os russos? 
Luis Nassif lembrou bem que "uma das características de 
qualquer ser humano racional, cartesiano, é a capacidade de 
prever as consequências de um lance jogado. Até Garrincha, 
gênio do futebol e escasso em raciocínio, entendia que não 
existe tática eficiente se não se prever qual será a reação do 
adversário. O famoso “já combinaram com os russos” é um 
monumento à boa lógica". 
 
Bem vindo ao mundo da Teoria dos Jogos. Garrincha não foi nada ingênuo. Elaborar uma estratégia significa pensar 
todas as suas opções considerando as reações do seu adversário. A ciência e arte da Teoria dos Jogos está em 
oferecer algumas ferramentas formais para antecipar o movimento do outro jogador. Como exemplo, uma dos 
principais conceitos é "coloque-se na posição do adversário e veja o que você faria se fosse ele". 
 
3.1. A TEORIA DOS JOGOS PROPRIAMENTE 
DITA 
 
A Teoria dos Jogos trata de situações de decisão nas 
quais dois oponentes inteligentes, cujos objetivos são 
conflitantes, estão tentando superar o outro. Como 
exemplos típicos, pode-se citar o lançamento de 
campanhas publicitárias para produtos concorrentes e 
planejamento de estratégicas para exércitos em 
guerra. 
 
3.1.1. O Início da Teoria dos Jogos 
Registros antigos sobre teoria dos 
jogos remontam ao século XVIII. 
Em correspondência dirigida a 
Nicolas Bernoulli, James 
Waldegrave analisa um jogo de 
cartas chamado “le Her” e fornece 
uma solução que é um equilíbrio 
de estratégia mista. Contudo, 
Waldegrave não estendeu sua 
abordagem para uma teoria geral. No início do século 
XIX, temos o famoso trabalho de Augustin Cournot 
sobre duopólio. 
Em 1913, Ernst Zermelo publicou 
o primeiro teorema matemático da 
teoria dos jogos, o teorema afirma 
que o jogo de xadrez é 
estritamente determinado, isto é, 
em cada estágio do jogo pelo 
menos um dos jogadores tem uma 
estratégia em mão que lhe dará a 
vitória ou conduzirá o jogo ao 
empate. 
Outro grande matemático que se interessou em jogos 
foi Emile Borel, que reinventou as soluções minimax e 
publicou quatro artigos sobre jogos estratégicos. Ele 
achava que a guerra e a economia podiam se 
estudadas de uma maneira semelhante. 
Em seu início, a teoria dos jogos 
chamou pouca atenção. O grande 
matemático John von Neumann 
mudou esta situação. Em 1928, ele 
demonstrou que todo jogo finito de 
soma zero com duas pessoas possui 
uma solução em estratégias mistas. 
Profº Túlio de Almeida 
Pesquisa Operacional II 
 
A demonstração original usava topologia e análise 
funcional e era muito complicada de se acompanhar. 
Em 1937, ele forneceu uma nova demonstração 
baseada no teorema do ponto fixo de Brouwer. John 
von Neumann, que trabalhava em muitas áreas da 
ciência, mostrou interesse em economia e, junto com 
o economista Oscar Morgenstern, publicou o clássico 
“The Theory of Games and Economic Behaviour” em 
1944 e, com isto, a teoria dos jogos invadiu a 
economia e a matemática aplicada. 
Em 1950, o matemático 
John Forbes Nash Junior 
publicou quatro artigos 
importantes para a teoria 
dos jogos não-cooperativos 
e para a teoria de barganha. 
Em “Equilibrium Points in n-
Person Games” e “Non-cooperative Games” , Nash 
provou a existência de um equilíbrio de estratégias 
mistas para jogos não-cooperativos, denominado 
equilíbrio de Nash, e sugeriu uma abordagem de 
estudo de jogos cooperativos a partir de sua redução 
para a forma não-cooperativa. Nos artigos “The 
Bargaining Problem” e “Two-Person Cooperative 
Games”, ele criou a teoria de barganha e provou a 
existência de solução para o problema da barganha 
de Nash. 
Em 1994, John Forbes Nash Jr. (Universidade de 
Princeton), John Harsanyi Universidade de Berkeley, 
California) e Reinhard Selten (Universidade de Bonn, 
Alemanha) receberam o prêmio Nobel por suas 
contribuições para a Teoria dos Jogos. 
 
3.1.2. Conceitos Fundamentais 
 
Jogo 
 
Situação de competição entre N pessoas ou grupos 
com objetivos em conflito, que possuem um conjunto 
de regras conhecido com ganhos conhecidos. 
Oponentes 
Jogadores 
Lance 
Atividades elementares de um jogo, cada jogador 
pode realizar lances diferentes, mas cada conhece os 
lances disponíveis dos outros. 
Alternativas 
Estratégias que indicam a sequencia de lances e 
contra-lances que o jogador fará durante o jogo 
completo. 
 
3.2. JOGOS DE SOMA ZERO 
 
3.2.1. Conceitos Fundamentais 
 
Como a raiz dos jogos é o conflito de interesses, a 
solução ótima seleciona uma ou mais estratégias para 
cada jogador de modo que qualquer alteração nas 
estratégias escolhidas não beneficie o retorno para 
qualquer um dos jogadores. Estas soluções podem 
estar na forma de uma única estratégia pura ou de 
várias estratégias mistas, de acordo com 
probabilidades específicas. Em geral, um jogo de 
soma zero possui as seguintes características: 
 Estratégias do Jogador 1; 
 Estratégias do Jogador 2; 
 Matriz de Ganho (Payoffs) 
Observação: O jogo de soma zero, nada mais é que 
um jogo onde se um jogador ganha o outro perde. 
Matriz de Ganhos 
 
Caracteriza o jogo, mostrando os ganhos de cada 
jogador de acordo com a estratégia adotada. 
 
 Jogador B 
Estratégias B1 B2 
J
o
g
a
d
o
r 
A
 
A1 v(A1;B1) v(A1;B2) 
A2 v(A2;B1) v(A2;B2) 
 
3.2.2. Modelo em Programação Linear 
 
Para o Jogador A 
 
As probabilidades ótimas para o jogador A, xi, onde i = 
1,2,3,...,m podem ser determinadas resolvendo o 
seguinte problema: 
 
Profº Túlio de Almeida 
Pesquisa Operacional II 
 
0x
1x...xxx
.a.s
xa,...,xa,xaMinMax
i
m321
m
1i
m
1i
iin
m
1i
i2ii1iiy j














 
 
 
 
Observação: O Problema não é linear! Como pode ser 
feita a linearização. (Programação Não-Linear) 
 
irrestrito v
m,...,3,2,1i
0x
1x...xxx
vxa
vxa
vxa
.a.s
vMax
i
m321
m
1i
iin
m
1i
i2i
m
1i
i1i
x i













 
 
Parao Jogador B 
 
As probabilidades ótimas para o jogador B, yj, onde j = 
1,2,3,...,n podem ser determinadas resolvendo o 
seguinte problema: 
 
0y
1y...yyy
.a.s
xa,...,xa,yaMaxMin
j
n321
n
1j
n
1i
jjm
n
1j
j2jj1jjx i


















 
 
 
 
Observação: O Problema não é linear! Como pode ser 
feita a linearização. (Programação Não-Linear) 
 
 
irrestrito v
m,...,3,2,1j
0y
1y...yyy
vya
vya
vya
.a.s
vMin
j
n321
n
1j
jjm
n
1j
j2j
n
1j
j1j
y j













 
 
Observação: O PPL do jogador B é o dual do PPL do 
jogador A. 
 
3.2.3. Jogos Estáveis ou Jogos de Estratégia 
Pura 
 
Em jogos de estratégia pura, parte-se do princípio que 
os jogadores usaram apenas UMA estratégia simples. 
Adota-se a abordagem pessimistas para ambos os 
jogadores. 
 
Critério MaxMin 
 
Utilizado para o jogador A, tal critério usará de uma 
abordagem pessimista pelo ponto de vista do ganho. 
Logo, a melhor decisão para o jogador A será o 
melhor (máximo) valor dentre os piores (mínimo). 
 
Critério MiniMax 
 
Utilizado para o jogador B, tal critério usará de uma 
abordagem pessimista pelo ponto de vista do perda. 
Logo, a melhor decisão para o jogador A será o 
mínimo valor dentre os maiores. 
 
Observação: Fique atento às características do 
problema, para entender o sentido de otimização 
(maximizar ou minimizar). Por exemplo: lucro, receita, 
custo etc. 
 
Exemplos 
 
Duas empresas A e B, vendem duas marcas de 
medicamento para gripe. A empresa A anuncia em 
rádio (A1), televisão (A2) e jornais (A3). A empresa B, 
Profº Túlio de Almeida 
Pesquisa Operacional II 
 
além de usar rádio (B1), televisão (B2) e jornais (B3), 
também envia folhetos (B4), por mala direta. 
Dependendo da efetividade de cada campanha 
publicitária, uma empresa pode capturar uma parte da 
fatia de mercado (market share) da outra. A matriz a 
seguir resume a porcentagem de mercado capturada 
ou perdida pela empresa A. 
 
 B1 B2 B3 B4 
A1 8% -2% 9% -3% 
A2 6% 5% 6% 8% 
A3 -2% 4% -9% 5% 
 
3.2.4. Jogos Instáveis ou Jogos de Estratégia 
Mista 
No caso de jogos de estratégia mista, o valor ótimo 
ocorre em algum lugar entre os valores maximin e 
minimax do jogo. Jogos de estratégia mista podem ser 
resolvidos por meio de gráficos ou programação 
linear. 
 
Método Gráfico de Solução 
 
O método é interessante porque explica a ideia de 
sela por meio de gráficos. 
 
O retorno esperado de A correspondente a j-ésima 
estratégia pura de B é calculado por: 
 
  
j21j2j1jx axaaminmax i 
 
 
O retorno esperado de B correspondente a i-ésima 
estratégia pura de A é calculado por: 
 
  i21i2i1iy bybbmaxmin j 
 
 
Exemplo: 
 
Considere o seguinte jogo 2x4. O retorno é para o 
jogador A. 
 
 B1 B2 B3 B4 
A1 2 2 3 -1 
A2 4 3 2 6 
 
O jogo não possui nenhuma estratégia pura de 
solução. 
 
Estratégia pura de B Retorno esperado de A 
1 
2 
3 
4 
-2x1 + 4 
-x1 + 3 
x1 + 2 
-7x1 + 6 
 
 
O máximo dos mínimos se dá na intersecção das 
estratégias B3 e B4. Logo, a solução se dará da 
seguinte forma: 
 
50,0
2
1
x
4x8
6x72x
1
1
11



 
O jogador A deve aplicar 50% das vezes a estratégia 
A1 e 50% a estratégia A2. 
Como para a estratégia B, deve-se escolher entre as 
alternativas B3 e B4, então: 
 
 B3 B4 
A1 3 -1 
A2 2 6 
 
Como o jogo não possui nenhuma estratégia pura de 
solução 
 
Estratégia pura de A Retorno esperado de B 
1 
2 
4y1 -1 
-4x1 + 6 
 
Profº Túlio de Almeida 
Pesquisa Operacional II 
 
 
A solução se dá pela intersecção das retas. 
 
875,0
8
7
x
7y8
6y41y4
1
1
11



 
O jogador B deve optar pela estratégia B3 87,5% das 
vezes e optar pela estratégia B4 12,5% das vezes. 
 
 
3.3. JOGOS DE SOMA NÃO CONSTANTE 
 
Os jogos de soma não constantes são aqueles onde 
não se permite cooperação. Determina-se um ponto 
de equilíbrio onde nenhum dos jogadores possa se 
beneficiar por uma mudança unilateral nas estratégias. 
 
3.3.1. O Dilema dos Prisioneiros 
 
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. 
 
“Dois ladrões, Al e Bob, são capturados e acusados 
de um mesmo crime. Presos em selas separadas, 
sem poderem 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 ambos confessarem, ambos 
terão uma 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.” 
 
 Bob 
confessar negar 
Al 
confessar (-5, -5) (0,-10) 
negar (-10,0) (-1,-1) 
 
Em termos da teoria dos jogos, dizemos que os dois 
jogadores possuem uma estratégia dominante, isto é, 
todas menos uma estratégia é estritamente dominada, 
que o jogo é resolvível por dominância estrita iterada 
e que o jogo termina em uma solução o que é um 
equilíbrio de estratégia dominante. 
Contextualizando ... 
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. 
 Mulher 
futebol cinema 
Homem 
futebol (10, 5) (0, 0) 
cinema (0, 0) (5,10) 
 
3.3.2. Dominância 
Estratégia Pura Estritamente Dominada 
Uma estratégia pura sik ∈ Si do jogador gi ∈ G é 
estritamente dominada pela estratégia sik ∈ Si se 
)s,s(u)s,'s(u iikiiiki  
 
para todo s−i ∈ S−i. A estratégia sik ∈ Si é fracamente 
dominada pela estratégia sik ∈ Si se 
)s,s(u)s,'s(u iikiiiki  
 
para todos−i ∈ S−i 
Observação: Dominância estrita iterada nada mais é 
do que um processo onde se eliminam as estratégias 
que são estritamente dominadas. 
Exemplo: 
 
Considere o jogo determinado pela matriz de payoffs a 
seguir. 
 
24232221 ssss
 
 












)8,4()2,0()3,1()5,9(
)1,5()1,1()2,2()0,7(
)1,1()1,2()2,3()0,0(
)4,0()4,1()6,2()2,5(
s
s
s
s
14
13
12
11
 
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. 
Profº Túlio de Almeida 
Pesquisa Operacional II 
 
 
242322 sss
 
 












)8,4()2,0()3,1(
)1,5()1,1()2,2(
)1,1()1,2()3,2(
)4,0()4,1()6,2(
s
s
s
s
14
13
12
11
 
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 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. Obtém-se então uma matriz reduzida 
2×2. 
 
2422 ss





)1,5()2,2(
)1,1()2,3(
s
s
13
12
 
E pelo método da dominância, observa-se que a 
melhor estratégia está nos valores (3,2). 
 
3.3.3. Solução Estratégica ou Equilíbrio de Nash 
Uma solução estratégica ou equilíbrio de Nash de um 
jogo é um ponto onde cada jogador não tem incentivo 
de mudar sua estratégia se os demais jogadores não 
o fizerem. 
 
Definição Matemática 
 
Dizemos que um perfil de estratégia 
 
S)s,...,s,s,s,s(s *n
*
1i
*
i
*
1i
*
1
*  
 
 
é um equilíbrio de Nash se 
 
)s,s(u)s,s(u *i
*
iji
*
i
*
ii  
 
 
para todo i=1,...,n e para todo ji =1,..., mi, com mi ≥ 2 
 
Características 
 
1. É uma jogada para a qual uma estratégia é a 
melhor resposta à outra. 
2. Cada estratégia é a melhor resposta possível 
às estratégias dos demais jogadores e isso é 
verdade para todos os jogadores. 
3. Jogos Estáveis: 
Maximin = Minimax = Equilíbrio de Nash 
4. Jogos Instáveis: 
O jogador muda a estratégia como resposta a 
estratégia do outro, ou seja, uso de estratégia 
mista para obter o Equilíbrio de Nash. 
 
Conclusão: Equilíbrio de Nash = Ponto de Equilíbrio 
dos Jogos de Soma Zero. 
 
3.4. BIBLIOGRAFIA E REFERÊNCIAS 
[1] TAHA, Hamdy. Pesquisa Operacional. 8ª Edição. 
São Paulo: Pearson Prentice Hall, 2008. 
[2] HILLIER, Frederick S. & LIEBERMAN, Gerald J. 
Introduction to Operations Research. 7th Edition. 
McGraw Hill. 2001. 
[3] MEZA, Lidia Angulo. Teoria dos Jogos (Parte 1). 
Universidade Federal Fluminense. Disciplina: 
Pesquisa Operacional II. 32 slides. 2010. 
[4] MEZA, Lidia Angulo. Teoria dos Jogos (Parte 2). 
Universidade Federal Fluminense. Disciplina: 
Pesquisa Operacional II. 32 slides. 2010. 
[5] SARTINI, Brígida Alexandre; GARBUGIO, Gilmar; 
BORTOLOSSI, Humberto José; SANTOS, Polyana 
Alves & BARRETO, Larissa Santana. Uma 
Introdução à Teoria dos Jogos. Universidade 
Federal da Bahia. II Bienal da SBM. 2004 
[6] BARRICHELLO, Fernando. Site Ciência da 
Estratégia. www.cienciadaestrategia.com.br. 
Acessado em setembro de 2017. 
[7] NASSIF, Luis. Blog do Luis Nassif On-Line. 
www.advivo.com.br. Acessado em setembro de 2017.