Apostila de Teoria dos Jogos

Prévia do material em texto

Pesquisa Operacional – Teoria dos Jogos
Prof. M.Sc. Renato Resende Borges
Teoria dos Jogos
Introdução
	Os modelos de decisão podem ser considerados como um procedimento de tomada de decisão em situações não competitivas, no sentido de não envolver diretamente outras pessoas ou organizações. Os estados ou os cenários que irão acontecer envolvem riscos ou incertezas referentes à previsão do mercado, influência do clima, etc. O tomador de decisão escolhe uma das alternativas de decisão existentes. O decisor tem conhecimento dos cenários possíveis e dos riscos embutidos nesses cenários.
	Uma situação competitiva ou de conflito acontece quando um estado ou cenário ocorre causado pela decisão tomada por outro participante. A análise dos problemas de decisão em situações nas quais existem conflitos é efetuada pela Teoria dos Jogos que foi formulada por Von Neumann (Prêmio Nobel) e Morgenstern em 1935.
Jogo entre duas pessoas com ganhos iguais (ou jogo de soma zero)
	Um jogo é formado pelos seguintes elementos:
Jogadores: Dois jogadores tentam decidir, a seu favor, um jogo em que todas as alternativas de decisão, denominadas estratégias, são previamente conhecidas e representadas por meio de uma matriz.
Estratégias: As linhas da matriz contêm as estratégias ou possíveis alternativas de decisão do jogador I, enquanto as colunas contêm as estratégias do jogador II. Existem m alternativas possíveis para o jogador I e n para o jogador II.
Nota: Os dois jogadores podem ter também o mesmo número de estratégias.
Resultados ou ganhos (payoffs) do jogo: Estão representados pelos valores 
de uma matriz. Se um jogador ganha o que o outro perde, isto é, 
Ganho do jogador I = - Ganho do jogador II
ou, 
, temos um Jogo de duas pessoas com soma zero (Two Persons zero sum game), pois 
.
Forma Genérica da Matriz de Ganhos
 Jogador II
Jogador I 
Exemplo: Para um jogo com m = n = 4, temos: 
Métodos para resolver um jogo: As estratégias puras
Critério Maxmin
	O objetivo do jogador I é maximizar seus ganhos mínimos. Dessa forma o jogador I deve escolher os menores ganhos em cada linha e depois o maior ganho entre eles, ou seja: Ganho do jogador I: Maxmin 
Critério Minmax
	O objetivo do jogador II é minimizar suas perdas máximas. Dessa forma o jogador II escolhe as maiores perdas em cada coluna e depois a menor perda entre eles, ou seja: Ganho do Jogador II: Minmax
Jogo estável ou estritamente determinado: O valor do jogo
	Um jogo de duas pessoas é chamado estável ou estritamente determinado se e apenas se o menor valor do ganho nas linhas da matriz de resultados corresponder ao maior ganho encontrado nas colunas da matriz. Esse ponto é chamado ponto de equilíbrio ou ponto de sela (saddle point), e o valor encontrado é o valor do jogo, ou seja:
Para o exemplo abaixo, temos:
			 Jogador II Min
Jogador I 
 
 Maxmin = 2
 Max 3 2 3 3 
 Minmax = 2
Logo o valor jogo é v = 2. 
	Quando um jogo não possui ponto de sela, dizemos que ele não é estável ou não é estritamente determinado. 
Estratégias Mistas
	Num jogo não estritamente determinado, não existe uma estratégia nitidamente ótima que possa ser consistentemente usada por qualquer jogador e, além disso, o uso consistente de qualquer estratégia particular por qualquer um dos jogadores pode ser aproveitado pelo outro jogador. Assim , existe uma importante diferença entre jogos estritamente determinados e não estritamente determinados: Num jogo estritamente determinado, existe uma estratégia ótima para cada jogador e não são necessárias “medidas de segurança”. Num jogo não estritamente determinado, o jogo ótimo deve impedir que o oponente venha a saber que estratégia será usada num dado jogo. Isto é efetuado selecionando-se ao acaso a estratégia a ser usada em cada jogo, de acordo com as probabilidades que podem ser computadas a partir da matriz de jogo. Tal estratégia, que consiste de uma mistura de probabilidades de mais de uma estratégia (pura), é denominada uma estratégia mista.
Exemplo:
Seja o seguinte jogo que não é estável (não possui ponto de sela)
					Jogador II	
 Jogador I 
John Von Neumann provou que, mesmo o jogo que não possui ponto de sela definido por uma estratégia pura, pode ser analisado para chegar-se a uma estratégia ótima por meio de um procedimento bem definido, ou seja, é possível determinar os valores das probabilidades 
para o jogador I e as probabilidades 
 para o jogador II, e determinar o valor do jogo. Para o jogo acima, temos:
Ganho esperado para o jogador I se o jogador II decidir usar a estratégia 1:
 1 2
 
�� EMBED Equation.3 
Ganho I.1 = 
Ganho I.2 = 
O jogador I espera maximizar o ganho esperado. É possível mostrar que isso ocorre no ponto de interseção das retas representados pelos dois ganhos (verificaremos isso na resolução de um jogo através do método gráfico), isto é, para o valor de 
quando: 
o que nos dá após os cálculos 
 e 
