Teoria dos Jogos A2 - GRUPO

Prévia do material em texto

Universidade Veiga de Almeida
Engenharia de Produção:
Pesquisa Operacional
ANDREZIENE ALMEIDA DOS SANTOS – 20151112506
HENRIQUE ALMEIDA CASTRO DIAZ – 20162104909
MARCELLA SANTOS MARTINS – 20171102035
PEDRO ALVARENGA NANES – 20171101521
A aplicabilidade da Modelação matemática para resolução dos desafios na Teoria dos Jogos
Rio de Janeiro – RJ
2021
ANDREZIENE ALMEIDA DOS SANTOS - 20151112506
HENRIQUE ALMEIDA CASTRO DIAZ - 20162104909
MARCELLA SANTOS MARTINS – 20171102035
PEDRO ALVARENGA NANES – 20171101521
A aplicabilidade da Modelação matemática para resolução dos desafios na Teoria dos Jogos
Trabalho de Pesquisa Operacional apresentado a Universidade Veiga de 
Almeida, como parte dos requisitos a obtenção da nota na Avaliação A1
Professor: D. Sc. Marco Almeida
Rio de Janeiro – RJ
2021
SUMÁRIO
RESUMO 
A Teoria dos Jogos é um ramo da matemática aplicada que estuda situações estratégicas onde jogadores escolhem diferentes ações na tentativa de melhorar seu ganho. Inicialmente desenvolvida como ferramenta para compreender comportamento econômico, a teoria dos jogos é hoje usada em diversos campos acadêmicos. O objetivo do trabalho é mostrar não só a sistematização e a apresentação dos conceitos fundamentais da teoria dos jogos, mas também a formalização matemática dos principais conceitos clássicos de solução de um jogo e ilustrar a sua aplicação. A programação matemática pode ser utilizada através de jogos simples, conceitos de soma-zero, estratégias, matriz de ganhos, jogos estritamente e não estritamente determinados e finalmente, o famoso Teorema Minimax de John Von Neumann e Oskar Morgenstern. 
Palavras-chave: Teoria dos jogos, modelagem matemática, estratégias, conflitos, - Maximin - Minimax 
 INTRODUÇÃO
Inicialmente, a teoria dos jogos foi desenvolvida como um modelo para analisar situações de conflito, buscando uma razão nas escolhas a serem realizadas por esses agentes de decisão. Em sua essência, ela é o estudo da interdependência estratégica, isto é, situações em que minhas ações afetam meu resultado e o resultado dos outros e vice-versa.
Teoria dos jogos é um ramo da matemática aplicada que estuda situações estratégicas onde jogadores escolhem diferentes ações na tentativa de melhorar seu retorno. Inicialmente desenvolvida como ferramenta para compreender comportamento econômico e depois usada pela Corporação RAND para definir estratégias nucleares, a teoria dos jogos é hoje usada em diversos campos acadêmicos. A partir de 1970 a teoria dos jogos passou a ser aplicada ao estudo do comportamento animal, incluindo evolução das espécies por seleção natural. 
Alguns matemáticos já fizeram estudos de jogos, como James Waldergrave, Augustin Cournot, Ernst Zermelo e Emile Borel. Porém, nenhum deles deu continuidade às suas pesquisas para melhor fundamentá-las. Assim, esta teoria começou a se tornar realmente um foco de estudo na Matemática na década de 30 com pesquisas do matemático John von Neumann, ganhando um enfoque maior no ano de 1944 com seu livro The Theory of Games and Economic Behavior, escrito por ele e Oskar Morgenstern.
A partir da segunda metade do anos 60, engenheiros e economistas começaram a perceber a Teoria dos Jogos como um instrumento de considerável alcance para uma velha questão que voltará a tomar fôlego: a análise, projeto e implementação de mecanismos de alocação de recursos. O principal protagonista desta questão foi HURVICZ (1973). Sua preocupação central estava voltada para a análise institucional, especialmente em economias informacionalmente descentralizadas. Para tal propósito, se envolveu na construção de mecanismos de alocação ou de planejamento que produzissem resultados "satisfatórios". Como cada mecanismo de alocação de recursos contém implicitamente definido um jogo, abre-se assim um novo campo de pesquisa:
a análise e projetos de mecanismos de alocação de recursos através das técnicas da Teoria dos Jogos.
 
