APLICAÇÃO DE ÁLGEBRA LINEAR EM JOGOS DE ESTRATÉGIA

Prévia do material em texto

APLICAÇÃO DE ÁLGEBRA LINEAR EM JOGOS DE ESTRATÉGIA
INTRODUÇÃO 
A Teoria dos jogos basicamente é a parte da matemática, que compreende a tomada de decisões em jogos estratégicos. A teoria dos jogos se tornou proeminente e atualmente é um importante campo de estudo do ramo matemático, tendo aplicações em diversos áreas como economia, ciência da computação, ciência política, filosofia, psicologia.
Para um jogo de estratégia é necessário a existência de alguns elementos fundamentais, como jogadores, movimentos que estes podem tomar e o lucro dos mesmos. As interações e as situações de conflito, podem ser consideradas como jogos e as pessoas envolvidas nesses acontecimentos são chamados de jogadores. 
Para introduzir o conceito básico de teoria de jogos, numa primeira aplicação considerando os dois jogadores que competiam sem a utilização de estratégias, como em um jogo que contém duas roletas na qual os movimentos de seus ponteiros giram de forma aleatória. A segunda aplicação é um de dois jogadores jogadas, pré-determinadas, sem a possibilidade de alteração da jogada, o ganho de um significa a perda do outro, chamada de “soma zero”. Conclui-se que a aplicação final foi a técnica que era impossível de ser definida pelo outro jogador, o uso de matriz de compensação que permitia que os jogadores ligassem a mais adequada técnica independente do outro, pressionando uma “compensação esperada”.
2. OBJETIVOS 
Definição de alguns conceitos Algébricos e enunciados de alguns teoremas relacionados à aplicação de álgebra linear visando a teoria dos jogos de estratégia.
Estudo de três casos hipotético, onde a álgebra linear é aplicada em jogos estratégicos e determinar a estratégia ótima para verificar as possibilidades dos ganhadores.
3. METODOLOGIA
A metodologia da pesquisa utilizada foi com base bibliográfica, e em artigos científicos. Trata-se de uma pesquisa bibliográfica e aplicada, desenvolvida com material já elaborado, constituído principalmente de livros e artigos científicos. Inicialmente foi pesquisado algumas aplicações de álgebra linear no contexto de jogos, tanto em livros como também artigos científicos, após isso chegou-se a três exemplos que servirá para ilustrar a aplicação da algebra linear nos jogos estratégicos.
4. APLICAÇÃO DE ÁLGEBRA LINEAR EM JOGOS DE ESTRATÉGIA 
Vamos tomar como base um jogo genérico para argumentar a respeito da aplicação de álgebra linear em jogos de estratégia, em que dois competidores adotam estratégias distintas para atingir objetivos opostos. Em determinados casos, a melhor estratégia encontrada é com a utilização das técnicas matriciais. Sendo que a multiplicação de matrizes e os conceitos básicos de probabilidade são pré-requisitos primordiais.
Para inserir os conceitos básicos da teoria de jogos, levamos em conta um jogo que pode ser visto em parques de diversões, onde duas pessoas estão de acordo em jogar. Suponhamos que integrantes do jogo sejam o jogador L e o jogador C, e que cada participante tenha uma roda estacionária com ponteiro móvel fixado em seu centro, como mostra a figura 1. A roda do jogador L é chamada de roda das linhas, onde é dividida em três setores, numerados 1, 2 e 3 e a roda do jogador C é denominada de roda das colunas, dividida em quatro setores , numerados 1, 2, 3 e 4. As frações de áreas ocupadas pelos diferentes setores estão indicadas na figura 1. Para iniciar o jogo, cada jogador gira o ponteiro de sua roda, pondo-o em movimento até parar aleatoriamente. O número do setor de cada roda é denominado o movimento do jogador. Dessa forma, o jogador L dispõe de três movimentos possíveis e o jogador C tem quatro movimentos possíveis. Dependendo do movimento feito por cada jogador, o jogador C faz um pagamento em dinheiro ao jogador L de acordo com a tabela 1. 
Figura 1: Roda das linhas do jogador L e Roda das colunas do jogador C. 
Tabela 1: Pagamentos ao jogador L
	Por exemplo, se o ponteiro da roda das Linhas parar no Setor 1 ( o jogador L fez o movimento 1) E o ponteiro da roda das colunas parar no Setor 2 ( o jogador C fez o movimento 2), então o jogador C deve pagar $5,00 ao jogador L. Algumas das entradas nesta tabela são negativas, indicando que o jogador C faz um pagamento negativo ao jogador L. Sendo assim o jogador L faz um pagamento positivo ao jogador C. Por Exemplo, se a roda das linhas mostrar 2 e a roda das colunas mostrar 4, então o jogador L paga ao jogador C a quantia de $4,00, pois a entrada correspondente na tabela é $-4,00. Dessa maneira, as entradas positivas na tabela são os ganhos do jogador L e as perdas do jogador C, e as entradas negativas na tabela são os ganhos dos jogadores C e as perdas do jogador L.
	Nesse jogo, os jogadores não tem controle sobre seus movimentos, pois cada movimento é determinado pela sorte. Contudo, cada jogador pode decidir se ele quer ou não jogar, então caso decida jogar, ele pode ganhar ou perder ao longo do jogo. 
	O jogo que acabamos de descrever é um exemplo de um jogo matrizes de duas pessoas com soma zero. O termo “soma zero” significa que a cada vez que é jogado, o ganho positivo de um jogador é igual ao ganho negativo (perda) do outro jogador. Ou seja, a soma dos dois ganhos é zero. O termo “jogo de matriz” é usado para retratar um jogo de duas pessoas no qual cada jogador tem somente um número finito de movimentos, de modo que todos os possíveis resultados de cada jogada, e os correspondentes ganhos nos jogadores, podem ser arranjados em formato tabular ou matricial como na tabela 1.
	Em um jogo arbitrário desse tipo, seja m o número de movimentos possíveis do jogador L e seja n o número de possíveis movimentos do jogador C. Num lance desse jogo, cada jogador faz um de seus movimentos possíveis e, então, é feita uma compensação do jogador C para o jogador L dependendo dos movimentos. Sendo i = 1, 2, . . . , m e j =1, 2, …, n, escrevemos
	compensação do jogador C para o jogador L, se jogador L 
