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.

2 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. 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.

3 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. Se o jogador A colocar um n mero par de dedos (estrat gia A1) e o jogador B.

4 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).

5 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). 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.

6 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. 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.

7 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%). 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.

8 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.

9 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.

10 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. 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.