Teoria dos Jogos - SOL - Professor



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 [pic]de uma matriz. Se um jogador ganha o que o outro perde, isto é,

Ganho do jogador I = - Ganho do jogador II

ou, [pic], temos um Jogo de duas pessoas com soma zero (Two Persons zero sum game), pois [pic].

Forma Genérica da Matriz de Ganhos

Jogador II

Jogador I [pic]

Exemplo: Para um jogo com m = n = 4, temos: [pic]

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 [pic] [pic] Maxmin = 2

Max 3 2 3 3 [pic]

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 [pic]

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 [pic]para o jogador I e as probabilidades [pic] 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

[pic][pic]

Ganho I.1 = [pic]

Ganho I.2 = [pic]

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 [pic]quando:

[pic]

o que nos dá após os cálculos [pic] e [pic].

Assim, a melhor estratégia para o jogador I é utilizar as probabilidades [pic], ou seja, [pic]para a linha (estratégia) 1 e [pic] 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 [pic]em qualquer um dos ganhos esperados de ambos os jogadores. No exemplo anterior, o valor do jogo é: [pic][pic], ou ainda, [pic].

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

[pic] [pic] [pic] 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

[pic] [pic] [pic]

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 os pares 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 [pic]

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: [pic]

Est.2: [pic]

Est.3: [pic]

Est.4: [pic]

E representando graficamente, temos:

[pic]

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 [pic] e ainda que [pic].

Seguindo com a solução do jogo, utilizaremos a combinação (2, 3) para descobrimos as probabilidades [pic]e [pic]. Dessa forma, o subjogo restante será:

[pic] [pic]

[pic]

O pagamento esperado para o jogador II se o jogador usar:

Est. 1: [pic]

Est. 2: [pic]

Logo [pic] [pic] [pic] e [pic].

O valor do jogo será [pic].

-----------------------

Maxmin = Minmax = ponto de sela = v = valor do jogo

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download