Buscar

Teoria_dos_Jogos

Prévia do material em texto

Universidade Federal Fluminense 
Profª. Lídia 1 
DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO – VEP 
PESQUISA OPERACIONAL II 
PROFª. LÍDIA 
 
 Teoria dos Jogos 
 
 
Situações de competição envolvendo dois ou mais oponentes inteligentes, com objetivos 
em conflito. 
Denominam-se de jogadores as N pessoas ou grupos que participam do jogo. 
Associado a cada par de estratégias, existe uma quantidade que um jogador paga ao 
outro, que representam os ganhos do segundo jogador. Tais jogos são denominados 
Jogos de Soma Zero, já um jogador ganha exatamente o que o outro perde. 
As regras e os ganhos de cada jogador de acordo com as estratégias adotadas são 
conhecidos previamente. 
Uma estratégia simples indica a seqüência de lances e contralances que um jogador fará 
ao longo de todo o jogo. 
Representamos um jogo entre dois jogadores A e B com estratégias m e n por uma 
matriz de ganhos: 
 Estratégias de B 
 1 2B B Bn � 
Estratégias de A 
1 11 12 1
2 21 22 2
1 2
A
A
A
n
n
m m m mn
a a a
a a a
a a a
� �
� �
� �
� �
� �� �
� �
�
�
� � � � �
�
 
 
 Esta representação indica que se A usa a estratégia i e B a estratégia j, o pagamento de 
A é aij, o que significa que o pagamento de B é – aij. 
 
Exemplo: Em um jogo em que dois jogadores mostram simultaneamente um, dois ou 
três dedos cada, o jogador II paga ao jogador I a soma do número de dedos mostrados 
pelos dois caso esta seja par (em unidades monetárias). Se a soma for ímpar, é o jogador 
I que paga o valor da soma ao jogador II. 
A matriz de ganhos do jogador I é mostrada a seguir: 
 
 Jogador II 
 1 2 3 
Jogador I 
1 2 3 4
2 3 4 5
3 4 5 6
−� �
� �
− −� �
� �
−� �
 
 Universidade Federal Fluminense 
Profª. Lídia 2 
Solução ótima para Jogos de Soma Zero entre duas pessoas 
 
A solução ótima seleciona uma ou mais estratégias para cada jogador de modo que 
qualquer mudança nas estratégias selecionadas não melhora o pagamento de qualquer 
dos jogadores. Estas soluções podem ser uma estratégia pura ou várias estratégias 
mistas de acordo com probabilidades predeterminadas. 
Exemplo 1: Duas companhias A e B vendem antigripais. A Cia A anuncia em rádio 
(A1), televisão (A2) e jornais (A3). A Cia B usa rádio (B1), televisão (B2), jornais (B3) e 
também mala direta (B4). Dependendo da intensidade da publicidade, cada Cia pode 
captar uma proporção de mercado da outra. A matriz mostra a percentagem do mercado 
ganho ou perdido pela companhia A considerando cada combinação de estratégias de A 
e B. Qual a melhor estratégia de A? E de B? 
 
 1 2 3 4B B B B 
1
2
3
A 8 2 9 3
A 6 5 6 8
A 2 4 9 5
− −� �
� �
� �
� �
− −� �
 
 
A solução do jogo baseia-se em determinar o melhor ganho entre os piores ganhos para 
cada jogador. 
 
 1 2 3 4B B B B Min (linhas) 
 
1
2
3
A 8 2 9 3
A 6 5 6 8
A 2 4 9 5
− −� �
� �
� �
� �
− −� �
 
3
5
9
−
−
 Maximin = 5 
Max (colunas) 8 5 9 8 
 
 Minimax = 5 
 
Se A escolhe A1, sem importar a escolha de B, o pior que pode acontecer é que A perca 
3% da participação do mercado em favor de B. Para A2, a pior hipótese é um ganho de 
5% e para A3 é uma perda de 9%. 
Para B, como a matriz é de pagamentos dados para A, o critério “o melhor do pior” 
requer a determinação do valor Minimax. A solução do jogo pede para selecionar as 
estratégias A2 e B2. Dizemos que o valor do jogo é 5%, com resultado favorável para a 
Cia A. 
A e B usam uma solução de ponto de equilíbrio. 
 
