ISSN 2317-3300 A teoria da dualidade e o equilíbrio de Nash Lara Martins Barbosa1, Marcos Antônio da Câmara2, Letícia Ferreira Martins1 UFU - Faculdade de Matemática – Campus Santa Mônica 38408-100, Uberlândia, Minas Gerais E-mail: [email protected], [email protected], [email protected] Palavras-chave: Painéis IC, dualidade, teoria dos jogos, equilíbrio de Nash Resumo: Neste trabalho estudamos a teoria da dualidade da programação linear e sua aplicação na demonstração da existência do equilíbrio de Nash em estratégias mistas para jogos de soma zero com dois jogadores. 1 Introdução 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 linguagem para a descrição de processos de decisões conscientes envolvendo mais do que um indivíduo. Em seu início, a teoria dos jogos chamou pouca atenção. Em 1928, John Von Neumann mudou essa situação ao demonstrar que todo jogo finito de soma zero possui uma solução em estratégias mistas. A demonstração original usava topologia e análise funcional e era difícil de acompanhar. Em 1937, ele forneceu uma nova demonstração baseada no teorema do ponto fixo de Brouwer. Neste trabalho apresentaremos uma demonstração que utiliza a Teoria da Dualidade da Programação Linear. 2 A teoria da dualidade Os problemas duais da programação linear denominados, respectivamente, de PRIMAL e DUAL são: minimizar 𝑄 𝑋 = 𝐶 𝑇 𝑋 sujeito a 𝐴𝑋 ≥ 𝐵 (1) 𝑋≥0 em que 𝐴 = 𝑎𝑖𝑗 𝑚𝑥𝑛 , 𝐵 = 𝑏𝑖 𝑚𝑥 1 , 𝐶 = 𝑐𝑗 maximizar sujeito a 𝑛𝑥 1 , 𝑋 = 𝑥𝑗 𝑛𝑥 1 𝑄𝐷 𝑌 = 𝐵𝑇 𝑌 𝐴𝑇 𝑌 ≤ 𝐶 (2) 𝑌≥0 e 𝑌 = 𝑦𝑖 𝑚𝑥 1 . De outra forma, podemos considerar (2) o PRIMAL e (1) o DUAL. Teorema 1: Se 𝑋 e 𝑌 são soluções viáveis quaisquer, respectivamente, do primal e do dual, então 𝑄 𝑋 ≥ 𝑄𝐷 𝑌 . Corolário 1: Se 𝑋 ∗ e 𝑌 ∗ são soluções viáveis, respectivamente, do primal e do dual, tais que 𝑄 𝑋 ∗ = 𝑄𝐷 𝑌 ∗ , então 𝑋 ∗ e 𝑌 ∗ são soluções ótimas dos seus respectivos problemas. Corolário 2: Se a função objetivo é ilimitada no conjunto das soluções viáveis 𝑆𝑃 do primal, então o conjunto das soluções viáveis 𝑆𝐷 do dual é vazio. Resumindo todas as alternativas de soluções possíveis para o para primal-dual, teremos somente uma das seguintes alternativas: 1 Bolsistas do PET Matemática da UFU – SESu/MEC 2 Tutor do PET Matemática da UFU – SESU/MEC 591 ISSN 2317-3300 PRIMAL DUAL Existe solução ótima 𝑋 ∗ Existe solução ótima 𝑌 ∗ 𝑄 𝑋 ∗ = 𝑄𝐷 𝑌 ∗ 𝑆𝑃 = ∅ 𝑆𝑃 = ∅ 𝑄 𝑋 ∗ → −∞ 𝑆𝐷 = ∅ 𝑄𝐷 𝑌 ∗ → +∞ 𝑆𝐷 = ∅ 3 Teoria dos jogos 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. Um jogo tem os seguintes elementos básicos: existe um conjunto finito de jogadores, representado por 𝐺 = 𝑔1 , 𝑔2 , … , 𝑔𝑛 . Cada jogador possui um conjunto finito 𝑆𝑖 = 𝑠𝑖1 , 𝑠𝑖2 , … , 𝑠𝑖𝑚 𝑖 de opções, denominadas estratégias puras do jogador 𝑔𝑖 , 𝑚𝑖 ≥ 2. Definição 1: Um jogo de soma constante com dois jogadores é um jogo com dois jogadores, comumente denominados jogador linha 𝑔𝑙 e jogador coluna 𝑔𝑐 , com estratégias 𝑆𝑙 = 1, 2, 3, … , 𝑚 e 𝑆𝑐 = 1, 2, 3, … , 𝑛 e matriz de payoff 𝑎𝑖𝑗 , 𝑏𝑖𝑗 , 𝑖 = 1, 2, ⋯ , 𝑚 e 𝑗 = 1, 2, … , 𝑛, em que 𝑎𝑖𝑗 e 𝑏𝑖𝑗 representam os payoffs de cada jogador para as escolhas da estratégia 𝑖 de 𝑔𝑙 e estratégia 𝑗 de 𝑔𝑐 , satisfazendo 𝑎𝑖𝑗 + 𝑏𝑖𝑗 = 𝑐, 𝑐 ∈ ℝ. Vamos considerar o caso particular em que 𝑐 = 0, ou seja, jogos que tem soma zero. Nesse caso, 𝑏𝑖𝑗 = −𝑎𝑖𝑗 . Além disso, vamos considerar o jogo do ponto de vista probabilístico, ou seja, ao invés de escolher um perfil de estratégia pura, o jogador deve escolher uma distribuição de probabilidade sobre suas estratégias puras. Uma estratégia mista 𝒑 = 𝑝1 , 𝑝2 , 𝑝3 , … , 𝑝𝑚 para 𝑔𝑙 é uma distribuição de probabilidade para as estratégias puras desse jogador e uma estratégia mista 𝒒 = 𝑞1 , 𝑞2 , 𝑞3 , … , 𝑞𝑛 é uma distribuição de probabilidade para as estratégias puras desse 𝑛 jogador, em que 𝑚 𝑖=1 𝑝𝑖 = 1, 𝑝𝑖 ≥ 0 e 𝑗 =1 𝑞𝑗 = 1, 𝑞𝑗 ≥ 0. Nesse caso, o payoff esperado para 𝑔𝑙 é 𝑢𝑙 𝒑, 𝒒 = 𝒑𝑇 𝐴𝒒, com 𝐴 = 𝑎𝑖𝑗 𝑚𝑥𝑛 e o payoff esperado para 𝑔𝑐 é 𝑢𝑐 𝒑, 𝒒 = 𝒑𝑇 𝐵𝒒, com 𝐵 = 𝑏𝑖𝑗 𝑚𝑥𝑛 . Definição 2: (Equilíbrio de Nash) Dizemos que um perfil de estratégia mista 𝒑∗ , 𝒒∗ é um equilíbrio de Nash se 𝑢𝑙 𝒑∗ , 𝒒∗ ≥ 𝑢𝑙 𝒑, 𝒒∗ 𝑒 𝑢𝑐 𝒑∗ , 𝒒∗ ≥ 𝑢𝑐 𝒑∗ , 𝒒 , para quaisquer 𝒑 e 𝒒. Isto significa que nenhum jogador sente motivação de trocar sua estratégia mista se o outro não o fizer. Ao utilizar a estratégia 𝒑, o ganho médio mínimo de 𝑔𝑙 é min𝒒 𝑢𝑙 𝒑, 𝒒 e 𝑔𝑙 tentará escolher 𝒑 de forma a maximizar esta quantia, isto é, tentará encontrar um número 𝑀𝑙 > 0 tal que 𝑀𝑙 = max𝒑 min𝒒 𝑢𝑙 𝒑, 𝒒 . Ao utilizar a estratégia 𝒒, a perda média máxima de 𝑔𝑐 é max𝒑 𝑢𝑙 𝒑, 𝒒 e 𝑔𝑐 tentará escolher 𝒒 de forma a minimizar esta quantia, isto é, tentará encontrar um número 𝑀𝑐 > 0 tal que 𝑀𝑐 = min𝒒 max𝒑 𝑢𝑙 𝒑, 𝒒 . Para otimizar ambas as estratégias espera-se que 𝑀𝑙 = 𝑀𝑐 . Mas, isto é possível. Teorema 2 (Minimax de von Neumann) 1 Bolsistas do PET Matemática da UFU – SESu/MEC 2 Tutor do PET Matemática da UFU – SESU/MEC 592 ISSN 2317-3300 Para todo jogo de soma zero com dois jogadores, representado pela matriz de payoffs 𝐴 do jogador linha, sempre existe um perfil de estratégia mista 𝒑∗ , 𝒒∗ satisfazendo max𝒑 min𝒒 𝑢𝑙 𝒑, 𝒒 = 𝑢𝑙 𝒑∗ , 𝒒∗ = min𝒒 max𝒑 𝑢𝑙 𝒑, 𝒒 . Demonstração: O problema de 𝑔𝑙 é encontrar um vetor 𝒑𝑻 = 𝑝1 , 𝑝2 , 𝑝3 , … , 𝑝𝑚 e um número 1 𝑝𝑖 𝑚 𝑀𝑙 tal que 𝐴𝑇 𝒑 ≥ 𝑀𝒍 𝒏𝒙𝟏 , 𝑚 𝑖=1 𝑥𝑖 = 𝑀 , 𝑖=1 𝑝𝑖 = 1 e 𝑝𝑖 ≥ 0. Colocando 𝑥𝑖 = 𝑀 , teremos 𝑙 𝑙 que queremos minimizar, pois queremos maximizar 𝑀𝑙 . Nesse caso, teremos o seguinte PPL: minimizar sujeito a em que 𝑋 𝑇 = 𝑥1 , 𝑥2 , … , 𝑥𝑚 e 1 𝑇 𝑚 𝑖=1 𝑥𝑖 1 =𝑀 𝑙 𝐴𝑇 𝑋 ≥ 1 𝑋≥0 (1) = 1, 1, … , 1 . O problema de 𝑔𝑐 é encontrar um vetor 𝒒𝑻 = 𝑞1 , 𝑞2 , 𝑞3 , ⋯ , 𝑞𝑛 e um número 𝑀𝑐 tal que 𝑞𝑗 1 𝑛 𝑛 𝐴𝒒 ≤ 𝑀𝑐 𝒎𝒙𝟏 , 𝑖=1 𝑦𝑗 = 𝑀 , que 𝑗 =1 𝑞𝑗 = 1 e 𝑞𝑗 ≥ 0. Colocando 𝑦𝑗 = 𝑀 , teremos 𝑐 𝑐 queremos maximizar, pois queremos minimizar 𝑀𝑐 . Nesse caso, teremos o seguinte PPL: maximizar sujeito a em que 𝑌 𝑇 = 𝑦1 , 𝑦2 , … , 𝑦𝑛 e 1 𝑇 𝑛 𝑖=1 𝑦𝑗 = 1 𝑀𝑐 𝐴𝑌 ≤ 1 𝑌≥0 (2) = 1, 1, … , 1 . Os problemas (1) e (2) são duais e, portanto, min 𝑚 𝑖=1 𝑥𝑖 = max 𝑛 𝑖=1 𝑦𝑗 , ou seja, 1 𝑀𝑙 1 =𝑀 ⇒ 𝑐 𝑀𝑙 = 𝑀𝑐 . ∎ Em particular, 𝒑∗ , 𝒒∗ é um equilíbrio de Nash. Além de estabelecer a existência de equilíbrios de Nash, a demonstração sugere uma maneira de encontrá-los: resolvendo-se dois problemas duais da programação linear. Referências [1] D. G. Luenberger, Linear and Nonlinear Programming, Second Edition. Addison-Wesley Publishing Company, 1989. [2] H. V. Machado, Programação Linear, IMPA, Rio de Janeiro, 1975. [3] B. A. Sartini, G. Garbugio, H. J. Bortolossi, P. A. Santos, L. S. Barreto, Uma Introdução à Teoria dos Jogos, II Bienal da SBM, 2004. 1 Bolsistas do PET Matemática da UFU – SESu/MEC 2 Tutor do PET Matemática da UFU – SESU/MEC 593