.
Assim, a melhor estratégia para o jogador I é utilizar as probabilidades 
, ou seja, 
para a linha (estratégia) 1 e 
 para a linha (estratégia) 2.
Exercício para o lar: Determinar as estratégias mistas para o jogador II.
Valor espertado do jogo não estável
	
	O valor de um jogo é o mesmo tanto para os jogos estáveis e não estáveis: o valor do jogo é o pagamento que um jogador pode esperar obter por jogo. Esse valor é obtido substituindo as probabilidades encontradas 
em qualquer um dos ganhos esperados de ambos os jogadores. No exemplo anterior, o valor do jogo é: 
�� EMBED Equation.3 , ou ainda, 
.
Dominância
	
Numa matriz de jogo m x n, diz-se que a linha i majora ou domina a linha h, se todo o elemento na i for maior ou igual do que o elemento correspondente na linha h. Analogamente, diz-se que uma coluna j minora ou é dominada pela coluna k se todo elemento da coluna j for menor ou igual que o elemento correspondente na coluna k. De maneira simplificada podemos caracterizar da seguinte maneira:
- linhas dominadas caem
- colunas dominantes caem
Exemplo 1: Dado o jogo
 
 
 
 subjogo restante
	Devemos comparar cada uma das estratégias entre si, duas a duas (linhas e colunas). Esse jogo não possui dominância entre as colunas. Comparando a estratégia 1 e a estratégia 3, podemos observar que na est.1 o jogador I pode ganhar 2 ou 5 (se o jogador II usar a est.1 ou 2, respectivamente) e na est.3 poderá ganhar 3 ou 6. Como o objetivo do jogador I é maximizar seus ganhos, ele escolhe usar a est.3 pois o retorno será maior. Devido a essa escolha, omitimos a est. 1 do jogador I. Da mesma forma, procedemos assim com as outras estratégias até esgotarmos todos os casos de dominância. 
	Este jogo não possui um ponto de sela. (Para o lar: resolva o jogo)
Exemplo 2: Dado o jogo 
 
 
 
O jogo acima não possui dominância nas linhas. Utilizando um raciocínio análogo ao exemplo 1 para as colunas, obtemos o subjogo restante. Vale lembrar aqui, que o objetivo do jogador II é minimizar suas perdas.
Este jogo não possui um ponto de sela pode ser resolvido pela técnica de tentativa e erro e pelo método gráfico. Trataremos apenas da solução gráfica, que é mais vantajosa.
Solução Gráfica
	
	A solução de um jogo 2 x n ou n x 2 é determinada como segue. 
1º passo: Aplique o critério de dominância;
2º passo: Desenhe os pares de pagamentos das n estratégias do jogador com 2 estratégias em dois eixos verticais e ligue ospares de pontos por retas.
3º passo: Observe o jogador que possui duas estratégias. Se for o jogador I, o seu objetivo é maxmin. Se for o jogador II, o objetivo é minmax.
Exemplo 1: Dado o jogo 	
Devemos constatar que o jogo é resolvido sempre para o jogador que possui duas estratégias. Os pagamentos esperados para o jogador I se o jogador II usar:
Est.1: 
 Est.2: 
 Est.3: 
Est.4: 
E representando graficamente, temos:
 
	Observando a figura, podemos notar que o ponto maximin ocorre com as interseções de quaisquer das retas 2, 3 e 4, tomadas duas a duas, e que 
 e ainda que 
.
	Seguindo com a solução do jogo, utilizaremos a combinação (2, 3) para descobrimos as probabilidades 
e 
. Dessa forma, o subjogo restante será:
 
 
 
 
O pagamento esperado para o jogador II se o jogador usar:
Est. 1: 
Est. 2: 
Logo 
 
 
 e 
.
O valor do jogo será 
.
Maxmin = Minmax = ponto de sela = v = valor do jogo
�PAGE �
�PAGE �4�
_1090412528.unknown
_1090672267.unknown
_1090846042.unknown
_1090846332.unknown
_1090846673.unknown
_1130655643.unknown
_1130655695.unknown
_1090846735.unknown
_1090847097.unknown
_1090846717.unknown
_1090846601.unknown
_1090846631.unknown
_1090846388.unknown
_1090846220.unknown
_1090846243.unknown
_1090846082.unknown
_1090846148.unknown
_1090675460.unknown
_1090845880.unknown
_1090845917.unknown
_1090675487.unknown
_1090675413.unknown
_1090675440.unknown
_1090675240.unknown
_1090670563.unknown
_1090671126.unknown
_1090671672.unknown
_1090670578.unknown
_1090412645.unknown
_1090412702.unknown
_1090412637.unknown
_1090410866.unknown
_1090411741.unknown
_1090411832.unknown
_1090411883.unknown
_1090411802.unknown
_1090411612.unknown
_1090411727.unknown
_1090411311.unknown
_1090411591.unknown
_1090410932.unknown
_1090410427.unknown
_1090410519.unknown
_1090410658.unknown
_1090410482.unknown
_1090410394.unknown
_1090410422.unknown
_1090395132.unknown