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