fizer o movimento i e o jogador C o movimento j 
Essa Compensação não precisa ser em dinheiro, mas qualquer espécie de bens de consumo ao qual possamos associar um valor numérico. Como antes, se uma entrada for negativa, isso significa que o jogador C recebe do jogador L uma compensação de . Arranjamos essas mn compensações possíveis no formato de uma matriz m x n a qual nos referimos como matriz de compensação ou matriz de pagamento do jogo.
Cada jogador deve fazer seus movimentos numa base probabilística. Por exemplo, para o jogo discutido na introdução, a razão da área de um setor para área da roda seria a probabilidade de que o jogador faz o movimento correspondente àquele setor. Assim pela figura 1 dizemos que o jogador L faz o movimento 2 com probabilidade e o jogador C faz o movimento 2 com probabilidade . Em geral usamos as definições seguintes:
Probabilidade de que o jogador L faz o movimento i (i= 1,2,...,m)
	Probabilidade de que o jogador C faz o movimento j (j= 1,2,...,n)
Segue dessas definições que
p1 + p2 + … + pm =1
q1 + q2 + … + qn = 1
Com as probabilidades e , formamos os dois vetores
Dizemos que o vetor linha p é a estratégia do jogador L e o vetor coluna q, a estratégia do jogador C. Por exemplo pela figura 1 temos Para o jogo de parque de diversões descrito acima. 
Pela Teoria de Probabilidades, se for a probabilidade do jogador L fazer o movimento i e, independentemente, for a probabilidade dos jogadores C fazer o movimento j , então será a probabilidade de num lance qualquer do jogo, o jogador L fazer o movimento i e o jogador C fazer o movimento j. A compensação para o jogador L para um tal de movimento é . Multiplicando cada possível compensação pela correspondente probabilidade e somando sobre todas as pontuações possíveis, obtemos a expressão: 
 (1)
