Teoria dos Jogos - UFJF

1 Modelagem e Simula o - Teoria dos Jogos Teoria dos Jogos 1. Introdu o A Teoria dos Jogos devida principalmente aos trabalhos desenvolvidos por von Neumann e John Nash. John von Neumann (*1903, Budapeste, Hungria; 1957, John Forbes Nash (*1928, Bluefield, West Washington, Estados Unidos). Virgina, Estados Unidos). A Teoria dos Jogos trata com situa es de tomada de decis o em que dois ou mais oponentes possuem objetivos conflitantes. Exemplos t picos s o: 1. Campanhas publicit rias para produtos concorrentes. 2. Planejamento de estrat gias de guerra para ex rcitos inimigos. Em um jogo, dois oponentes (jogadores) podem ter um n mero finito ou infinito de alternativas ou estrat gias. Associado com cada par de estrat gias h um valor de pagamento (payoff) que um jogador paga para seu oponente. Estes Jogos s o conhecidos como Jogos de Soma Zero e Dois Jogadores porque o ganho de um jogador igual . perda do outro.

2 Com os conceitos citados acima, o jogo pode ser resumido em termos dos payoff para um nico jogador, uma vez que os payoff podem ser positivos (ganhar e o oponente perder) e negativos (perder e o oponente ganhar). Adotando os dois jogadores como A e B com m e n estrat gias, respectivamente, o jogo pode ser representado por uma matriz de payoff para o jogador A como: Notas de Aula - Fernando Nogueira 1. Modelagem e Simula o - Teoria dos Jogos B1 B2 .. Bn A1 p11 p12 .. p1m A2 p21 p22 .. p2m : : : : : Am pm1 pm2 .. pmn A representa o matricial acima indica que se A usa uma estrat gia i e B usa uma estrat gia j, o payoff para A pij e conseq entemente o payoff para B -pij. Exemplo 1: A matriz de payoff de um jogo de "par ou impar" para o jogador A que apostou em "par" dada por: B1 B2. o o n par de dedos n impar de dedos A1 no par de dedos 1 -1. A2 no impar de dedos -1 1. A matriz acima mostra que se o jogador A colocar um n mero par de dedos (estrat gia A1) e o jogador B colocar tamb m um n mero par de dedos (estrat gia B1), o jogador A ir ganhar 1, pois o jogador A apostou em par.

3 Se o jogador A colocar um n mero par de dedos (estrat gia A1) e o jogador B. colocar um n mero impar de dedos (estrat gia B2), o jogador A ir ganhar -1, ou seja, A ir . perder e B ir ganhar. 2. Solu o tima de Jogos de Soma Zero e Dois Jogadores A solu o tima de um Jogo de Soma Zero e Dois Jogadores seleciona uma ou mais estrat gias para cada jogador tal que qualquer mudan a em uma estrat gia escolhida n o melhora o payoff para o outro jogador. Estas solu es podem estar na forma de uma nica estrat gia ou v rias estrat gias misturas de acordo com probabilidades pr -determinadas. Exemplo 2: Duas companhias, A e B, vendem duas marcas de vacina para gripe. Companhia A pode anunciar o seu produto no r dio (estrat gia A1), na televis o (estrat gia A2) ou no jornal (estrat gia A3). A Companhia B pode anunciar o seu produto no r dio (estrat gia B1), na televis o (estrat gia B2), no jornal (estrat gia B3) ou mala direta (estrat gia B4).

4 Dependendo da criatividade e da intensidade dos an ncios, cada companhia pode ganhar uma por o do mercado da outra companhia. A matriz de payoff abaixo resume a porcentagem de mercado ganho ou perdido pela companhia A. B1 B2 B3 B4 Min Linha A1 8 -2 9 -3 -3. A2 6 5 6 8 5 Maximin A3 -2 4 -9 5 -9. Max Coluna 8 5 9 8. Minimax Notas de Aula - Fernando Nogueira 2. Modelagem e Simula o - Teoria dos Jogos A solu o do jogo baseada no princ pio da "Melhor entre as Piores". Se a companhia A escolher a estrat gia A1, ent o, independente da estrat gia que B escolha, o pior que pode acontecer A perder 3% do seu mercado para B. Isto representado pelo valor m nimo dos elementos da matriz na linha 1. Similarmente, se A escolher a estrat gia A2, o pior que pode acontecer A ganhar 5% do mercado de B, e se A escolher a estrat gia A3, o pior que pode acontecer A perder 9% do seu mercado para B. Estes resultados s o listados na coluna "Min Linha" da matriz.

5 Para obter a "Melhor entre as Piores", a companhia A escolhe a estrat gia A2 por que esta representa o valor m ximo entre os valores m nimos (Maximin). Uma vez que a matriz de payoff para A, o crit rio "Melhor entre as Piores" para as estrat gias da companhia B requer determinar o valor m nimo entre os valores m ximos (Minimax). A solu o tima do jogo ent o seleciona as estrat gias A2 e B2, isto , ambas as companhias devem anunciar seus produtos na televis o. O payoff ser a favor da companhia A, porque seu mercado ir ganhar 5% do mercado de B. Neste caso, dito que o valor do jogo 5 (5%) e que A e B est o usando uma Estrat gia Pura ou Estrat gia Dominante cuja solu o um ponto de sela. A solu o de ponto de sela garante que nenhuma companhia est tentando selecionar uma estrat gia melhor. Se B escolher outra estrat gia (B1, B3 ou B4), a companhia A pode ficar com a estrat gia A2, a qual garante que B ir perder mais mercado para A (6% ou 8%).

