2 - Teoria dos Jogos (1)

Prévia do material em texto

Teoria dos Jogos
O que é a Teoria dos Jogos
A teoria dos jogos é uma teoria matemática criada para se modelar fenômenos que podem ser observados quando dois ou mais “agentes de decisão” interagem entre si. Ela fornece a linguagem para a descrição de processos de decisão conscientes e objetivos envolvendo mais do que um indivíduo.
A teoria dos jogos é usada para estudar, por exemplo, eleições, leilões, economia, etc. A teoria dos jogos também uma teoria matemática pura que é estudada sem a necessidade de resolver problemas comportamentais.
Alguns estudiosos acreditam que a teoria dos jogos será a base o conhecimento técnico estrito para a tomada de decisões e para a economia.
O que é um jogo?
A teoria dos jogos pode ser definida como a teoria dos modelos matemáticos que estuda a escolha de decisões ótimas sob condições de conflito.
O elemento básico em um jogo é o conjunto de jogadores que dele participam. Cada jogador tem um conjunto de estratégias.
Quando cada jogador escolhe sua estratégia, temos então uma situação ou perfil no espaço de todas as situações (perfis) possíveis. Cada jogador tem interesse ou preferências para cada situação no jogo.
Em termos matemáticos, cada jogador tem uma função utilidade que atribui um número real (o ganho ou payoff do jogador) a cada situação do jogo.
Teoria dos Jogos : Utilidade
Utilidade é a representação numérica da preferência;
A classificação em preferências nos permite avaliar as ações (escolhas) dos agentes para decidir a “jogada”, e sendo assim necessitaremos ter a noção da preferência do “oponente”.
A regra que associa cada opção de escolha (preferência) a utilidade é a função de utilidade.
A função de utilidade pode ser mostrada formalmente:
Lê-se: A é preferível a B, se somente se a utilidade de A for maior ou igual a utilidade de B. 
A Teoria da Escolha Racional
A teoria dos jogos tem como principal objetivo explicar como os agentes, interagindo entre si, fazem suas escolhas.
Assumindo que os agentes são racionais – procuram sempre maximizar suas recompensas - utilizando o método que considera as preferências de cada um.
Em um problema de escolha pessoal ou empresarial existem um indivíduo e um conjunto de alternativas. O individuo fará sua escolha de acordo com suas relações de preferência.
Teoria da escolha racional
Preferência ()
, onde lemos é tão boa quanto ou é fracamente preferível a ou ainda, é preferível a .
Preferência estrita ()
, onde lemos é estritamente (sempre) preferível a .
Indiferença ()
, onde lemos e são equivalentes.
Axiomas da preferência revelada
O Axioma Fraco das Preferências Reveladas (AFrPR):
Conhecidas duas cestas de consumo ou conjuntos X (com os bens x1 e x2) e Y (com os bens y1 e y2) se X for escolhida (preferida) ao invés de Y, então Y não poderá ser escolhida em detrimento de X.
O Axioma Forte das Preferências Reveladas (AFoPR):
Dadas as cestas de consumo X, Y e Z, se a cesta X for preferível a cesta Y e esta for escolhida em lugar da cesta Z, então X terá que ser preferível a Z.
Teoria dos Jogos: Utilidade
Represente matematicamente estas situações de preferência:
Júlio gosta muito das aulas de Matemática e pouco das de História.
Gabriela, por sua vez, adora aulas de História e aprecia pouco as de Matemática.
Renata é indiferente entre o consumo de margarina ou de manteiga.
Alfredo não gosta de lixo.
Teoria dos Jogos: Utilidade
Represente matematicamente estas situações de preferência:
Júlio gosta muito das aulas de Matemática e pouco das de História.
Gabriela, por sua vez, adora aulas de História e aprecia pouco as de Matemática.
Renata é indiferente entre o consumo de margarina ou de manteiga.
Alfredo não gosta de lixo.
C: consumo
Exercício 1
Um individuo vai almoçar em um restaurante. Ao receber o cardápio a primeira coisa que ele olha é os preços. Desta forma, a escolha de um determinado prato dependerá do seu custo.
Suponha três opções de refeição, estabeleça uma relação de preferência entre elas de modo que exista uma superior e uma inferior.
Exercício 1
Classificar a preferência por preço:
C: Caro;
M: Médio;
B: Barato;
Exercício 2
Considere um parlamento imaginário com 3 partidos em que os deputados possuem todos o mesmo ordenamento de preferências do seu respectivo partido. Considere ainda, que os partidos possuem o mesmo número de deputados. Chamaremos os partidos de Conservador, Moderado e Radical. Existem 3 propostas orçamentárias a serem votadas.
Aumentar o número de propostas sociais (proposta A);
Manter o número de propostas sociais (proposta M);
Reduzir o número de propostas sociais (proposta R);
Exercício 2
As preferências dos partidos estão representados a seguir:
O processo de escolha será feito da seguinte forma:
Na primeira votação será escolhida uma proposta entre as opções A e M;
Na segunda votação será escolhida uma proposta entre as opções M e R.
Na terceira votação será escolhida uma proposta entre as opções A e R.
Mostre quais seriam os resultados das votações e a ordem de preferência do parlamento.
	Partido	Ordem de Preferências
	Conservador	
	Moderado	
	Radical	
