Teoria dos Jogos

Prévia do material em texto

1. Teoria dos Jogos
5.1 Elementos de um jogo
· Jogadores: num jogo com n jogadores, tem-se seu conjunto 
· Estratégias: cada jogador i tem um conjunto de estratégias ;
· Payoffs (função objetivo): num jogo do n estratégias, podemos denotar o payoff de um jogador i como sendo: ;
Um jogo pode ser representado em notação por:
Formas de Representar Jogos: exemplo do Dilema dos Prisioneiros
Dois prisioneiros são interrogados, podendo confessar ou não seus crimes. Caso ambos confessem, há uma punição leve (u = 1). Caso ambos não confessem, a punição é ainda mais leve (u = 2). Caso apenas um confesse, o delator (1) recebe uma recompensa e o que não confessa (2) recebe uma punição forte (u1 = 3 e u2 = 0).
a) Representação na Forma Extensa (Árvore)
b) Representação na Forma Normal (Estratégica ou de Tabela)
Exemplos: 
L4-2a) Dois motoristas se aproximam de um cruzamento e eles podem parar (P) ou continuar (C). Se ambos pararem, os dois recebem o payoff u=1. Se ambos continuarem, eles colidem e u=0. Se um motorista parar e o outro continuar, este recebe u=2 e o que parou, u=1 – c, onde c é o desgosto do motorista ao ser o único a parar. 
a) Formulando essa situação como sendo um jogo na forma estratégica:
						 Motorista 2
	
	
	Parar
	Continuar
	Motorista 1
	Parar
	1, 1
	1 – c, 2
	
	Continuar
	2, 1 – c
	0, 0
L4-7a)
O Serviço de Receita Internacional deve decidir se audita (A) ou não (NA) um pagador de impostos, que, por sua vez, pode escolher sonegar (S) ou não sonegar (NS) a quantia devida de 1. O custo de auditar é c < 1 e a multa caso o pagador seja pego sonegando é ƒ > 0. 
a) Formulando essa situação como sendo um jogo na forma estratégica:
					 Pagador de Impostos
	
	
	S
	NS
	 SRI
	A
	1 + ƒ – c, –1 – ƒ
	1 – c, –1
	
	NA
	0, 0
	1, –1
__________________________________________________________
5.2 Equilíbrio de Nash
Melhor resposta: é a melhor resposta para o jogador i para as estratégias dos demais rivais se
Equilíbrio de Nash: é um conjunto de estratégias tal que, para cada jogador , é a melhor resposta para as estratégias de equilíbrio de outros jogadores . 
Um equilíbrio de Nash é estável tal que, se todos os jogadores revelassem as estratégias para todos os outros, nenhum deles teria incentivo para escolher alguma outra se não a própria.
No Dilema do Prisioneiro, o equilíbrio de Nash ocorre quando ambos confessam. Isso porque em qualquer outro cenário, o jogador que não confessou sempre poderá melhorar sua situação ao o fazer. Com isso, há incentivo para a confissão.
Estratégia Dominante: uma estratégia dominante é uma estratégia para um jogador i que é a melhor resposta para todos os conjuntos de estratégias de outros jogadores. 
A diferença entre uma estratégia dominante e um equilíbrio de Nash é clara: uma estratégia que é parte de um equilíbrio de Nash deve ser a melhor resposta apenas para um conjunto de estratégias dos outros jogadores; a estratégia dominante é a melhor resposta não somente para o equilíbrio de Nash, mas para qualquer outro conjunto de estratégias adotadas pelos outros jogadores. 
_______________________________________________________________________
5.3 Estratégias Mistas
Estratégias mistas são aquelas em que, ao fazer uma escolha, não há certeza sobre se isso causará um ou outro resultado.
Uma estratégia mista para o indivíduo i é uma distribuição de probabilidade sobre os elementos de Si. Assim, mi(si) é a probabilidade de i jogar a estratégia .
Evidentemente, .
Uma estratégia conjunta mista é o conjunto de todas as estratégias mistas. A probabilidade de uma estratégia conjunta é 
Payoffs dadas estratégias mistas – Teorema da Utilidade Esperada
Dadas as estratégias mistas , o payoff do indivíduo i é:
Equilíbrio de Nash com estratégias mistas
O mesmo princípio com estratégias puras se aplica aqui:
Proposição: se em um equilíbrio de Nash as estratégias e são jogadas com probabilidade positiva, então o jogador i é indiferente entre jogar qualquer uma das duas. Isso significa que o payoff esperado deve ser igual para cada uma das estratégias. Caso contrário, ele ganharia jogando a de maior payoff em lugar de jogar a de menor. Essa é a propriedade utilizada para derivar o Equilíbrio de Nash em Estratégias Mistas.
Teorema de Nash: todo jogo com um número finito de agentes e de estratégias tem ao menos um equilíbrio de Nash.
Exemplo: Par ou Ímpar
	
	Par
	Ímpar
	
	Par
	1, -1
	-1, 1
	q
	Ímpar
	-1, 1
	1, -1
	(1 – q)
	
	k
	(1 – k)
	