A equação (1) é uma média ponderada das compensações para o jogador L; cada compensação é ponderada de acordo com a probabilidade de sua ocorrência. Na Teoriade Probabilidades, essa média ponderada é denominada compensação esperada para o jogador L. Pode ser mostrado que, se o jogo for jogado muitas vezes, a compensação média por jogada para o jogador L, é dada por essa expressão. Denotamos essa compensação esperada por E(p,q), para enfatizar que depende das estratégias de ambos os jogadores. Pela definição da Matriz de compensação A e das estratégias p e q , pode ser verificado que podemos expressar a compensação esperada em notação matricial como:
Como E(p,q) é a compensação esperada para o jogador L, segue que -E(p,q) é a compensação esperada para o jogador C.
EXEMPLO 1. Compensação esperada para o jogador L
Para o jogo de parque de diversões descrito acima, temos:
Assim, a longo termo, o jogador L pode esperar receber uma média de 18 centavos do jogador C a cada jogada do jogo.
 Até aqui, discutimos a situação em que cada jogador tem uma estratégia pré-determinada. Agora discutimos a situação mais difícil e que ambos os jogadores podem mudar suas estratégias independentemente. Por exemplo, no jogo descrito logo no início, permitindo a ambos jogadores alteraram as áreas dos setores e de suas rodas e, assim, controlar as probabilidades e seus respectivos movimentos. Isso muda qualitativamente a natureza do problema e nos coloca firmemente na verdadeira teoria dos jogos. Fica entendido que nenhum dos dois jogadores conhece a estratégia que o outro irá escolher. Cada jogador vai fazer a melhor escolha possível de estratégia e que o outro jogador sabe disso. Assim, o jogador L tenta escolher uma estratégia p tal que E(q,p) seja a menor possível para melhor estratégia P que o jogador ele possa decidir para ver que essas escolhas são realmente possíveis, precisamos do teorema, denominado O Teorema Fundamental dos jogos de duas pessoas com soma zero, adiante provamos esse teorema no caso de jogos estritamente determinados e jogos de matrizes 2 x 2.
TEOREMA 1: Teorema Fundamental dos jogos com soma zero
As estratégias p* e q* desse teorema são as melhores estratégias para os jogadores L e C, respectivamente. Para ver isso, escrevemos u =E (p*,q*). A Desigualdade do lado esquerdo da equação 3 então diz que:
Isso significa que, se o jogador L escolher a estratégia p*, não interessando qual a estratégia que o jogador C escolher, a compensação esperada para o jogador L nunca será menor do quê u. Além disso, não é possível para um jogador L alcançar uma compensação esperada maior do que u. Para ver isso, suponha que exista alguma estratégia p** que o jogador L posso escolher de tal modo que:
Então, em particular,
contradizendo a desigualdade do lado direito da equação 3, que pede: 
Consequentemente, o melhor que o jogador L pode fazer é impedir que a sua compensação esperada caia abaixo do valor u. De maneira análoga, o melhor que o jogador C pode ficar e garantir que a sua compensação esperada tenha pelo menos o valor u, o que pode ser alcançado com a estratégia q*. Assim, chegamos as definições seguintes:
 
O fraseado nessa definição sugere que as estratégias não são necessariamente únicas. Isso realmente ocorre e no, exercício 2, temos uma prova. Contudo, pode ser demonstrado que quaisquer dois pares de estratégia ótimas sempre resultam no mesmo valor u do jogo. ou seja, se p*, q* e p**, q** forem estratégias ótimas, então 
 o valor de um jogo é, portanto, compensação esperada para o jogador L quando ambos os jogadores escolhem quaisquer estratégias ótimas possíveis.