PROBLEMA DE PESQUISA E HIPÓTESES 
A teoria dos jogos é usada para se estudar assuntos tais como eleições, leilões, balança de poder, evolução genética, etc. Ela nos fornece a linguagem para a descrição de processos de decisão conscientes e objetivos envolvendo mais do que um indivíduo. Não apenas isso, ela é também uma teoria matemática pura, que pode e tem sido estudada de tal forma, sem a necessidade de relacioná-la com problemas comportamentais ou jogos.
Diversas pessoas acreditam que a teoria dos jogos formará em algum dia o alicerce de um conhecimento técnico estrito de como decisões serão tomadas e de como o mundo econômico girará ao seu redor. O desenvolvimento da teoria ainda não atingiu este patamar e, hoje, a teoria dos jogos é mais estudada em seus aspectos matemáticos puros e, em aplicações, ela é usada como uma ferramenta ou alegoria que auxiliam no entendimento de sistemas mais complicados.
JUSTIFICATIVA
Vivemos em uma sociedade na qual os conflitos e interesses são inerentes às relações humanas, e por conta disso que a aplicação desta teoria consegue ser tão vasta, e abranger áreas tão distintas das exatas; como a Psicologia, Ciências Sociais, Política, Biologia, Sociologia, entre outras. Trazendo análises importantes na tomada de decisões que podem ser utilizadas como ferramentas para enriquecer o trabalho desenvolvido dentro da área em questão.
OBJETIVOS 
O seguinte trabalho tem como objetivo principal a apresentação e sistematização dos conceitos básicos da Teoria dos Jogos, também iremos ilustrar sua aplicação com alguns exemplos junto com a formalização matemática dos seus principais conceitos. 
 Mas o que seria a Teoria dos Jogos? Essa teoria matemática estuda a tomada de decisões de indivíduos quando seus resultados estariam diretamente conectados com as decisões de terceiros. Assim, um jogo é assimilado a partir da interação estratégica desses indivíduos, e a partir desta interação, podemos observar a influência que um indivíduo tem sobre os outros participantes (jogadores). 