A probabilidade de ambos jogarem par é k • q, por exemplo.
Se o jogador das linhas (i) aleatoriza, temos que o payoff esperado de ele jogar par deve ser igual ao payoff esperado de ele jogar ímpar:
O payoff esperado de ele jogar par ou ímpar é:
Se o jogador das colunas aleatoriza, temos:
O payoff esperado de ele jogar par ou ímpar é:
Portanto, é equilíbrio de Nash.
Representação gráfica:
__________________________________________________________
5.4 Jogos Sequenciais
São jogos com várias etapas em que a ordem das jogadas importa. A cada uma delas, os jogadores têm informação do que ocorreu nas suas anteriores. 
São tipicamente representados na forma de árvore. Ingredientes:
· Nós: descrevem a sequência de eventos ao longo do jogo. Cada nó (exceto os finais) está associado a um único jogador e às possíveis estratégias que ele pode tomar a partir dali.
· Conjuntos de informação: conjunto de nós tal que o indivíduo que nele joga não informação sobre em que nó está.
· Num conjunto de informação, o mesmo indivíduo está associado a todos os nós;
Os jogos sequenciais também podem ser representados na forma estratégica.
________________________________________________________________
Exemplo: L4-5a) 
Considerar o seguinte jogo:
a) Formulando esse jogo na forma estratégica:
	 		 		 Jogador 2
	
	
	S
	C
	 
	CC
	0, 2
	2, 4
	Jogador 1
	CS
	0, 2
	3, 1
	
	SC
	1, –1
	1, –1
	
	SS
	1, –1
	1, –1
Aqui, o jogador 1 joga duas vezes e o 2, uma. Considera-se, nas linhas, uma combinação de jogadas de 1 e, nas colunas, a única jogada de 2. 
___________________________________________________________________
Equilíbrio de Nash Perfeito em Subjogos
O Equilíbrio de Nash Perfeito em Subjogos nada mais é que um subgrupo dos equilíbrios de Nash. Um Equilíbrio de Nash é também um ENPS se ele é um equilíbrio de Nash em todos os subjogos. 
A melhor forma de encontrar o ENPS é por indução retroativa: resolve-se para o melhor payoff do último subjogo e o substitui-se o subjogo por tal payoff. Com isso, repete-se o mesmo processo até o primeiro nó.
É possível também aleatorizar em subjogos e encontrar o ENPS com estratégias mistas.
Exemplo: 
L4-5
a) Achando o equilíbrio de Nash em estratégias puras no jogo:
 		 		 Jogador 2
	
	
	S
	C
	 
	CC
	0, 2
	2, 4
	Jogador 1
	CS
	0, 2
	3, 1
	
	SC
	1, –1
	1, –1
	
	SS
	1, –1
	1, –1
Para o jogador 1: (linha superior)
· Maior payoff quando 2 joga S: SC ou SS, onde o payoff é 1.
· Maior payoff quando 2 joga C: CS, onde o payoff é 3.
Para o jogador 2: (linha inferior)
· Maior payoff quando 1 joga CC: C, onde o payoff é 4.
· Maior payoff quando 1 joga CS: S, onde o payoff é 2.
· Maior payoff quando 1 joga SC: S ou C, onde o payoff é –1.
· Maior payoff quando 1 joga SS: S ou C, onde o payoff é –1.
Com isso, temos dois equilíbrios de Nash em estratégias puras: (SC, S) e (SS, S)
b) Achando o(s) ENPS:
1)
2)
3)
4) (1,–1) e o caminho até ele foi (SS, S).
Com isso, temos (SC, S) e (SS, S) de Equilíbrios de Nash em estratégias puras e (SS, S) de ENPS.
__________________________________________________________
5.4 Jogos Repetidos
Aqui, parte-se de um jogo estático que se realiza N ou infinitas vezes. Isso implicará a formação de reputação entre os jogadores e, eventualmente, o comprometimento para com os adversários.
Payoff: no caso de N jogos, o payoff pode ser dado pela soma ou pela média de todas as repetições do mesmo.
Exemplo: 
	
	A
	B
	C
	A
	4, 4
	0, 5
	0, 0
	B
	5, 0
	1, 1
	0, 0
	C
	0, 0
	0, 0
	3, 3
Há equilíbrio de Nash em estratégias puras (B, B) e(C, C). (A, A) não é equilíbrio de Nash, mas domina (B, B) e (C, C) em termos de Pareto. 
Vamos supor que há duas repetições. Num primeiro momento, ambos cooperem para jogar A.
- Caso ambos tenham jogado A na primeira, ambos jogam C na segunda.
- Caso contrário, a confiança é quebrada: joga-se B na segunda. 
Nesse jogo, o payoff de desviar é de, no máximo, 5 + 1 = 6. O payoff de cooperar na primeira, no entanto, é de 4 + 3 = 7. Portanto, não vale a pena desviar.
Agora, suponhamos que o jogo tem infinitas repetições. Pode-se repetir A e garantir um payoff igual a 4 sempre, exceto na última repetição.
Proposição: em um jogo com um único equilíbrio de Nash, o único ENPS do jogo repetido N vezes é a repetição do Equilíbrio de Nash no jogo estático. No caso do Dilema dos Prisioneiros, por exemplo, a traição no primeiro jogo leva à traição nas outras repetições.
Jogos Repetidos Infinitas Vezes
Um jogo repetido infinitas vezes pressupõe que, eventualmente, a cooperação terá de ser necessária.
A definição do payoff, nesse caso, dá menos valor ao futuro do que ao presente. Isso tem várias justificativas, sendo duas delas, por exemplo, a inflação e o juros. Para tanto, desconta-se do payoff futuro um fator tal que :
1
(1,–1) (0,2) (3,1)
(2,4)12
S S S
C C C
1
(1,–1) (0,2)
(3,1)2
S S
C C
1
(1,–1)
(0,2)
S
C
1
q
k1
1/2 Equilíbrio de Nash
1/20
1
q
k
1
1/2
EquilíbriodeNash
1/20
(1,–1)
1
1 1
2 2
(1,2)
(3,0)
Conjunto de Informação
Nó
(2,4) (0,5)
(4,–1)
1
(1,–1) (0,2) (3,1)
(2,4)12
S S S
C C C