Para encontrar estratégias ótimas, devemos encontrar vetores p* e q* que satisfaz a equação 4. Geralmente, isso é feito usando técnicas de programação linear. A seguir, temos casos especiais nos quais as estratégias podem ser encontradas usando técnicas elementares.
Por exemplo, o elemento sombreado em cada uma das matrizes de compensação seguir é um ponto de sela
 
Se uma matriz tiver um ponto de sela ars, ocorre estratégias ótimas para os dois jogadores são essas:
Isso mostra que na estratégia para o jogador L é fazer sempre o r-ésimo movimento e que é uma estratégia ótima para o jogador C é fazer sempre o s-ésimo movimento. Essas estratégias em que um só movimento é possível são denominadas estratégias puras. As estratégias nas quais é possível mais de um movimento são denominadas estratégias mistas. Para mostrar que as estratégias acima são ótimas, pode-se verificar as três equações a seguir:
Juntas, essas desigualdades implicam
quaisquer que sejam as estratégias p e q. como isso coincide com a equação 4, segue que p* e q* são estratégias ótimas.
 	Pela equação 6, o valor de um jogo estritamente determinado é simplesmente o valor numérico do ponto de sela ars. . É possível uma matriz de compensação ter vários pontos de Sela, Mas então a unidade do valor de um jogo garante que o valor numérico de todos os pontos de sela é o mesmo.
EXEMPLO 2. Estratégias ótimas para maximizar uma audiência
Duas redes de televisão competidoras, L e C, estão planejando levar ao ar programas de uma hora de duração para o mesmo horário. A rede L pode utilizar um entre três programas possíveis, e a rede C pode utilizar um entre quatro programas possíveis. nenhuma das redes sabe qual programa A outra vai levar ao ar. Ambas as redes contratam o mesmo Instituto de Pesquisa de opinião para lhe dar uma estimativa de como as diversas possibilidades de transmitir os dois programas vão dividir audiência. Instituto das redes a tabela 2, cuja (i,j)-ésima entrada é a porcentagem da audiência que assistira a rede L se o programa i da Rede L competir, em termos de audiência, com o programa j da Rede C. qual programa da Rede deveria levar ao ar para maximizar audiência?
Tabela 2. Porcentagem de audiência para a rede L
Subtraímos 50 de cada entrada da tabela e construímos a matriz:
Essa é a matriz de compensação do jogo de duas pessoas com soma zero no qual consideramos que as duas redes de televisão começam com 50% da audiência e em que a (i,j)-esima entrada da matriz é a porcentagem da audiência que a rede C perde para a rede L se os programas i da rede L e j da rede C competirem entre si. É fácil ver que a entrada a23= -5 , é um ponto de sela da matriz de compensação. Portanto, a estratégia ótima para a rede L é levar ao ar o programa 2 e a estratégia ótima para rede C e levar ao ar o programa 3. isso Vai resultar em 45% da audiência para a rede L e 55% da audiência para a rede C.
O outro caso em que podemos encontrar estratégias ótimas por meio elementares ocorre quando cada jogador tem somente dois movimentos possíveis. Nesse caso, a matriz de compensação é a matriz 2 x 2.
 Se o jogo for estritamente determinado, pelo menos uma das quatro estradas de A será um ponto de sela e as técnicas discutidas acima poderão, então, ser aplicadas para determinar as estratégias ótimas para os dois jogadores. Se o jogo não for estritamente determinado calculando os primeiros a compensação esperada com estratégias p e q quaisquer obtendo:
 
Como 
 p1 + p2 =1 e q1 + 12 = 1 		 		(10)