Um exemplo muito comum e bastante conhecido sobre a Teoria dos Jogos é o “Dilema do Presidiário”. Neste exemplo, dois suspeitos (A e B) são presos simultaneamente. A polícia, não tendo provas suficientes para condenar ambos suspeitos, oferece o mesmo acordo para ambos: caso um dos prisioneiros testemunhem contra o outro, o primeiro que o fizer teria sua sentença anulada e o outro cumpriria 10 anos de prisão. Se ambos os prisioneiros permanecessem em silêncio, os dois seriam condenados apenas a 6 meses de exclusão, por conta da falta de provas no caso. Mas, caso ambos em algum momento resolvessem confessar, neste caso os dois iriam cumprir 5 anos de prisão. 
Utilizando este caso, podemos observar que a decisão que cada um dos prisioneiros acabe tomando irá impactar diretamente não somente no seu destino, mas também no de seu parceiro. Assim, ambos se encontram em um dilema para decidir o que será feito e qual a melhor estratégia seria traçada, já que ambos não teriam como saber qual será a decisão escolhida pelo outro e quais resultados podem ser obtidos a partir da própria decisão. Acredita-se que a programação matemática poderá resolver essas questões. Abaixo iremos demonstrar mais alguns exemplos muito comuns onde a Teoria dos Jogos pode ser utilizada.
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.
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 (perdere 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:
B1	B2	...	Bnp11
p12
...
p1m
p21
p22
...
p2m
:
:
:
:
pm1
pm2
...
pmn
A1 A2
:
Am
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 ímpar" para o jogador A que apostou em "par" é dada por:
 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 colocar um número ímpar de dedos (estratégia B2), o jogador A irá ganhar -1, ou seja, A irá perder e B irá ganhar.
1.2) Abordar os modelos matemático (Andreziene)
Solução Ótima de Jogos de Soma Zero e Dois Jogadores (Perfil Conservador)
Outra forma de encontrar a solução ótima de um jogo de soma constante e dois jogadores é pela utilização do conceito de maxmin e minmax. Estes conceitos baseiam-se no princípio da “melhor opção entre as piores”. Este princípio conservador, portanto, pressupõe jogadores avessos ao risco, ou, prudentes.
Bancos comerciais, são intermediários financeiros que têm nas transferências de recursos dos agentes superavitários para os deficitários sua atividade primordial. Logo, a administração de recursos de terceiros, a gestão do capital de acionistas (ou proprietários), o papel fundamental que desempenham no sistema de pagamentos, e a conseqüente importância dos mesmos para as demais atividades econômicas, são características que os conduzem para posturas conservadoras, sejam por iniciativa própria ou por regulação (Kaufman, 1991). Justifica-se assim a aderência desta postura conservadora para o contexto do trabalho. Abaixo é exemplificada tal estratégia.
A solução do ótimo na matriz de pagamentos acima pela adoção da postura conservadora
seria:
O pior que pode ocorrer com o J1 dadas as escolhas do J2 são representados pelos mínimos de suas estratégias (linhas). Dado ao cenário pessimista o J1 irá maximizar seu resultado (maxmin), que no caso é 5, ou seja, a adoção de s2 . O pior que pode ocorrer com J2 dadas as escolhas do J1 são representadas pelos máximos de coluna. Assim o J2, prudente, irá escolher a
estratégia que minimiza sua perda, em que o ganho ou perda é dado pelo valor positivo ou negativo, respectivamente na matriz de pagamentos.
 A solução ótima, então, é dada pelas s2 do J1 e pela s’2 do J2. O payoff é a favor do J1 porque este tem um resultado positivo sobre o J2 (por exemplo, ganha 5% do mercado do J2). 
 Utilizando a estratégia conservadora ou a estratégia dominante temos a solução 5, um ponto-sela. 
 O equilíbrio ocorre quando os dois jogadores ao otimizarem suas respectivas estratégias conservadoras obtêm o mesmo payoff na matriz de pagamentos. A solução de ponto-sela ocorre
quando o maxmin de um jogador é o mesmo que o minmax do outro. Formalmente:
maxmin(aij ) = min max(aij )
i	j	j	i
Desta forma, os jogadores “concordam” com o resultado do jogo e o ponto-sela é a solução.
No caso de jogos de soma zero com dois jogadores esta solução, caso exista, é EN.
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.
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
probabilidade estas variáveis devem ser obrigatoriamente não-negativas e as suas somatórias 
Os planos (x1, x2, ..., xm) e (y1, y2,..., yn) são denominados Estratégias Mistas.
Estes planos significam que o jogador A 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. 
O payoff esperado pode ser determinado como:
 (payoff para jogador A)