Exemplo 2: Dois jogadores jogam uma moeda. Cada jogador seleciona cara (C) ou 
coroa (K). Ambos os jogadores revelam suas seleções simultaneamente. Se 
concordarem C C ou K K, o jogador A recebe 1 real de B. Caso contrário, A paga 1 real 
a B. 
 Universidade Federal Fluminense 
Profª. Lídia 3 
 C KB B min 
 
C
K
B 1 1
B 1 1
−� �
� �
−� �
 
1
1
−
−
 Max (min) = -1 
 Max 1 1 
 Min (max) = 1 
 
Como os valores não são iguais o jogo não tem solução de estratégia pura. 
Ambos os jogadores devem misturar as suas estratégias aleatoriamente. Neste caso, o 
valor ótimo do jogo acontecerá em algum lugar entre os valores maximin e minimax do 
jogo. 
 
Valor Maximin ≤ Valor do Jogo ≤ Valor Minimax 
 
-1 ≤ Valor do Jogo ≤ 1 
 
Exemplo 3: 
 
 1 2 3 4B B B B Min 
 
1
2
3
4
A 1 9 6 0
A 2 3 8 4
A 5 2 10 3
A 7 4 2 5
� �
� �
� �
� �
− − −
� �� �
− −� �
 
0
2
5
5
−
−
 Maximin = 2 
 Max 7 9 10 4 
 
 Minimax = 4 
 
Valor do Jogo: 2 ≤ v ≤ 4 
 
 
Solução de Jogos de Estratégias Mistas 
 
Podem ser resolvidos de forma gráfica ou mediante programação linear. 
 
a) Método gráfico 
 
Um dos jogadores tem duas estratégias puras. 
 
 
 
 
 
 Universidade Federal Fluminense 
Profª. Lídia 4 
 1 2 ny y y� 
 1 2B B Bn � 
1
11
x
x−
 
11 12 11
21 22 22
A
A
n
n
a a a
a a a
� �
� �
� �
�
�
 
 
O jogo supõe que o jogador A mistura as estratégias A1 e A2 com as probabilidades x1 e 
1 – x1, 0 ≤ x1 ≤ 1. 
O jogador B mistura as estratégias B1 a Bn com as probabilidades y1, y2, ..., yn, onde yj ≥ 
0, j = 1, 2, ..., n e y1 + y2 + ... + yn = 1. Neste caso, o pagamento esperado de A 
correspondente a j-ésima estratégia pura de B é calculado como: 
 
(a1j – a2j) x1 + a2j , j = 1, 2, ..., n. 
 
O jogador A procura determinar o valor de x1 que maximiza os pagamentos esperados 
mínimos, isto é, 
 
( )
1 1 2 1 2x j j j jMax min a a x a� �− +	 
 
 
Exemplo 4: Considere a matriz de pagamentos para o jogador A. 
 
 1 2 3 4B B B B 
1
2
A 2 2 3 1
A 4 3 2 6
−� �
� �
� �
 
 
O jogo não tem uma solução de estratégia pura, devemos misturar as estratégias. 
 
Estratégia pura de B Pagamento esperado de A 
1 1 1 12 4(1 ) 2 4x x x+ − = − + 
2 1 1 12 3(1 ) 3x x x+ − = − + 
3 1 1 13 2(1 ) 2x x x+ − = + 
4 1 1 11 6(1 ) 7 6- x x x+ − = − + 
 
1 1 12 7 6 0,5v x x x= + = − + ∴ = 
Substituímos: v = 0,5 + 2 = 2,5 
 v = (-7) 0,5 + 6 = 2,5 
 
 
A envoltória inferior representa o pagamento esperado mínimo (o pior) para A sem 
importar o que B faça. O Max (o melhor) da envoltória inferior corresponde ao ponto de 
solução maximin, em x1 = 0,5. 
Solução ótima do jogador A pede para misturar A1 e A2 com probabilidade 0,5 e 0,5. 
O valor deste jogo é v = 2,5. 
 Universidade Federal Fluminense 
Profª. Lídia 5 
��
��
�
�
�
�
�
�
�
	
� �
� �
x �
�
�
�
�
�
�
�
�	
�
�
�
��
�
	
�
�
�
�
�
�
�
Valor ótimo do jogo: v *
��
��
�
�
�
�
�
�
�
	
� �
� �
x �
�
�
�
�
�
�
�
�	
�
�
�
��
�
	
