Baixe o app para aproveitar ainda mais
Prévia do material em texto
TEORIA DOS JOGOS Miguel Vazquez Miguel.Vazquez.Martinez@gmail.com 1o Semestre 2015 JOGOS SIMULTÂNEOS – ESTRATÉGIAS MISTAS JOGO EM FORMA ESTRATÉGICA (O NORMAL) Conjunto de jogadores Espaço de estratégias puras de cada jogador O número de estratégias pode ser diferente para cada jogador Espaço total de estratégias puras Supomos que é um conjunto finito. Recompensas de cada jogador , donde é o conjunto de estratégias escolhidas pelos jogadores: 1,2, ,i I iS i iS S ( )iu s s 1( , , )Is s s S 1 2 3, , ,i i i iS s s s JOGO DAS MOEDAS O jogo das moedas (matching pennies) é um exemplo de não existência do equilíbrio de Nash Tem dois jogadores Os espaços de estratégias puras são Recompensas: se ambas as moedas coincidem, o jogador 2 ganha a moeda do jogador 1. Se as moedas não coincidem, o jogador 1 ganha a moeda do jogador 1,2i 1 2 ,S S cara cruz Jugador 1 Jugador 2 (-1,1) (1,-1) (1,-1) (-1,1) cara coroa cara coroa ESTRATÉGIAS MISTAS Estratégia mista: 𝜓, distribuição de probabilidade sobre as estratégias puras Supomos que a aleatorização de cada jogador é uma distribuição independente do resto dos jogadores A recompensa será o valor esperado levando em consideração as probabilidades E.g. 2 jogadores O primeiro tem J estratégias puras e o segundo K 𝑢1 𝜓1 , 𝜓2 = 𝑗=1 𝐽 𝜓1 𝑠1𝑗 𝑘=1 𝐾 𝜓2 𝑠2𝑗 𝑢1 𝑠1𝑗 , 𝑠2𝑘 𝑢2 𝜓1 , 𝜓2 = 𝑘=1 𝐾 𝜓2 𝑠2𝑘 𝑗=1 𝐽 𝜓1 𝑠1𝑗 𝑢2 𝑠1𝑗 , 𝑠2𝑘 ESTRATÉGIAS MISTAS Qual a intuição atrás das estratégias mistas? Harsanyi (1973) – incerteza do jogador 1 sobre a estratégia pura do jogador 2... ...e que depende do que sabe o jogador 2 EXEMPLO Jogador 1 Jogador 2 cara (-1,1) (1,-1) (1,-1) (-1,1)coroa cara coroa q 1 q r 1 r • Os ganhos esperados do jogador 1 são – Se cara: – Se coroa: ( 1) (1 ) (1) 1 2q q q 1 (1 ) ( 1) 2 1q q q 1 2 q 1 2 q 1 2 q Melhor coroase se se Indiferente Melhor cara 𝜓1 = (𝑟, 1 − 𝑟) 𝜓2 = (𝑞, 1 − 𝑞) MELHOR RESPOSTA EM ESTRATÉGIAS MISTAS • Jogador 1 • Nota – supomos que os sucesos são independentes, i.e. a probabilidade de (cara,cara) é rq • A função é crescente em r se e decrescente se • A melhor resposta considerando estratégias puras e mistas é igual a considerar só estratégias puras (2 1) (2 4 )q r q (2 4 ) 0q (2 4 ) 0q 𝑢1 𝜓1 , 𝜓2 = 𝑟𝑞 ∙ −1 + 𝑟 1 − 𝑞 ∙ 1 + 1 − 𝑟 𝑞 ∙ 1 + 1 − 𝑟 1 − 𝑞 ∙ −1 = 2𝑞 − 1 + 𝑟(2 − 4𝑞) UTILIDADE (RECOMPENSA) ESPERADA q 1( )u 1 cara coroa 1 2 1 0 -1 r 2( )u 1 0 -1 cruz coroa 1 1 2 𝑢1 𝜓1 , 𝜓2 𝑢2 𝜓1 , 𝜓2 MELHOR RESPOSTA PARA 1 (NÃO É FUNÇÃO!) r q 0 1 2 1 *( )r q 1cara cruz cruz cara * 1 1/ 2 [0( ,1] 1 2 1/ ) / 0 2 r q q q q EQUILÍBRIO DE NASH EM ESTRATÉGIAS MISTAS Na aula anterior, equilíbrio de Nash em estratégias puras: A generalização direta seria Mas basta comprovar * * *( , ) ( , ) i i i i i i i ii u s s u s s s S ∀𝑖 𝑢𝑖 𝜓𝑖 ∗, 𝜓−𝑖 ∗ ≥ 𝑢𝑖 𝜓𝑖 , 𝜓−𝑖 ∗ ∀𝑖 𝑢𝑖 𝜓𝑖 ∗, 𝜓−𝑖 ∗ ≥ 𝑢𝑖 𝑠𝑖 , 𝜓−𝑖 ∗ PRIMEIRA PARTE DO CASO PRÁTICO Justificar que os equilíbrios obtidos com as duas definições é igual Definição 1 Definição 2 ∀𝑖 𝑢𝑖 𝜓𝑖 ∗, 𝜓−𝑖 ∗ ≥ 𝑢𝑖 𝜓𝑖 , 𝜓−𝑖 ∗ ∀𝑖 𝑢𝑖 𝜓𝑖 ∗, 𝜓−𝑖 ∗ ≥ 𝑢𝑖 𝑠𝑖 , 𝜓−𝑖 ∗ MELHOR RESPOSTA 2 q r 0 1 2 1 *( )q r 1cara cruz cruz cara * 0 1/ 2 [0( ,1] 1 2 1/ ) / 1 2 q r r r r MELHORES RESPOSTAS r q 0 1 2 1 *( )r q 1cara cruz cara *( )q r cruz Agora equilibrio em estratégias mistas BATALHA DOS SEXOS Futebol Ballet Futebol 4 , 2 0 , 0 Ballet 0 , 0 2 , 4 ela ele q 1 q r 1 r BATALHA DOS SEXOS Fútbol Ballet Fútbol 4 , 2 0 , 0 Ballet 0 , 0 2 , 4 ela ele q 1 q r 1 r BATALHA DOS SEXOS Fútbol Ballet Fútbol 4 , 2 0 , 0 Ballet 0 , 0 2 , 4 ela ele q 1 q r 1 r 1( ) 4 (1 ) 0 u rq r q (1 ) 0 r q (1 )(1 ) 2 r q * 0 1/ 3 [0,1] 1/ 1 ) / ( 3 1 3 r q q q q 𝑢1 𝜓 𝑟 = 1 → 𝑢1 𝜓 = 𝑞 ∙ 4 𝑟 = 0 → 𝑢1 𝜓 = 2 − 2𝑞 EQUILÍBRIOS r q 0 2 3 1 *( )r q 1ballet fútbol ballet *( )q r fútbol 1 3 EQUILÍBRIOS r q 0 2 3 1 *( )r q 1ballet fútbol ballet *( )q r fútbol 1 3 EXISTENCIA DEL EQUILIBRIO DE NASH (EN) Teorema de Nash (1950): Em todo jogo com um número finito de jogadores, cada um deles com um número finito de estratégias, existe pelo menos um equilíbrio de Nash, incluindo possivelmente estratégias mistas MELHORES RESPOSTAS E EQUILÍBRIOS DE NASH Pensem num jogo 2×2 A pode escolher entre as ações aA1 e a A 2 B pode escolher entre as ações aB1 e a B 2 Há quatro combinações de ações: (aA1, a B 1), (a A 1, a B 2), (a A 2, a B 1), (a A 2, a B 2) Cada combinação poderá proporcionar recompensas diferentes aos jogadores MELHORES RESPOSTAS E EQUILÍBRIOS DE NASH Suponha que os ganhos de A e B, quando as ações escolhidas forem aA1 e a B 1, sejam: UA(aA1, a B 1) = 6 e U B(aA1, a B 1) = 4 Analogamente, suponha que: UA(aA1, a B 2) = 3 e U B(aA1, a B 2) = 5 UA(aA2, a B 1) = 4 e U B(aA2, a B 1) = 3 UA(aA2, a B 2) = 5 e U B(aA2, a B 2) = 7 MELHORES RESPOSTAS E EQUILÍBRIOS DE NASH UA(aA1, a B 1) = 6 e U B(aA1, a B 1) = 4 UA(aA1, a B 2) = 3 e U B(aA1, a B 2) = 5 UA(aA2, a B 1) = 4 e U B(aA2, a B 1) = 3 UA(aA2, a B 2) = 5 e U B(aA2, a B 2) = 7 24 MELHORES RESPOSTAS E EQUILÍBRIOS DE NASH UA(aA1, a B 1) = 6 e U B(aA1, a B 1) = 4 UA(aA1, a B 2) = 3 e U B(aA1, a B 2) = 5 UA(aA2, a B 1) = 4 e U B(aA2, a B 1) = 3 UA(aA2, a B 2) = 5 e U B(aA2, a B 2) = 7 Se B escolhe a ação aB1, então a melhor resposta de A é ?? 25 MELHORES RESPOSTAS E EQUILÍBRIOS DE NASH UA(aA1, a B 1) = 6 e U B(aA1, a B 1) = 4 UA(aA1, a B 2) = 3 e U B(aA1, a B 2) = 5 UA(aA2, a B 1) = 4 e U B(aA2, a B 1) = 3 UA(aA2, a B 2) = 5 e U B(aA2, a B 2) = 7 Se B escolhe a ação aB1, então a melhor resposta de A é a ação aA1 (pois 6 > 4) 26 MELHORES RESPOSTAS E EQUILÍBRIOS DE NASH UA(aA1, a B 1) = 6 e U B(aA1, a B 1) = 4 UA(aA1, a B 2) = 3 e U B(aA1, a B 2) = 5 UA(aA2, a B 1) = 4 e U B(aA2, a B 1) = 3 UA(aA2, a B 2) = 5 e U B(aA2, a B 2) = 7 Se B escolhe a ação aB1, então a melhor resposta de A é a ação aA1 (pois 6 > 4) Se B escolhe a ação aB2, então a melhor resposta de A é ?? 27 MELHORES RESPOSTAS E EQUILÍBRIOS DE NASH UA(aA1, a B 1) = 6 e U B(aA1, a B 1) = 4 UA(aA1, a B 2) = 3 e U B(aA1, a B 2) = 5 UA(aA2, a B 1) = 4 e U B(aA2, a B 1) = 3 UA(aA2, a B 2) = 5 e U B(aA2, a B 2) = 7 Se B escolhe a ação aB1, então a melhor resposta de A é a ação aA1 (pois 6 > 4) Se B escolhe a ação aB2, então a melhor resposta de A é a ação aA2 (pois 5 > 3) 28 MELHORES RESPOSTAS E EQUILÍBRIOS DE NASH Se B escolhe aB1, então A escolhe a A 1 Se B escolhe aB2, então A escolhe a A 2 A “curva” de melhor resposta de A é: Melhor resposta de A aA1 aA2 aB2a B 1 Ação de B + +MELHORES RESPOSTAS E EQUILÍBRIOS DE NASH UA(aA1, a B 1) = 6 e U B(aA1, a B 1) = 4 UA(aA1, a B 2) = 3 e U B(aA1, a B 2) = 5 UA(aA2, a B 1) = 4 e U B(aA2, a B 1) = 3 UA(aA2, a B 2) = 5 e U B(aA2, a B 2) = 7 MELHORES RESPOSTAS E EQUILÍBRIOS DE NASH UA(aA1, a B 1) = 6 e U B(aA1, a B 1) = 4 UA(aA1, a B 2) = 3 e U B(aA1, a B 2) = 5 UA(aA2, a B 1) = 4 e U B(aA2, a B 1) = 3 UA(aA2, a B 2) = 5 e U B(aA2, a B 2) = 7. Se A escolhe a ação aA1, então a melhor resposta de B é ?? MELHORES RESPOSTAS E EQUILÍBRIOS DE NASH UA(aA1, a B 1) = 6 e U B(aA1, a B 1) = 4 UA(aA1, a B 2) = 3 e U B(aA1, a B 2) = 5 UA(aA2, a B 1) = 4 e U B(aA2, a B 1) = 3 UA(aA2, a B 2) = 5 e U B(aA2, a B 2) = 7. Se A escolhe a ação aA1, então a melhor resposta de B é a ação aB2 (porque 5 > 4) MELHORES RESPOSTAS E EQUILÍBRIOS DE NASH UA(aA1, a B 1) = 6 e U B(aA1, a B 1) = 4 UA(aA1, a B 2) = 3 e U B(aA1, a B 2) = 5 UA(aA2, a B 1) = 4 e U B(aA2, a B 1) = 3 UA(aA2, a B 2) = 5 e U B(aA2, a B 2) = 7. Se A escolhe a ação aA1, então a melhor resposta de B é a ação aB2 (porque 5 > 4) Se A escolhe a ação aA2, então a melhor resposta de B é ?? MELHORES RESPOSTAS E EQUILÍBRIOS DE NASH UA(aA1, a B 1) = 6 e U B(aA1, a B 1) = 4 UA(aA1, a B 2) = 3 e U B(aA1, a B 2) = 5 UA(aA2, a B 1) = 4 e U B(aA2, a B 1) = 3 UA(aA2, a B 2) = 5 e U B(aA2, a B 2) = 7 Se A escolhe a ação aA1, então a melhor resposta de B é a ação aB2 (porque 5 > 4) Se A escolhe a ação aA2, então a melhor resposta de B é a ação aB2 (porque 7 > 3) MELHORES RESPOSTAS E EQUILÍBRIOS DE NASH Se A escolhe aA1 , então B escolhe a B 2 Ação de A a A 1 aA2 aB2a B 1 Melhor resposta de B MELHORES RESPOSTAS E EQUILÍBRIOS DE NASH Se A escolhe aA1 , então B escolhe a B 2 Se A escolhe aA2 , então B escolhe a B 2 Ação de A a A 1 aA2 aB2a B 1 Melhor resposta de B MELHORES RESPOSTAS E EQUILÍBRIOS DE NASH Se A escolhe aA1 , então B escolhe a B 2 Se A escolhe aA2 , então B escolhe a B 2 A “curva” de melhor resposta de B é: Ação de A a A 1 aA2 aB2a B 1 Melhor resposta de B MELHORES RESPOSTAS E EQUILÍBRIOS DE NASH Se A escolhe aA1 , então B escolhe a B 2 Se A escolhe aA2 , então B escolhe a B 2 A “curva” de melhor resposta de B é: Ação de A a A 1 aA2 aB2a B 1 Melhor resposta de B Notem que aB2 é ação estritamente dominante para B MELHORES RESPOSTAS E EQUILÍBRIOS DE NASH Resposta de A aA1 aA2 aB2a B 1 aA1 aA2 aB2a B 1 + + Escolha de A Escolha de B Resposta de B Como as curvas de melhores respostas podem ser usadas para localizar os EN? B A MELHORES RESPOSTAS E EQUILÍBRIOS DE NASH Resposta de A aA1 aA2 aB2a B 1 + + Resposta de B Há equilíbrio de Nash? Sobrepondo-as! MELHORES RESPOSTAS E EQUILÍBRIOS DE NASH aA1 aA2 aB2a B 1 + + Há equilíbrio de Nash? Resposta de A Resposta de B Sim, (aA2, a B 2). Por que? aA2 é melhor resposta a a B 2 aB2 é melhor resposta a a A 2
Compartilhar