onde:
pij é o payoff se o jogador A utilizar a estratégia i e o jogador B utilizar a estratégia j.
Teorema Minimax: Se estratégias mistas são permitidas, o par de estratégias mistas que é ótimo de acordo com o critério Minimax fornece uma solução estável com v = v = v, de tal maneira que nenhum jogador pode melhorar sua situação mudando sua estratégia. 
O payoff esperado para o exemplo 4 (calculado através de (4) resulta em V= 1/4 
Esta medida não revela nada sobre o risco envolvido em jogar o jogo, mas indica o valor
que o payoff médio irá tender se o jogo for jogado várias vezes.
Embora o conceito de estratégias mistas torne-se bastante intuitivo se o jogo é repetido várias vezes, este requer alguma interpretação quando o jogo é jogado apenas uma vez. Neste caso, usando uma estratégia mista ainda envolve selecionar e usar uma única estratégia pura (randomicamente selecionada a partir da distribuição de probabilidade especificada).
O objetivo da Teoria dos Jogos é determinar a estratégia ótima para cada jogador, sendo o jogo de estratégia pura ou mista. Este objetivo pode ser alcançado através de Programação Linear.
Ilustração da teoria dos jogos, antes de introduzir a formalização matemática. 
Case PEDRA-PAPEL-TESOURA. O jogo pedra, papel e tesoura consiste em dois jogadores ficando um de frente para o outro e optando por um entre os três elementos que dão nome ao jogo. Estes
elementos são representados com as mãos (a pedra é simbolizada por um punho fechado; a tesoura, por dois dedos esticados; e o papel, pela mão aberta) e cada elemento apresenta uma habilidade e uma limitação diante de cada um dos outros, o que amplia as possibilidades de combinações e torna o jogo mais interessante. Exemplo: Pedro e João devem simultaneamente estender os braços com suas respectivas representações e então comparam os símbolos para decidir quem ganhou, da seguinte forma:
· Pedra ganha da tesoura (quebrando-a).
· Tesoura ganha do papel (cortando-o).
· Papel ganha da pedra (embrulhando-a).
Caso dois jogadores façam o mesmo gesto, ocorre um empate, e geralmente se joga de novo até desempatar.
Esse jogo é muito similar ao Par ou Ímpar na medida em que nenhum dos dois jogadores têm como tomar uma má decisão, ou tentar criar algum artifício engenhoso capaz de aumentar suas possibilidades
em uma única jogada. Mas, assim como no Par ou Ímpar, se o jogo
for realizado diversas vezes e em sequência, algum dos jogadores pode se colocar em desvantagem, optando com mais frequência por um dos elementos. Desta forma, uma boa maneira de se proteger de tal desvantagem seria escolher com igual probabilidades de 1/3 entre pedra, papel ou tesoura. Como é muito difícil ter imparcialidade na escolha dos elementos e conseguir de fato obter este 1/3 para cada escolha, uma maneira eficaz de se fazer isso seria utilizar uma roleta aleatória como representa a Figura 1.
 
Figura 1- Roleta Aleatória I
A matriz de ganho do jogo Pedra-Papel-Tesoura pode ser tabu- lada como
Como visto anteriormente, as entradas positivas referem-se `a vit´oria de Pedro e os valores negativos `as derrotas, o valor zero representa um empate.
1.3) Como o modelo matemático pode ajudar a resolver casos da teoria dos jogos (Andreziene)
Resolução da Teria dos Jogos por Programação Linear (Programação matemática)
Sendo o payoff esperado do jogador A utilizar as suas m estratégias quando o jogador B utiliza a sua estratégia j, as probabilidades ótimas ou planos (x1, x2, ..., xm) do jogador A podem ser determinadas resolvendo o seguinte problema Maximin:
Com isso, o problema para o jogador A pode serescrito como:
As probabilidades ótimas ou planos (y1, y2,..., yn) do jogador B podem ser determinadas resolvendo o seguinte problema Minimax:
· A expressão (7) desempenha o papel de minimizar v, uma vez que v será sempre menor que pijxi.
i1
Assim, a função-objetivo pode apenas maximizar v, uma vez que a expressão (7) minimiza v, estando de acordo com o critério MaxMin.
De maneira análoga ao problema do jogador A, o problema do jogador B pode ser escrito como:
Minimize z = v
Comparando as expressões em (8) e em (10), percebe que o problema do jogador B é o dual do problema do jogador A e vice-versa. 
 