�
�
�
�
�
�
�
Valor ótimo do jogo: v *
 
 
Para o jogador B, a mistura ótima é determinar através das estratégias da envoltória 
inferior B3 e B4, assim, y1 = y2 = 0 e y4 = 1 – y3. 
 
Estratégia pura de A Pagamento esperado de B 
1 3 3 33 (1 ) 4 1y y y− − = − 
2 3 3 32 6(1 ) 4 6y y y+ − = − + 
 
A solução ‘o melhor do pior’ para B é o ponto mínimo sobre a envoltória superior das 
duas linhas dadas: 
 
4 y3 – 1 = - 4 y3 + 6 
 
y3 = 7/8v = 4 (7/8) – 1 = 2,5 
 
A solução do jogo requer que o jogador A misture A1 e A2 com probabilidades 0,5 e 0,5 
e que o jogador B misture B3 e B4 com probabilidades 7/8 e 1/8 (Existem probabilidades 
alternativas). 
 
b) Solução do jogo com programação linear 
 
As probabilidades ótimas para o jogador A, xi, i = 1, 2, ..., n, podem ser determinadas 
resolvendo o seguinte problema: 
 
1 2
1 1 1
1 2
, , ,
s.a.
1
0 ; 1,2, ,
i
m m m
x i i i i in i
i= i= i=
m
i
Max min a x a x a x
x x x
x i m
� �� �
 �� �
� �� �
+ + + =
≥ =
� � ��
�
�
 
 Universidade Federal Fluminense 
Profª. Lídia 6 
 
Transformando para problema linear, fazemos: 
 
v = 1 2
1 1 1
, , ,
m m m
i i i i in i
i= i= i=
min a x a x a x� �� �
� �
� � �� 
 
O que implica que: 
 
1
, 1, 2, ,
m
ij i
i=
a x v j = n ≥� � 
 
Logo, o problema para o jogador A pode ser escrito como: 
 
1
1 2
, 1, 2, ,
1
0 1,2, ,
m
ij i
i=
m
i
Max v
s.a.
a x v j n
x x x
x , i m
v irrestrito
≥ =
+ + + =
≥ =
� �
�
�
 
 
As estratégias ótimas para o jogador B, y1, y2, ..., yn, são determinadas resolvendo o 
problema: 
 
1 2
1 1 1
1 2
, , ,
1
0 ; 1,2, ,
j
n n n
y j j j j mj j
j= j= j=
n
j
Min max a y a y a y
s.a.
y y y
y j n
� �� �� �
 �� �
� �� �� �
+ + + =
≥ =
� � ��
�
�
 
 
1
1 2
, 1, 2, ,
1
0 ; 1,2, ,
n
ij j
j=
n
j
Min v
s.a.
a y v i m
y y y
y j n
v irrestrito
≤ =
+ + + =
≥ =
� �
�
�
 
 
Os dois problemas otimizam a mesma variável, o valor do jogo. O PPL de B é o dual de 
A. 
 
Exemplo 5: Resolva o jogo a seguir com programação linear. 
 
 
 Universidade Federal Fluminense 
Profª. Lídia 7 
 1 2 3B B B min 
 
1
2
3
A 3 1 3
A 2 4 1
A 5 6 2
− −� �
� �
− −� �
� �
− −� �
 
-3
-2
-6
 Max (min) = -2 
 max 3 4 2 
 Min (max) = 2 
 
Jogo de estratégia mista: -2 � v � 2 
 
O PPL do jogador A: 
 
1 2 3
1 2 3
1 2 3
1 2 3
1 2 3
3 2 5
4 6
3 2
1
0
Max v
s.a.
x x x v
x x x v
x x x v
x x x
x , x , x
v irrestrito
− − ≥
− + − ≥
− − + ≥
+ + =
≥
 
 
x1 = 0,3945 
x2 = 0,3119 
x3 = 0,2936 
v= 0,9083 
 
O PPL do jogador B: 
 
1 2 3
1 2 3
1 2 3
1 2 3
1 2 3
3 3
2 4
5 6 2
1
0
Min v
s.a.
y y y v
y y y v
y y y v
y y y
y , y , y
v irrestrito
− − ≤
− + − ≤
− − + ≤
+ + =
≥
 
 
y1 = 0,3211 
y2 = 0,0826 
y3 = 0,5963 
v = - 0,9083

Outros materiais