podemos substituir p2 = 1 - p1 e q2 = 1 - q1 em (9) para obter
E(p,q) = a11p1q1 + a12p1(1 - q1) + a21(1- p1)q1 + a22 (1-p1) (1-q1) 	 (11)
Rearranjando os termos da equação 11, podemos escrever
E(p,q) = [(a11 + a22 - a12 - a21) p1 - (a22 - a21)] q1 + (a12 - a22) p1 + a22 	(12)
Examinando os coeficientes do termo com q1 em 12, vemos que colocando
 esse coeficiente resulta ser zero e 12 reduz-se a
A equação 14 é independente de q, ou seja, se o jogador L escolher a estratégia determinada por 13, o jogador C não poderá modificar a compensação esperada por uma variação de sua estratégia.
Analogamente, pode ser verificado que se o jogador C escolher a estratégiadeterminada por:
então, substituindo em 12, obtemos:
As equações 14 e 16 mostram que 
quaisquer que sejam as estratégias p e q. Assim, as estratégias determinadas por 13, 15 e 10 são estratégias ótimas para os jogadores L e C, respectivamente, e obtemos o resultado seguinte:
TEOREMA 2: Estratégias ótimas para jogos de matrizes 2 x 2 
Para sermos completos, precisamos mostrar que as entradas nos vetores p* e q* são números estritamente entre 0 e 1. A equação 17 é interessante, pois implica que cada um dos jogadores, escolhendo sua estratégia ótima, pode forçar o valor do jogo a ser a compensação esperada, independentemente de qual estratégia foram escolhidas pelo outro jogador. No entanto, isso não é válido nos jogos em que cada jogador tenha mais de dois movimentos.
EXEMPLO 3: Usando o teorema 2- estratégias ótimas para jogos de matrizes 2 x 2
O governo federal deseja vacinar seus cidadãos contra certo vírus de gripe. O vírus tem dois sorotipos, mas é desconhecido a proporção na qual os dois sorotipos ocorrem na população do vírus. Foram desenvolvidas duas vacinas. A eficácia da vacina 1 é de 85% contra o sorotipo 1 e de 70% contra o sorotipo 2. A eficácia da vacina 2 é de 60% contra o sorotipo 1 e de 90% contra o sorotipo 2. Qual política de vacinação deveria ser adotada pelo governo?
Podemos considerar isso um jogo de duas pessoas na qual o jogador L ( o governo) deseja fazer a maior compensação ( a fração dos cidadãos resistentes ao vírus) possível e o jogador C ( o vírus) desejo é fazer a menor compensação possível. A matriz de compensação é:
Essa matriz não tem pontos de sela, de modo que podemos aplicar o teorema 2. Consequentemente: 
Assim, a estratégia ótima para o governo é inocular dos cidadãos com a vacina 1 e dos cidadãos com a vacina 2. Isso vai garantir que cerca de 76,7% dos cidadãos resistirá a um ataque do vírus, independentemente da distribuição dos dois sorotipos do vírus.
Uma distribuição de do sorotipo 1 e de do sorotipo 2 do vírus resultará nos mesmos 76,7% de cidadãos resistente, Independentemente da política de vacinação adotada pelo governo. 
CONCLUSÃO 
Por fim, fica evidente a aplicabilidade para estudos relacionados aos jogos de estratégias que podem contribuir para sociedade como preventivos de doenças como: (governo x vacina aplicada); jogos de azar (jogador 1 x jogador 2); investimentos bancários (poupança x outro investimento), além de outros estudos que envolvam estratégias.
REFERÊNCIAS BIBLIOGRÁFICAS
HOWARD, Anton. Álgebra linear com Aplicações. 10. ed. Porto Alegre: Bookman, 2012.
SILVA, Ricardo. Álgebra Linear Aplicada a Jogos de Estrategia. Disponível em:<https://fenix.tecnico.ulisboa.pt/downloadFile/563568428712069/Algebra_Linear_Jogos_Estrategia.pdf> Acesso em 15 de março de 2018
SEYMOUR, Lipschutz. Álgebra Linear: Teoria e Problemas. São Paulo, SP, 1994.