O problema para o jogador A fica: 
Maximize z = v
Sujeito a (11)
O código para o Lindo, encontra-se abaixo:
O problema para o jogador B (dual) fica:
Minimize z = v
O código para o Lindo, encontra-se abaixo
Como era de se esperar, este jogo possui uma solução de ponto de sela ou estratégia pura, com isso o plano ótimo para o jogador A é:
e o plano ótimo para o jogador B é:
O valor v do jogo é 5 (v = 5%).
Os resultados apresentados em (13) e (14) estão de acordo com resultados obtidos no exemplo, ou seja, o jogador A deve utilizar somente a sua segunda estratégia (A2) e desprezar as demais assim como o jogador B, que deve utilizar também somente a sua segunda estratégia (B2) e desprezar as demais.
Exemplo 6: A mesma matriz de payoff do exemplo 3.
O problema para o jogador A fica:
Maximize z = v
Sujeito a
O código para o Lindo, encontra-se abaixo:
O problema para o jogador B fica:
Minimize z = v
O código para o Lindo, encontra-se abaixo:
Como era de se esperar, este jogo não possui uma solução de ponto de sela ou estratégia pura, com isso o plano ótimo para o jogador A é:
E o plano ótimo para o jogador B é: 
O valor Vdo jogo é 11/2. 
A contribuição fundamental da Teoria dos Jogos é que esta fornece uma metodologia para formulação e análise dos problemas apresentados em situações simples. Entretanto, existe uma grande lacuna entre o que a teoria pode tratar e a complexidade da maioria das situações competitivas reais.
CONSIDERAÇÕES FINAIS
	A Teoria dos Jogos, apesar de seus curtos períodos de estagnação, em nenhum momento deixou de se desenvolver. Sua história constitui um processo de desenvolvimento de novos conceitos e técnicas. No entanto chega-se a um determinado momento de desenvolvimento e de especialização destas técnicas onde, aparentemente, rompe-se o elo entre conceito e realidade. De forma que essa metodologia, que possui um elo tão orgânico em relação ao comportamento humano pode, devido obviamente ao alto grau necessário de abstração das novas técnicas, ser equivocadamente vista como uma mera abstração e sem qualquer ligação com o mundo real.
 
REFERÊNCIAS BIBLIOGRÁFICAS
https://simulare.com.br/blog/teoria-dos-jogos/
https://www.ufjf.br/epd042/files/2009/02/jogos.pdf
http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0104-530X1994000300005
https://www.ime.usp.br/~rvicente/IntroTeoriaDosJogos.pdf
2
image3.png
image4.png
image5.png
image6.png
image7.png
image8.png
image9.png
image10.png
image11.png
image12.png
image13.png
image14.png
image15.png
image16.png
image17.png
image18.png
image19.png
image20.png
image21.png
image22.png
image23.png
image24.png
image25.png
image26.png
image27.png
image1.png
image2.png
image28.jpeg
image29.png
 
 
 
1
 
 
 
 
 
 
 
Universidade Veiga de Almeida
 
Engenharia de Produção:
 
Pesquisa Operacional
 
 
ANDREZIENE ALMEIDA DOS SANTOS 
–
 
20151112506
 
HENRIQUE ALMEIDA CASTRO DIAZ 
–
 
20162104909
 
MARCELLA SANTOS MARTINS
 
–
 
20171102035
 
PEDRO ALVARENGA NANES 
–
 
20171101521
 
 
A 
aplicabilidade da Modelação matemática para resolução dos desafios na 
Teoria dos Jogos
 
 
 
 
 
Rio de Janeiro 
–
 
RJ
 
2021
 
 
 
 
1 
 
 
 
 
 
 
Universidade Veiga de Almeida 
Engenharia de Produção: 
Pesquisa Operacional 
 
ANDREZIENE ALMEIDA DOS SANTOS – 20151112506 
HENRIQUE ALMEIDA CASTRO DIAZ – 20162104909 
MARCELLA SANTOS MARTINS – 20171102035 
PEDRO ALVARENGA NANES – 20171101521 
 
A aplicabilidade da Modelação matemática para resolução dos desafios na 
Teoria dos Jogos 
 
 
 
 
Rio de Janeiro – RJ 
2021