O que é um jogo?
O que é um jogo?
Um jogo tem os seguintes elementos básicos:
Existe um conjunto finito de jogadores, representado por . 
Cada jogador possui um conjunto finito de opções de opções, denominadas estratégias puras do jogador .
Um vetor , onde é uma estratégia pura para o jogador , é denominado um perfil de estratégia pura.
O que é um jogo?
O conjunto de todos os perfis de estratégia pura formam, portanto, o produto cartesiano:
Denominado espaço de estratégia pura do jogo. Para jogador , existe uma função utilidade
Que associa o ganho (payoff) do jogador a cada perfil de estratégia pura .
Classificação dos Jogos
Quanto ao resultado final
Jogos de Soma Zero
Um jogo de soma-zero é aquele em que o total de pagamentos para todos os jogadores, para cada combinação de estratégias, sempre soma zero ou, em outras palavras, o lucro de um jogador é igual ao prejuízo de outro. O Poker e alguns jogos de tabuleiro exemplificam jogos de soma zero porque o vencedor recebe exatamente a soma das perdas de seus oponentes. 
Jogos de Soma não nula	
Diferentemente dos jogos de soma nula, aqueles cuja soma dos resultados e diferente de zero são mais estudados pelos pesquisadores da teoria dos jogos, pois apresentam um maior número de aplicações no mundo real. 
Classificação dos Jogos
Quanto à sequência de ações
Jogos Simultâneos ou estáticos
Jogos simultâneos ou estáticos são aqueles em que cada jogador toma sua decisão sem levar em consideração a decisão dos outros. Isto ocorre porque os jogadores desconhecem a priori as ações de seus adversários. (Par ou ímpar, leilão com envelope fechado)
Jogos sequenciais ou dinâmicos:
Um jogo sequencial ou dinâmico é aquele em que os jogadores executam suas ações de forma não simultânea, ou seja o próximo jogador tem conhecimento da jogada de seu antecessor. (Xadrez, disputa de mercado)
Classificação dos jogos
Quanto à cooperação entre agentes
Jogos competitivos
Um jogo é dito competitivo ou não cooperativo quando os agentes envolvidos não negociam entre si as estratégias a serem implementadas. (disputas entre empresas, batalhas militares)
Jogos cooperativos
Um jogo cooperativo acontece quando os agentes podem negociar entre si as estratégias a serem implementadas. (Cartel, Oligopólios)
O jogo
Considere um jogo representado na matriz de pagamentos a seguir:
O jogador 1 tem suas opções registradas nas linhas e o jogador 2 nas colunas. 
Suponha que o Jogador 1 escolheu “para cima” e que o Jogador 2 escolheu “esquerda”, então o Jogador 1 ganha 4, e o Jogador 2 ganha 3. 
			Jogador 2	
			Esquerda	Direita
	Jogador 1	Para cima		
		Para baixo		