6 D mesma forma, A n o quer usar uma estrat gia diferente (A1 ou A3). uma vez que se A escolher a estrat gia A3, B pode escolher a estrat gia B3 e ganhar 9% do mercado de A. O racioc nio an logo verdadeiro para A escolher a estrat gia A1. Exemplo 3: Dois pol ticos A e B, est o em campanha concorrendo a uma vaga de senador. necess rio fazer o planejamento para os dois dias finais da campanha. Os dois pol ticos pretendem gastar estes dois dias finais em duas cidades: S o Paulo e Rio de Janeiro. Cada pol tico pode gastar um dia em cada cidade ou ent o gastar dois dias em S o Paulo ou dois dias no Rio de Janeiro. Resumindo, as estrat gias ficam: A1 = pol tico A gastar um dia em S o Paulo e um dia no Rio de Janeiro A2 = pol tico A gastar dois dias em S o Paulo A3 = pol tico A gastar dois dias no Rio de Janeiro B1 = pol tico B gastar um dia em S o Paulo e um dia no Rio de Janeiro B2 = pol tico B gastar dois dias em S o Paulo B3 = pol tico B gastar dois dias no Rio de Janeiro A matriz de payoff abaixo resume o n mero (em milhares) de votos ganhos (valores positivos) ou perdidos (valores negativos) para o pol tico A.

7 B1 B2 B3 Min Linha A1 0 -2 2 -2 Maximin A2 5 4 -3 -3. A3 2 3 -4 -4. Max Coluna 5 4 2. Minimax Notas de Aula - Fernando Nogueira 3. Modelagem e Simula o - Teoria dos Jogos Ao contr rio do exemplo anterior, o valor Maximin (-2) diferente do valor Minimax (2), portanto, n o existe uma solu o de Ponto de Sela, conseq entemente n o existe uma Estrat gia Dominante. Este fato facilmente verificado: para o pol tico A, a melhor estrat gia (a que ele perder menos votos) independente da estrat gia utilizada pelo pol tico B a estrat gia A1 (gastar um dia em cada cidade) e com isso perder 2 mil votos na pior das hip teses. No entanto, a melhor estrat gia para o pol tico B a estrat gia B3 (gastar dois dias no Rio de Janeiro) e com isso perder 2 mil votos na pior das hip teses. Por m, as estrat gias A1 e B3 resultam em um ganho de 2 mil votos para o pol tico A e conseq entemente uma perda de 2 mil votos para o pol tico B.

8 Como o pol tico B racional, ele pode antecipar este resultado e mudar sua estrat gia para B2 (A est com estrat gia A1) ganhando ent o 2 mil votos. Prevendo isto, o pol tico A pode mudar sua estrat gia para A2 (B est com estrat gia B2) ganhando assim, 4. mil votos. Dando continuidade a an lise, o pol tico B ent o pode mudar sua estrat gia para B3 (A est com estrat gia A2) ganhar 3 mil votos. Ent o, A pode mudar sua estrat gia novamente para A1 (B est com estrat gia B3) e ent o ganhar 2 mil votos. Nota-se neste instante que a estrat gia inicial foi retomada, configurando assim um ciclo. Para Jogos onde o valor Maximin diferente do valor Minimax a solu o dita Inst vel e portanto, n o h uma Estrat gia Dominante. De fato, o que acontece com Jogos que n o possuem Estrat gia Dominante que sempre quando a estrat gia de um jogador previs vel, o seu oponente poder tomar vantagem desta informa o para melhorar a sua tomada de decis o.

9 Com isso, uma caracter stica essencial para um planejamento racional de um jogo deste tipo que nenhum jogador deveria estar habilitado a deduzir a estrat gia que o seu oponente ir usar. Portanto, neste caso, ao inv s de aplicar algum crit rio conhecido para determinar uma nica estrat gia que ser definitivamente usada, faz-se necess rio escolher estrat gias alternativas aceit veis geradas sobre algum tipo de base rand mica. Pode-se afirmar ent o, que o valor v deste jogo estar entre o valor Maximin v e Minimax v . Isto : v v v (1). 3. Jogos com Estrat gias Mistas Toda vez que um jogo n o possuir uma solu o em um ponto de sela, faz-se necess rio designar uma distribui o de probabilidade sobre cada conjunto de estrat gias. Matematicamente, fica: xi = probabilidade do jogador A usar a estrat gia i (i = 1,2,..,m) (2). yj = probabilidade do jogador B usar a estrat gia j (j = 1,2,..,n) (3). onde: m e n s o os n meros de estrat gias do jogador A e B, respectivamente.

10 Assim, o jogador A deve especificar seu plano de jogo designando valores para x1, x2,.., xm e o jogador B designando valores para y1, y2,.., yn. Como xi e yj s o medidas de Notas de Aula - Fernando Nogueira 4. Modelagem e Simula o - Teoria dos Jogos probabilidade estas vari veis devem ser obrigatoriamente n o-negativas e as suas m n somat rias xi =1 e i=1. y j=1. j = 1. Os planos (x1, x2, .., xm) e (y1, y2,.., yn) s o denominados Estrat gias Mistas. Exemplo 4: A mesma matriz de payoff para o exemplo 3 com estrat gias mistas (x 1 , x 2 , x 3 ) = (1 2 , 1 2 ,0) e (y1 , y 2 , y 3 ) = (0, 1 2 , 1 2 ) . 1 1. B2: y2 = B3: y3 =. B1: y 1 = 0 2 2. A1: x1 =. 1 0 -2 2. 2. A2: x2 =. 1 5 4 -3. 2. A3: x3 = 0 2 3 -4. Estes planos significam que o jogador A est dando uma chance igual (com probabilidade 1 2 ) de escolher a estrat gia pura A1 ou A2, por m descartando a estrat gia A3. D mesma forma o jogador B est dando uma chance igual (com probabilidade 1 2 ) de escolher a estrat gia pura B2 ou B3, por m descartando a estrat gia B1.