O jogo (Árvore)
A empresa X está avaliando a proposta de lançamento de um novo modelo de Van no mercado. A empresa Y, sabendo desta possibilidade estuda se reduzirá o preço de seu modelo para não perder espaço no mercado. 
Se a empresa X lançar seuproduto e a empresa Y reduzir o preço do seu, cada empresa terá um lucro de R$2 milhões. Caso a Y mantenha seu preço seu lucro será de R$4 milhões e o da X R$2 milhões. 
Se a empresa X não lançar a nova Van e a Y mantiver seu preço, a X terá lucro de R$1 milhão e a Y de R$4 milhões, mas se a Y mesmo sem um novo produto na praça, decidir reduzir preço seu lucro cairá para R$3 milhões. 
O jogo (Árvore)
Empresa X
Lançar
Não
Lançar
Empresa Y
Empresa Y
(2,4)
(2,2)
(1,4)
(1,3)
Mantém o preço
Mantém o preço
Reduz o preço
Reduz o preço
Exemplo 1: O Dilema do Prisioneiro
Possivelmente o exemplo mais conhecido na teoria dos jogos é o dilema do prisioneiro.
Ele foi formulado por Albert W. Tucker em 1950, em um seminário para psicólogos na Universidade de Stanford, para ilustrar a dificuldade de se analisar certos tipos de jogos.
Exemplo 1: O Dilema do Prisioneiro
A situação é a seguinte: dois ladrões, Al e Bob, são capturados e acusados de um mesmo crime. Presos em selas separadas e sem poderem se comunicar entre si, o delegado de plantão faz a seguinte proposta: cada um pode escolher entre confessar ou negar o crime. Se nenhum deles confessar, ambos serão submetidos a uma pena de 1 ano. Se os dois confessarem, então ambos terão pena de 5 anos. Mas se um confessar e o outro negar, então o que confessou será libertado e o outro será condenado a 10 anos de prisão. 
Exemplo 1: O Dilema do Prisioneiro
Neste contexto, temos:
Jogadores:
Estratégias puras:
Espaço de estratégias puras do jogo:
Exemplo 1: O Dilema do Prisioneiro
As duas funções utilidade são:
são dadas por:
(que representam os ganhos de Al) e
(que representam os ganhos de Bob). 
Exemplo 1: O Dilema do Prisioneiro 
É uma prática se representar os payoffs dos jogadores através de uma matriz matriz de payofffs (pagamentos ou ganhos).
Nesta matriz, os números de cada célula representam, respectivamente, os payoffs de Al e Bob para as escolhas de Al e Bob correspondentes a célula.
			Bob	
			Confessar	Negar
	Al	Confessar		
		Negar		
Soluções em um jogo
Uma solução de um jogo é uma prescrição ou previsão sobre o resultado do jogo.
Existem vários conceitos diferentes de solução. Estudaremos os dois conceitos mais comuns: Dominância e Equilíbrio de Nash.
Considere o dilema do prisioneiro. Como encontrar uma solução para o dilema de Bob e Al, isto é, que estratégias são plausíveis se os dois prisioneiros querem minimizar o tempo de cadeia?
Se analisarmos o jogo do ponto de vista de Al, ele pode raciocinar da seguinte maneira:
“Duas coisas podem acontecer: Bob pode confessar ou Bob pode negar. Se Bob confessar, então é melhor para mim confessar também. Se Bob não confessar, então eu fico livre se eu confessar. Em qualquer um dos casos, é melhor para mim confessar. Então, eu confessarei.”
Soluções de um jogo
Se analisarmos agora o jogo do ponto de vista de Bob, podemos aplicar a mesma linha de raciocínio e concluir que Bob também irá confessar. Assim, ambos confessarão e ficarão presos por 5 anos.
Em termos de teoria dos jogos, dizemos que os dois jogadores possuem uma estratégia dominante, isto é, todas menos uma estratégia é estritamente dominada, que o jogo é solucionável por dominância estrita iterada e que o jogo termina em uma solução que é um equilíbrio de estratégia dominante, conceitos que definiremos a seguir.
Exemplo 2: A Batalha dos Sexos
Um homem e a sua mulher desejam sair para passear.
O homem prefere assistir a um jogo de futebol enquanto que sua mulher prefere ir ao cinema.
Se eles forem juntos para o futebol, então o homem tem satisfação maior do que a mulher.
Por outro lado, se eles forem juntos ao cinema, então a mulher tem satisfação maior do que o homem.
Finalmente, se eles saírem sozinhos, então ambos ficam igualmente insatisfeitos.
Esta situação também pode ser modelada como um jogo estratégico.
Exemplo 2: A Batalha dos Sexos
Temos:
Jogadores:
Estratégias Puras:
Espaço de Estratégias Puras do Jogo:
Exemplo 2: A Batalha dos Sexos
As duas funções de utilidade são:
E são descritas pela seguinte matriz de payoffs:
			Mulher	
			Futebol	Cinema
	Homem	Futebol		
		Cinema		
Exercício 1: A batalha de Bismark
Em dez/1942 o Japão decidiu levar reforços da China e do Japão, para Nova Guiné. Esta operação envolvia um risco elevado, pois o poderio aéreo aliado era muito forte. 
O comboio japonês dispunha de duas rotas para alcançar seu destino. A rota sul, que normalmente tinha tempo bom e boa visibilidade e a rota norte com características opostas. 
As forças aliadas, por seu turno, tinham aviões para pesquisar uma rota por vez. Isto implicava o consumo de um dia inteiro de buscas em qualquer das rotas. Assim, se a busca fosse mal sucedida os aliados perderiam um dia de ataque. 
Caso obtivesse sucesso no primeiro dia de busca, os aliados conseguiriam 3 dias de bombardeios na rota sul ou 2 dias de bombardeios na rota norte. 
A representação deste jogo na forma normal ou estratégica fica assim: 
			Japão	
			Rota Sul	Rota Norte
	Aliados	Rota Sul		
		Rota Norte		
Exercício 2
Dois indivíduos, totalmente sem recursos, resolvem constituir uma empresa somente com capital de terceiros. Para isto, tomam emprestados R$10 milhões, sendo metade no banco A e metade no banco B. Após um ano de atividade e alguns insucessos, os ativos da empresa foram reduzidos para R$ 6 milhões, valor inferior a sua divida. A situação se agrava de tal forma que a expectativa é que a empresa funcione por apenas mais 1 ano. Para os bancos restam as seguintes opções: renovar ou não os empréstimos.
Caso os bancos decidam renovar a dívida recebem, cada um, juros no valor de R$1 milhão e R$3 milhões da partilha dos ativos da empresa. Se somente um deles renovar o empréstimo receberá apenas R$1 milhão referente ao ativos remanescentes, pois a empresa pagará R$5 milhões ao banco que não renovou. Se os dois bancos não renovarem os débitos, a empresa decreta sua falência e cada um recebe R$3 milhões. 
Exercício 2
Para o banco A temos o seguinte conjunto de estratégia:
A = {renova empréstimo, Não renova empréstimo}
E para o banco B, que tem as mesmas opções, temos:
B = {renova empréstimo, Não renova empréstimo}
Os conjuntos de payoffs serão:
A = {1,3,4,5} para o banco A e;
B = {1,3,4,5} para o banco B.
E a representação desta situação na forma de jogo fica como a seguir:
			Banco B	
			Renova	Não Renova
	Banco A	Renova		
		Não Renova		
Exercício 3
Com o objetivo de aumentar sua participação no setor de transporte aéreo a empresa Fly pensa em adotar uma das seguintes estratégias: Descontos no valor das passagens ou serviço de busca do passageiro em sua residência.
A empresa Verde, do mesmo setor, observa esta movimentação e aguarda a ação da concorrente para depois agir estrategicamente. Esta empresa tem como politica não conceder descontos em suas passagens por achar que esta estratégia desvaloriza seus serviços. Assim suas opções de respostas serão: oferecer um programa de milhagem ou serviço personalizado de busca do passageiro em sua residência.
Se a Fly conceder descontos e a Verde um novo programa de milhagem, a primeira aumentará em 5% seu volume de passageiros, enquanto a outra receberá mais 10%.
Caso a Verde opte por reagir com um serviço de busca os payoffs serão de 8% para a Fly e 5% para a Verde. Se a Fly oferecer um serviço de busca e a Verde também, os payoffs serão de 3% para a Verde e 12% para a Fly, mas se a Verde reagir com um programa de milhagem ela terá 4% a mais de passageiros, enquanto a Fly terá mais 11%.
De acordo com o que foi especificado o conjunto de estratégia da Fly será:
F = {conceder desconto, oferecer serviço de busca}
Já a empresa Verde ficará com o seguinte conjunto de opções estratégicas:
V = {programa de milhagem, oferecer serviço de busca}
Os conjuntos de payoffs associados as estratégias serão:
F = {5,8,11,12} para a Fly e;
V = {3,4,5,10} para a Verde.
Fly
Descontos
Serviço de Busca
Verde
Verde
(5,10)
(8,5)
(11,4)
(12,3)
Milhagem
Milhagem
Serviço de Busca
Serviço deBusca