Jornal Eletrônico de Ensino e Pesquisa de Matemática

(1s.) v. 2 2 (2018): 25–51. c Jeepema–ISSN-2594-6323.

www.dma.uem.br/kit/jeepema

Introdução à teoria dos Jogos

Doherty Andrade (FEITEP) & Thiago Zanko (UEM)

Resumo: O presente texto tem por objetivo apresentar de forma sucinta os fundamentos ele-
mentares da teoria dos jogos e demonstrar o teorema de equilı́brio de Nash cuja demonstração
utiliza o teorema do ponto fixo de Brouwer.

Sumário

1 Introdução 26

2 Definição de jogo 28

3 Exemplos de jogos 28

4 Dominância 31

5 O teorema minimax de von Neumann 35

5.1 Jogo com 2 jogadores e de soma constante . . . . . . . . . . . . . . . . . . . . 35
5.2 Equilı́brio de Nash em estratégias puras . . . . . . . . . . . . . . . . . . . . . . 36

6 Equilı́brio de Nash em estratégias mistas 39

7 O teorema minimax de von Neumann 41

8 O Teorema de Equilı́brio de Nash 45

8.1 A demonstração . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
26 Doherty Andrade (FEITEP) & Thiago Zanko (UEM)

1. Introdução

A teoria dos jogos é a teoria matemática que procura modelar fenômenos em que se pode
observar conflito, isto é, quando dois ou mais agentes interagem com objetivos contrários.
Assim, 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.
A origem da teoria do jogos pode ser situada no século XVIII, até onde se tem co-
nhecimento, por meio de correspondências entre Nicolas Bernoulli e James Waldegrave,
este último analisa um jogo e fornece uma solução no sentido que veremos mais adiante.
No século XIX, Zermello e Borel, separadamente, publicaram diversos trabalhos sobre jo-
gos. Borel achava que a guerra e a economia podiam ser estudadas por meio de jogos
estratégicos.
Em 1928 o matemático John von Neumann demonstrou importantes resultados, em 1944,
junto com o economista Oscar Morgenstern, publicou o livro “The theory of games and
economic behaviour”. O grande salto ocorreu em 1950 com John Forbes Nash Junior, em
1994, juntamente com outros receberam o prêmio Nobel por suas contribuições à teoria dos
jogos.
Os primeiros registros de estudos de um jogo por estratégia mista datam de 1713 no
estudo do jogo Le her (jogo de baralho com um deck de 52 cartas) realizado por James
Waldegrave e descrito por ele em uma carta destinada a Pierre Rémond de Montmort. Em
1838, Augustin Cournot analisou um caso especı́fico de duopólio e ele definiu conceito de
equilı́brio de mercado como a situação em que ambas as empresas agem de forma ótima à
decisão da empresa concorrente.
A Teoria dos Jogos só vai chamar a atenção das ciências sociais em 1944 (em plena
Segunda Guerra Mundial) com o livro Teoria dos Jogos e Comportamento econômico de John Von
Neumann e Oscar Morgenstern. Nessa obra, eles detalharam e especificaram a formulação
de problemas econômicos e a aplicação da teoria dos jogos à economia
Para prosseguirmos com nossa explanação, voltemos a meados do século XVIII quando
Adam Smith publica a obra A Riqueza das Nações. Considerado o pai do liberalismo e
 Introdução à teoria dos Jogos 27

um marco na economia, com uma burguesia emergente e à beira da revolução industrial,

Adam Smith insere conceitos com A Mão Invisı́vel, no qual ele afirma que existiria uma
”mão invisı́vel”que regula os mercados e seus agentes e estabelece uma determinada ordem
originada da interação dos indivı́duos. Independentemente de uma entidade coordenadora
em comum. Ele afirmava ainda que se cada um fizesse o bem para si próprio, o estaria
fazendo também para o coletivo. Em meados da década de 50, século XX, John Forbes Nash,
prova a existência de um jogo cooperativo, ou seja, não há necessidade de sorte para jogá-lo,
e afirma que você tem que fazer o bem para si próprio e para o coletivo simultaneamente.
Por exemplo, o sonegador de impostos está se beneficiando com o valor que pagou a menos
em tributos, mas prejudicou a construção de estradas, hospitais, ferrovias, ou seja, o seu
coletivo. Ele prova então, que todo jogo possui um equilı́brio e ele é único, o que lhe
renderia o Prêmio Nobel de economia de 1994. O trabalho de Nash foi um marco para a
economia e para os conceitos matemáticos da Teoria dos Jogos da época, principalmente,
porque era o perı́odo da Guerra Fria e buscava-se muito a compreensão da Teoria dos Jogos
e como aplicá-la. Ele ainda formulou o problema da barganha e fez uma ampla contribuição
para os jogos cooperativos e não cooperativos.
O tema de modelagem matemática em finanças é fascinante e possui aspectos interdis-
ciplinares que relacionam algumas das principais contribuições cientı́ficas do século XX.
Dentre elas, citamos como exemplo:

• A metodologia de Arrow-Debreu que está associada ao prêmio Nobel em Economia

de Kenneth Arrow (1972) e o de Gerard Debreu (1983).

• A teoria de precificação por princı́pios de não-arbitragem e de cobertura de cartei-

ras e que leva a equação de Black-Scholes. Esta última contribuição está associada
ao prêmio Nobel de 1997 para Robert Merton e Myron Scholes também na área de
Economia.

• A fórmula de Feynman-Kac que aqui novamente, temos uma referência ao célebre

matemático aplicado Marc Kac em conexão com o fı́sico Richard P. Feynman ganhador
28 Doherty Andrade (FEITEP) & Thiago Zanko (UEM)

do prêmio Nobel de Fı́sica de 1965.

Na próxima seção apresentamos a definição matemática de jogo e damos alguns exem-

plos.

2. Definição de jogo

Um jogo é uma terna ( G, S, U ), onde G = {g1 , g2 , . . . , gn } denota um conjunto finito de

jogadores gi , S é o conjunto das estratégias de cada jogador S = {S1 , S2 , . . . , Sn } e Si =
{si1 , si2 , . . . , simi } são opções de decisões do jogador gi , denominadas de estratégias puras, e
U é o conjunto das funções utilidades de cada jogador U = {u1 , u2 , . . . , un } em que cada ui
está definida por
ui : S → R
s 7→ u i (s)
Qn
onde S = i=1 Si é o espaço das estratégias puras. Um elemento s ∈ S é denominado um
perfil de estratégias puras
s = {s1j1 , s2j2 , . . . , snjn }.

Note que ui (s) associa a cada perfil de estratégias puras um ganho (payoff ) do jogador gi
quando os jogadores utilizaram as suas estretégias puras apresentadas em s.

3. Exemplos de jogos

Apresentamos a seguir alguns exemplos simples que ilustram os problemas tratados na

teoria dos jogos.

• Exemplo 3.1 (Dilema do prisioneiro)

Este é um dos exemplos mais conhecidos, foi formulado por Albert W. Tucker em 1950.
Dois ladrões, Al e Bob, são capturados e acusados do mesmo crime. Presos em selas
separadas e sem comunição entre si, o delegado faz a eles a seguinte proposta: cada um
pode escolher entre confessar e negar o crime. Se nenhum deles confessar, então ambos
 Introdução à teoria dos Jogos 29

terão uma pena de um ano de prisão. Se os dois confessarem, então ambos terão pena de
cinco anos. Mas se um confessar e o outro negar, então o que confessou será libertado e o
outro será condenado a dez anos de prisão.
Neste exemplo, temos:

Jogadores Estratégias
Al S1={confessar, negar}
Bob S2={confessar, negar}

O conjunto das estratégias S puras é o produto cartesiano S1 × S2 das estratégias de

cada um dos jogadores

S = {(confessar, confessar), (confessar, negar), (negar, confessar), (negar, negar)}.

As duas funções utilidades são

u Al : S → R, u Bob : S → R
(c, c) 7→ −5 (c, c) 7→ −5
(c, n) 7→ 0 (c, n) 7→ −10
(n, c) 7→ −10 (n, c) 7→ 0
(n, n) 7→ −1 (n, n) 7→ −1

É usual representar os payoffs em uma tabela

BOB
confessar negar
AL confessar (-5,-5) (0,-10)
negar (-10,0) (-1,-1)

Vamos analisar este jogo do ponto de vista do Al. Duas situações podem ocorrer com
relação ao Bob: confessa ou não confessa. Se Bob confessa, então é melhor Al confessar
também. Se Bob não confessa, então Al ficará livre se confessar. Em qualquer caso, é
melhor Al confessar.
30 Doherty Andrade (FEITEP) & Thiago Zanko (UEM)

Do mesmo modo, vamos alisar o jogo do ponto de vista de Bob. Duas situações podem
ocorrer com relação ao Al: confessa ou não confessa. Se Al confessa, então é melhor Bob
confessar também. Se Al não confessa, então Bob ficará livre se confessar. Em qualquer
caso, é melhor Bob confessar.
Pensando assim, ambos ficarão presos por cinco anos.

• Exemplo 3.2 (Guerra dos sexos)

Um casal deseja sair para passear. O homem prefere assitir a um jogo de futebol enquanto
a mulher prefere ir ao cinema. Ambos indo ao futebol ou ao cinema, apenas um deles terá
maior satisfação; mas se sairem sozinhos então ambos ficarão igualmente insatisfeitos.
Esta situação se adequa ao um jogo estratégico em que o conjunto de jogadores é
G = {homem, mulher}, as estratégias do homem S H = {futebol, cinema} e as estratégias
da mulher S M = {futebol, cinema}. Assim, o conjunto S das estratégias é

S = {(futebol, futebol), (futebol, cinema), (cinema, futebol), (cinema, cinema)}.

As duas funções utilidade u H e u M estão descritas pela seguinte matriz dos payoffs

Mulher
futebol cinema
Homem futebol (10,5) (0,0)
cinema (0,0) (5,10)

• Exemplo 3.3 (matching pennies)

Neste jogo, dois jogadores exibem, ao mesmo tempo, a moeda que cada um esconde na sua
mão. Se ambas apresentam cara ou coroa, o segundo jogador dá sua moeda ao primeiro
jogador. Se ambos forem distintas, isto é, uma apresenta cara e o outro coroa, o primeiro
jogador dá sua moeda ao segundo.
As duas funções utilidade estão descritas pela seguinte matriz dos payoffs
 Introdução à teoria dos Jogos 31

g1
s21 s22
g2 s11 (1,-1) (-1,1)
s12 (-1,1) (1,-1)

• Exemplo 3.4 (Caso da perfuração dos poços de petróleo)

As empresas XY e WZ ganham a licitação para a perfuração e exploração de um poço

de petróleo P. Ambas devem iniciar suas atividades simultaneamente. Há duas opções
de tubulação: a estreita, de custo de 1 (um) milhão de dólares e a larga ao custo de 5
(cinco) milhões de dólares. Ora, se XY e WZ acordarem em gastar menos, as duas instalam
a tubulação estreita e extraem a mesma quantidade de petróleo. Mas se uma das duas
decidirem colocar a tubulação larga para extrair mais petróleo e mais rápido, será benefici-
ada caso a outra mantenha a estreita. Mas se ambas tiverem o mesmo raciocı́nio, gastarão 5
(cinco) milhões e ao final vão extrair a mesma quantidade cada, mas com 4 (quatro) milhões
de dólar a mais de custo.
As estratégias são:

SXY × SWZ = {(estreita,estreita); (estrita,larga); (larga,estreita); (larga,larga)}.

A Matriz de payoffs é dada por:

Perfuradora XY
larga estreita
Perfuradora WZ larga (-5,-5) (-5,-1)
estreita (-1,-5) (-1,-1)

4. Dominância

Vamos denotar por s−i um perfil de estratégia em que a estratégia do jogador gi foi
retirada, isto é,
s−i = {s1j1 , s2j2 , . . . , s(i−1) ji−1 , s(i+1) ji+1 , . . . , snjn }S−i
32 Doherty Andrade (FEITEP) & Thiago Zanko (UEM)

e por S−i = S1 × · · · Si−1 × Si+1 × Sn .

Deste modo, um perfil de estratégia pura pode ser convenientemente representado por
s = (sij , s−i ).
Pelo par (siji , s−i ) representamos

(s1j1 , s2j2 , . . . , s(i−1) ji−1 , siji , s(i+1) ji+1 , . . . , snjn ).

Dizemos que uma estratégia pura sik do jogador gi é estritamente dominada pela es-
tratégia sik ′ se
ui (sik ′ , s−i ) > ui (sik , s−i ),

para todo s−i ∈ S−i .

A estratégia pura sik do jogador gi é fracamente dominada pela estratégia sik ′ se

ui (sik ′ , s−i ) ≥ ui (sik , s−i ),

para todo s−i ∈ S−i .

Chamamos de dominância estrita iterada ao processo em que, sequencialmente, se elimi-
nam as estratégias estritamente dominadas.
Uma solução estratégica ou equilı́brio de Nash de um jogo é um ponto onde cada joga-
dor não tem incentivo de mudar sua estratégia se os demais jogadores não o fizerem. Em
termos matemáticos, um perfil de estratégia pura

s∗ = (s∗1 , s∗2 , . . . , s∗(i−1) , si∗ , s∗(i+1) , . . . , s∗n ) ∈ S

é um equilı́brio de Nash se
ui (si∗ , s−i
∗ ∗
) ≥ ui (siji , s−i )

quando i = 1, 2, . . . , n e para todo ji = 1, 2, . . . , mi , com mi ≥ 2.

No dilema dos prisioneiras, o perfil de estratégias (confessar, confessar) é um equilı́brio
de Nash. Na batalha dos sexos, (futebol futebol) e( cinema, cinema) são únicos equilı́brios.
No jogo de combinar moedas não há equilı́brio de Nash.
 Introdução à teoria dos Jogos 33

Uma alternativa para estes casos é considerar o jogo de ponto de vista probabilı́stico,
isto é, ao invés de escolher um perfil de estratégia pura, o jogador deve escolher uma
distribuição de probabilidades sobre suas estratégias puras.
Uma estratégia mista pi para o jogador gi ∈ G é uma distribuição de probabilidades
sobre o conjunto Si de estratégias puras do jogador, isto é, pi é um elemento do conjunto
∆ mi ,
mi
X
mi
∆mi = {( x1 , x2 , . . . , xmi ) ∈ R ; x1 , ≥ 0, x2 , ≥ 0, . . . , xmi ≥ 0 e xk = 1}.
k=1
Note que ∆mi é um conjunto compacto e convexo.
O espaço de todos os perfis de estratégia mista é o produto cartesiano

∆ = ∆m1 × ∆m−2 × · · · × ∆mn ,

denominado de espaço de estratégia mista. Um vetor p ∈ ∆ é denominado de um perfil de

estratégia mista.
Como no caso de estratégias puras, usamos a notação p−i para representar as estratégias
de todos os jogadores, com exceção do jogador gi .
Note que ∆ é compacto e convexo, pois é produto de compactos e convexos.
Cada perfil de estratégia mista p = (p1 , p2 , . . . , pn ) ∈ ∆ determina um payoff esperado,
uma média dos payoffs ponderada pelas distribuições de probabilidades p1 , p2 , . . . , pn .
Mais precisamente,

p = (p1 , p2 , . . . , pn ) = ( p11 , p12 , . . . , p1n ; p21 , p22 , . . . , p2n ; . . . ; pn1 , pn2 , . . . , pnmn )

então
m2
m1 X mn n
!
X X Y
u i (p) = ··· pkjk ui (s1j1 , s2j2 , . . . , snjn .
j1 =1 j2 =1 jn =1 k=1

(0) (0)
Sejam Si = Si e ∆mi = ∆mi . Defina recursivamente,

(n) (n−1) (n−1) (n−1)

Si = {s ∈ Si ; 6 ∃p ∈ ∆ mi tal que ∀s−i ∈ S−i , ui (p, s−i > ui (s, s−i )}
34 Doherty Andrade (FEITEP) & Thiago Zanko (UEM)

(n) (n)
∆mi = {p = ( p1 , p2 , . . . , pmi ) ∈ ∆mi ; ∀k = 1, 2, . . . , mi , pk > 0 somente se sik ∈ Si },

onde ui (p, s−i ), por abuso de notação, representa o payoff esperado quando o jogador gi
escolhe a estratégia mista p e os demais jogadores escolhem as estratégias mistas corres-
pondentes as estratégias puras dadas por s−i . A interseção
∞
(∞) \ (n)
Si = Si
n=0

é o conjunto das estratégias puras e

(∞) (∞)
∆mi = {p ∈ ∆mi ; 6 ∃p ′ ∈ ∆mi talque ∀s−i ∈ S−i ui (p ′ , s−i ) > ui (p, s−i )},

é o conjunto de todas as estratégias mistas do jogador gi que sobreviveram a técnica da

dominância estrita iterada.

Definição 4.1 (Equilı́brio de Nash) Dizemos que um perfil de estratégia mista

p∗ = (p∗1 , p∗1 , . . . , p∗n ) ∈ ∆ = ∆mi × ∆m2 × · · · × ∆mn

é um equilı́brio de Nash se
ui (pi∗ , p−i
∗ ∗
) ≥ ui (pi , p−i )

para todo pi ∈ ∆mi , isto é, nenhum jogador se sente motivação de trocar sua estratégia mista se os
demais jogadores são o fizerem.

• Exemplo 4.2

No dilema do prisioneiro, o perfil de estratégia mista p∗ = (1, 0; 1, 0) é um equilı́brio de

Nash, pois

u1 (p, p∗ ) = u1 ( p, 1 − p; 1, 0) = 5p − 10 ≤ u1 (1, 0; 1, 0) = u1 ( p∗1 , p∗2 ),

 Introdução à teoria dos Jogos 35

para todo p = (1 − p, p) ∈ ∆2 e

u2 (p∗1 , q) = u1 (1, 0; q, 1 − q) = 5q − 10 ≤ u2 (1, 0; 1, 0) = u2 ( p∗1 , p∗2 ),

para todo q = (1 − q, q) ∈ ∆2 .
Note que este equilı́brio corresponde ao equilı́brio em estratégias
puras s∗ = (confessar, confessar).

5. O teorema minimax de von Neumann

5.1. Jogo com 2 jogadores e de soma constante. Um jogo com dois jogadores, gl cha-
mado jogador linha (com m estratégias) e gc chamado jogador coluna (com n estratégias) e
matriz de payoffs dado por

gc
1 2 ··· n
1 ( a11 , b11 ) ( a12 , b12 ) ( a1n , b1n )
gl 2 ( a21 , b21 ) ( a22 , b22 ) ( a2n , b2n )
.. .. .. ..
. . . ··· .
m ( am1 , bm1 ) ( am2 , bm2 ) ( amn , bmn )

satisfazendo aij + bij = c, para todo i = 1, 2, . . . , m e todo j = 1, 2, . . . , n é dito um jogo de

soma constante. No caso em que c = 0 o jogo é dito de soma zero.
Note que, nesse caso, conhecendo-se a matriz dos payoffs do jogador g1 também se
conhece a matriz dos payoffs do jogador g2 , pois bij = c − aij .
Se A é a matriz dos payoffs do jogador g1 e B é a matriz dos payoffs do jogador g2 , então
A + B = C, a matriz com todas as entradas iguais a c.
Se p = ( p1 , p2 , . . . , pm ) ∈ ∆m é uma distribuição de probabilidade para as estratégias
puras do jogador linha e se q = (q1 , q2 , . . . , qn ) ∈ ∆n é uma distribuição de probabilidade
36 Doherty Andrade (FEITEP) & Thiago Zanko (UEM)

para as estratégias puras do jogador coluna, então o payoff esperado para o jogador linha é
  
a11 a12 · · · a1n q1
m X n
  
X h i  a21 a22 · · · a2n   q2 
ul (p, q) = pi q j aij = p1 p2 · · · pm   = pT Aq.
  
 · · · · · · · · · · · ·   ... 

i=1 j=1
..
  
am1 am2 . amn qn
De modo análogo,
uc (p, q) = pT Bq.
Como o jogo tem soma constante,

A + B = [ aij + bij ] = [c] = c[1],

onde [1] denota a matriz m × n formada com 1 em todas as suas entradas.

PP PP
Notando que ul ( p, q) = pi q j aij = p T Aq obtemos uc ( p, q) = pi q j bij = p T Bq =
p T (C − A)q = c − ul ( p, q). Assim, temos:

Lema 5.1 uc ( p, q) = c − ul ( p, q).

Lema 5.2 Vale a seguinte propriedade

ul (p∗ , q∗ ) ≥ ul (p, q∗ ) ⇔ uc (p∗ , q∗ ) ≤ uc ( p, q∗ ).

Demonstração: Note que uc (p∗ , q∗ ) = c − ul (p∗ , q∗ ) ≤ c − ul (p, q∗ ) = uc (p, q∗ ).

Para a recı́proca, ul (p∗ , q∗ ) = c − uc (p∗ , q∗ ) ≥ c − uc (p, q∗ ) = ul (p, q∗ ).
Isto conclui a demonstração. 

5.2. Equilíbrio de Nash em estratégias puras. Dizemos que aij da matriz A é um ponto
de sela se ele for simultaneamente um mı́nimo em sua linha e um máximo em sua coluna.
Isto é,

aij ≥ ail , ∀l = 1, 2, . . . , n
aij ≥ akj , ∀k = 1, 2, . . . , m.
 Introdução à teoria dos Jogos 37

Teorema 5.3 O elemento aij é um elemento de sela de A se, e somente se, o par (i, j) é um equilı́brio
de Nash em estratégias puras para o jogo.

Demonstração: Suponha que o ponto aij seja um ponto de sela de A. Como aij é um máximo
na coluna, tem-se
ul (i, j) = aij ≥ akj = ul (k, j), ∀k = 1, 2, . . . , m.

Isto é, o jogador linha não pode aumentar o seu payoff se o jogador coluna mantiver a
estratégia.
Por outro lado, como aij é mı́nimo em sua linha, vale que

uc (i, j) = bij = c − aij ≥ c − ail = bil = uc (i, l )

para todo l = 1, 2, . . . , n. Isto é, o jogador coluna não pode aumentar o seu payoff se o
jogador linha mantiver a estratégia.
Se (i, j) é um equilı́brio de Nash para o jogo, é fácil ver que aij é uma máximo em sua
coluna e um mı́nimo em sua linha e portanto, é um ponto de sela. 

Teorema 5.4 Se aij e ars são pontos de sela de A, então ais e arj também são pontos de sela e além
disso,
aij = ars = ais = arj .

Demonstração: Considere a matriz dos payoffs A = [ aij ]. Como aij e ars são selas segue que

aij ≤ ais ≤ ars

e
aij ≥ arj ≥ ars .

Donde segue a igualdade e a conclusão. 

Notação: ak = min akl , mı́nimo na linha k e al = max akl , máximo na coluna k. Assim, o
1≤l ≤n 1≤k≤m
payoff mı́nimo do jogador coluna, se escolher a coluna l, é dado por c − al .
38 Doherty Andrade (FEITEP) & Thiago Zanko (UEM)

Defina

vl ( A) = max ak = max min akl

1≤k≤m 1≤k≤m 1≤l ≤n
vc ( A) = min al = min max akl .
1≤l ≤n 1≤l ≤n 1≤k≤m

Teorema 5.5 Vale sempre a desigualdade vc ( A) ≥ vl ( A).

Demonstração: É claro que akj ≥ min akl , ∀k = 1, . . . , m ∀l = 1, . . . , n. Tomando o máximo

1≤l ≤n
em k nessa expressão temos max akj ≥ max min akl = vl ( A), ∀ j.
1≤k≤m 1≤k≤m 1≤l ≤n
Agora tomando o mı́nimo em j, min max akj ≥ vl ( A), ∀ j, isto é, vc ( A) ≥ vl ( A). 
1≤ j≤n 1≤k≤m

Teorema 5.6 Uma matriz A tem ponto de sela, se e somente se, vl ( A) = vc ( A).

Demonstração: Suponha que aij seja ponto de sela da matriz A. Então, aij = min ail = ai .
1≤l ≤n
como vl ( A) = max ak segue quevl ( a) ≥ ai = aij .
1≤k≤m
Po outro lado, aij = max akj = a j e como vc ( A) = min −1 ≤ l ≤ nal segue que
a≤k≤m

vc ( A) ≤ a j ≤ aij .

Combinando, obtemos que vl ( A) ≥ vc ( A). Do teorema anterior, segue a igualdade.

Suponha que exista linha i tal que vl ( A) = ai . Mas como ai = min1≤s≤n ais , existe coluna
l tal que ai = ail . Assim, vl ( A) = ai = ail .
Do mesmo modo, vc ( A) = akj para algum k e algum i.
Como vl ( A) = vc ( A) temos que ail = akj donde segue que aij é ponto de sela. 

Assim, em um jogo de dois jogadores e com soma constante dado por uma matriz de
payoffs A do jogador linha tem um equilı́brio de nash em estratégias puras se, e somente
se, vl ( A) = vc ( A).
 Introdução à teoria dos Jogos 39

6. Equilı́brio de Nash em estratégias mistas

Definimos as seguintes funções

vl ( A) = max min pT Aq e vc ( A) = min max pT Aq.

p∈∆m q∈∆n q∈∆n p∈∆m

Como no caso de estratégias puras, tem-se:

Teorema 6.1 Vale sempre a desigualdade vc ( A) ≥ vl ( A).

Demonstração: Temos que para todo p ∈ ∆m ,

pT Aq ≥ min pT Ay.
y∈ ∆ m

Assim,
max pT Aq ≥ max min pT Ay = vl ( A).
p∈ ∆ m p∈ ∆ m y∈ ∆ m

Consequentemente,

vc ( A) = min max pT Aq ≥ max min pT Ay = vl ( A).

q∈ ∆ n p∈ ∆ m p∈ ∆ m y∈ ∆ m

Isto completa a demonstração. 

O resultado a seguir, é um teorema que caracteriza a existência de equilı́brios de Nash

em estratégias mistas em termos de vl e vc .

Teorema 6.2 Um perfil de estratégias mistas (p∗ , q∗ ) é um equilı́brio de Nash de um jogo com dois
jogadoes e com soma constante definido pela matriz de payoffs do jogador linha se, e somente se,
tem-se vl ( A) = vc ( A) = p∗ T Aq∗ .

Demonstração: Se (p∗ , q∗ ) é um equilı́brio de Nash, então

T
p∗ Aq∗ = ul (p∗ , q∗ ) ≥ ul (p, q∗ ) = pT Aq∗ ,
40 Doherty Andrade (FEITEP) & Thiago Zanko (UEM)

para todo p ∈ ∆m . Em particular,

p∗ T Aq = max pT Aq∗ ≥ min max pT Ay = vc ( A).

p∈ ∆ m y∈∆n p∈∆m

Vale também que

p∗ T Aq = c − uc (p∗ , q∗ ) ≤ c − uc (p∗ , q) = p∗ T Aq

para todo q ∈ ∆n . Em particular,

p∗ T Aq∗ = min p∗ T Aq = vl ( A).

q∈ ∆ n

Assim, obtemos que vl ( A) ≥ vc ( A). Agora a igualdade segue do teorema.

Agora suponha que vl ( A) = maxp∈∆m minq∈∆m pT Aq, então existe p∗ ∈ ∆m tal que
vl ( A) = minq∈∆n p∗ T Aq.
Analogamente, como vc ( A) = minq∈∆n maxp∈∆m pT Aq, então existe q∗ ∈ ∆n tal que
vc ( A) = maxp∈∆m pT Aq∗ .
Como por hipótese, vc ( A) = vl ( A), temos que

min p∗ T Aq = vl ( A) = vc ( A) = max pT Aq∗ .

q∈ ∆ m p∈ ∆ m

Afirmamos que (p∗ , q∗ ) é um equilı́brio de Nash do jogo. Com efeito,

ul (p∗ , q∗ ) = p∗ T Aq∗ ≥ min p∗ T Aq = max pT Aq∗ ≥ xT Aq∗ = ul (xT , q∗ )

q∈ ∆ n p∈ ∆ m

para todo x ∈ ∆m . Por outro lado,

uc (p∗ , q∗ ) = c − p∗ T Aq∗ ≥ c − max pT Aq∗ = c − min p∗ T Aq ≥ c − x∗ T Ay = uc (p∗ , y)

p∈ ∆ m q∈ ∆ n

para todo y ∈ ∆n .
Deste modo,(p∗ , q∗ ) é um equilı́brio de Nash do jogo. 
 Introdução à teoria dos Jogos 41

7. O teorema minimax de von Neumann

O próximo teorema estabelece que, para jogos de dois jogadores e com soma zero, sem-
pre vl ( A) = vc ( A). Sendo assim, pelo teorema 6.2, para esta classe de jogos, existe sempre
ao menos um equilı́brio de Nash em estratégias mistas. Além disso, o teorema a seguir dá
um método para determinar o equilı́brio de Nash.

Teorema 7.1 (MiniMax de von Neumann) Para todo jogo de soma zero com dois jogadores, re-
presentado pela matriz de payoffs de A do jogador linha, sempre existe um perfil de estratégia mista
(p∗ , q∗ ) ∈ ∆m × ∆n satisfazendo

vl ( A) = max min pT Aq = p∗ T Aq∗ = min max pT Aq = vc ( A).

p∈ ∆ m q∈ ∆ n q∈ ∆ n p∈ ∆ m

Em particular, (p∗ , q∗ ) é um equilı́brio de Nash do jogo.

A demonstração deste resultado que apresentamos a seguir utiliza um importante re-

sultado da programação linear, o teorema da dualidade.
Dado um problema de programação linear, chamado de primal,
 T
 Maximizar b y

(primal) sujeito a Ay ≤ c,


y≥0

o seu dual é dado por


T
 Minimizar c x

(dual) sujeito a x T A ≥ b T , .


x≥0

Teorema 7.2 (dualidade) O problema primal possui solução se, e somente se, o problema dual
possui solução. Além disso, se y∗ é solução do problema primal e x ∗ é solução do problema dual,
então ambos os problemas possuem o mesmo valor ótimo, isto é, c T x ∗ = b T y∗ .
42 Doherty Andrade (FEITEP) & Thiago Zanko (UEM)

Demonstração: (Teorema 7.1)A demonstração consiste em introduzir os seguintes proble-

mas de programação linear, onde c = (1, 1, . . . , 1) T e b = (1, 1, . . . , 1) T e
 T
 Maximizar b y

(primal) sujeito a Ay ≤ c,


y≥0

o seu dual é dado por 

T
 Minimizar c x

(dual) sujeito a x T A ≥ b T , .


x≥0
O problema dual tem solução x ∗ 6= 0 e o primal tem solução y∗ 6= 0. Como c T x ∗ = b T y∗ ,
definimos

Θ = c T x ∗ = b T y∗ > 0.

Note que Θ > 0, pois (0, 0, . . . , 0) não é admissı́vel.

Tome
x∗ y∗
p∗ = e q∗ = .
Θ Θ
Afirmamos que p∗ T Aq∗ = Θ−1 .
De fato,

x∗ T A ≥ b T ⇒ x∗ T Ay∗ ≥ b T y∗ = Θ
Ay∗ ≤ c ⇒ x∗ T Ay∗ ≤ c T x ∗ = Θ.

Segue que x∗ T Ay∗ = Θ. Dividindo por Θ2 , obtemos

!  
x∗ T y∗
A = Θ−1 .
Θ Θ

Isto é, p∗ T Aq∗ = Θ−1 .

Agora vamos provar que (p∗ , q∗ ) é um equilı́brio de Nash.
 Introdução à teoria dos Jogos 43

Notemos que p∗ ∈ ∆m e que q∗ ∈ ∆n , pois são não negativos e

X X x∗ cT x∗ Θ
i
pi = = = =1
Θ Θ Θ
X X y∗j b T y∗ Θ
qj = = = = 1.
Θ Θ Θ
Como x ∗T A ≥ b T (dual) obtemos x ∗T Aq ≥ b T q = 1, para todo q ∈ ∆n . Logo,

Θp∗ T Aq ≥ 1 ⇒ p∗ T Aq ≥ Θ−1 = p∗ T Aq∗ .

Como Ay∗ ≤ c (primal) obtemos pT Aq∗ ≥ pT c = 1, para todo p ∈ ∆m . Logo,

ΘpT A (q∗ Θ) ≤ 1 ⇒ pT Aq∗ ≤ Θ−1 .

Donde obtemos que

ul (p∗ , q∗ ) = p∗ T Aq∗ ≥ pT Aq∗ = ul ( p, q∗ ),

assim, o jogador linha não pode aumentar o seu payoff esperado trocando p∗ por p se o
jogador coluna não mudar a sua estratégia.
Por outro lado, como o jogo é de soma zero

uc (p∗ , q∗ ) = −ul (p∗ , q∗ ) ≥ −ul (p∗ , q) = uc (p∗ , q),

assim o jogador coluna não aumenta o seu payoff quando troca q∗ por q se o jogador linha
mantiver p∗ .
Logo,(p∗ , q∗ ) é um equilı́brio de Nash. 

• Exemplo 7.3 (Vacinação)

O governo deseja vacinar seus cidadãos contra um certo tipo de virus da gripe. Este virus
possui dois sorotipos, sendo que é desconhecida a proporção na qual os dois sorotipos
ocorrem na população di virus. Foram desenvolvidos duas vacinas em que a eficácia da
44 Doherty Andrade (FEITEP) & Thiago Zanko (UEM)

vacina 1 é 85% contra o sorotipo I e de 70% contra o sorotipo II. A eficácia da vacina 2 é de
60% contra o sorotipo I ede 90% contra o sorotipo II. Que polı́tica de vacinação deveria ser
tomada pelo governo?

A situação pode ser modelada como um jogo de soma zero com dois jogadores, o nde
o jogador linha, que é o governo, deseja fazer a compensação (a fração dos cidadãos resis-
tentes ao virus ) o maior possı́vel e o jogador coluna (o virus) deseja fazer a compensação a
menor possı́vel. A matriz dos payoffs é a seguinte:

Virus
Sorotipo I Sorotipo II
Governo Vacina I (0.85, −0.85) (0.70, −0.70)
Vacina II (0.60, −0.60) (0.90, −0.90)

Para encontrar um equilı́brio de Nash, devemos resolver os seguintes problemas de

programação linear (primal)

Maximizar (y1 + y2 )
" #" # " #
0.85 0.70 y1 1
sujeito a ≤
0.60 0.90 y2 1
y1 ≥ 0
y2 ≥ 0

e o seguintes problema de programação linear (dual)

Minimizar ( x1 + x2 )
" #
h i 0.85 0.70 h i
sujeito a x1 x2 ≥ 1 1
0.60 0.90
 Introdução à teoria dos Jogos 45

x1 ≥ 0
x2 ≥ 0

A solução do problema primal é dada por

40 50
y∗ = ( , )
69 69
e a solução do problema dual é
20 10
x ∗ = ( , ).
23 23
Segue que θ = y∗1 + y∗2 = x1∗ + x2∗ = 30
23 . Deste modo, o único equilı́brio de Nash para o
x∗ 2 1 y∗ 4 5
problema é da pelo ponto ( p∗ , q∗ ), onde p∗ = = ( , ) e q∗ = = ( , ).
θ 3 3 θ 9 9

Figura 1: ppl- primal

8. O Teorema de Equilı́brio de Nash

Na seção anterior provamos o teorema minimax de von Neumann que dá a existência
de um equilı́brio de Nash para jogos de soma zero com dois jogadores. Mas este resultado
é geral: todo jogo definido por uma matriz de payoffs possui um equilı́brio de Nash em
estratégias mistas.
46 Doherty Andrade (FEITEP) & Thiago Zanko (UEM)

A demonstração do Teorema de Equilı́brio de Nash utiliza o teorema do ponto fixo de

Brouwer.

Teorema 8.1 (Brouwer) Seja ∆ ⊂ R n um compacto convexo e F : ∆ → ∆ contı́nua. Então, F

possui um ponto fixo p∗ ∈ ∆, isto é, F (p∗ ) = p∗ .

Definimos para cada i = 1, ..., n e j = 1, ..., mi a função

zij : ∆ → R
p 7→ zij ( p) = ui (sij , p−i ) − ui ( pi , p−i ),

que mede o ganho ou perda do jogador gi quando ele troca a distribuição de probabilidade
pi pela estratégia pura sij .

Teorema 8.2 Seja p∗ ∈ ∆. Temos que p∗ é um equilı́brio de Nash se, e somente se, zij ( p) ≤ 0, para
cada i = 1, ..., n e j = 1, ..., mi .

Demonstração: Seja p∗ = ( pi∗ , p−i

∗ ) um equilı́brio de Nash, então u ( p∗ , p∗ ) ≥ u ( s , p∗ ),
i i −i i ij −i
para cada i = 1, ..., n e j = 1, ..., mi . Consequentemente,

zij ( p∗ ) = ui (sij , p−i

∗
) − ui ( pi∗ , p−i
∗
) ≤ 0,

para cada i = 1, ..., n e j = 1, ..., mi .

Reciprocamente, se zij ( p∗ ) ≥ 0 para cada i = 1, ..., n e j = 1, ..., mi , então

∗ ∗
ui (e j , p−i ) = ui (sij , p−i ) ≤ ui ( pi∗ , p−i
∗
),

para cada i = 1, ..., n e j = 1, ..., mi .

Devemos mostrar que para todo pi ∈ ∆mi , tem-se

∗
ui ( pi , p−i ) ≤ ui ( pi∗ , p−i
∗
).

Como x 7→ ui ( x, pi∗ ) é um funcional linear, temos que

 Introdução à teoria dos Jogos 47

mi mi
!
X X
∗ ∗ ∗
ui ( pi , p−i ) = ui pik · ek , p−i = pik · ui (ek , p−i )
k=1 k=1
mi
X mi
X
≤ pik · ui ( pi∗ , p−i
∗
) = ui ( pi∗ , p−i
∗
)· pik ,
k=1 k=1
Pm i
onde, na última igualdade, usamos o fato de que k=1 pik = 1, dado que pi ∈ ∆mi . 

Para cada i = 1, ..., n e j = 1, ..., mi , definimos a função

gij : ∆ → R
p 7→ gij ( p) = max{0, zij ( p)}

Corolário 8.3 Seja p∗ ∈ ∆. Temos que p∗ é um equilı́brio de Nash se, e somente se, gij ( p∗) = 0,
para cada i = 1, ..., n e j = 1, ..., mi .

Definimos a aplicação

F : ∆ = ∆m1 × ... × ∆mn → ∆ = ∆m1 × ... × ∆mn

p = ( p1 , ..., pn ) 7→ F ( p) = (y1 ( p), ..., yn ( p)),

onde pi = ( pi1 , ..., pimi ), yi ( p) = (yi1 ( p), ..., yimi ( p)) e

pij + gij ( p)
yij ( p) = Pm .
1 + k=i 1 gik ( p)

8.1. A demonstração.

Teorema 8.4 Seja p∗ ∈ ∆. Temos que p∗ é um equilı́brio de Nash se, e somente se, F ( p∗ ) = p∗ .

Demonstração: Observemos que yi ( p) ∈ ∆mi , para todo i = 1, ..., n. De fato, claramente

yij ≥ 0 para todo i = 1, ..., n e j = 1, ..., mi . Para todo p ∈ ∆, tem-se
48 Doherty Andrade (FEITEP) & Thiago Zanko (UEM)

mi mi
! Pm i Pm
X X pik + gik ( p) pik + k=i 1 gik ( p)
k=1
yik ( p) = Pm = Pm
1 + k=i 1 gik ( p) 1 + k=i 1 gik ( p)
k=1 k=1
Pm
1 + k=i 1 gik ( p)
= Pm = 1,
1 + k=i 1 gik ( p)
ou seja, mostramos que F (∆) ⊂ ∆.
Seja p∗ um equilı́brio de Nash, então gij ( p∗ ) = 0 para cada i = 1, ..., n e j = 1, ..., mi .
Deste modo, yij ( p∗ ) = p∗ para cada i = 1, ..., n e j = 1, ..., mi , isto é, yi ( p∗ ) = pi∗ para cada
i = 1, ..., n, ou ainda, F ( p∗ ) = p∗ .
Reciprocamente, se p∗ ∈ ∆ é um ponto fixo do operador F : ∆ → ∆, isto é,
pij∗ + gij ( p∗ )
pij∗ = Pm ,
1 + k=i 1 gik ( p∗ )
para todo i = 1, ..., n e j = 1, ..., mi . Segue que
mi
X
∗
gij ( p ) = pij∗ gik ( p∗ ). (1)
k=1
Pm i
Definimos α = k=1 gik ( p∗ ) para cada i = 1, ..., n e j = 1, ..., mi . Queremos mostrar que
α = 0, de modo que gik ( p∗ ) = 0 para todo i = 1, ..., n e k = 1, ..., mi . Suponhamos, por
absurdo, que α > 0, vemos por (1) que

gij ( p∗ ) > 0 ⇔ pij∗ > 0.

∗ >
Sem perda de generalidade suponhamos que para algum 0 < l < mi , tem-se pi1
0, ...pil∗ > 0 e pi∗(l +1) = ... = pim
∗ = 0. Observemos que
i

mi
X
pi∗ = ∗
pik ek ,
k=1

onde ei é o i-ésimo vetor da base canônica de R mi . Como gik ( p∗ ) > 0 para k = 1, ..., l, temos
0 < gik ( p∗ ) = zik ( p∗ ), ou seja
ui ( pi∗ , p−i
∗ ∗
) < ui (ei , p−i ),
 Introdução à teoria dos Jogos 49

para todo k = 1, ..., l. Desta maneira, temos

mi mi mi
!
X X X
∗ ∗ ∗ ∗ ∗ ∗ ∗
ui ( pi , p−i ) = ui pik , p−i = pik · ui (ei , p−i ) > pik · ui ( pi∗ , p−i
∗
)
k=1 k=1 k=1
mi
X
= ui ( pi∗ , p−i
∗
)· ∗
pik = ui ( pi∗ , p−i
∗
),
k=1

um absurdo. Isto demonstra que gij ( p∗ ) = 0, para todo i = 1, ..., n e j = 1, ..., mi e, assim
pelo corolário 8.3, p∗ é um equilı́brio de Nash em estratégias mistas. 

Teorema 8.5 (equilı́brio de Nash) Todo jogo definido por matrizes de payoffs possui um equilı́brio
de Nash.

Demonstração: A aplicação F : ∆ → ∆ é contı́nua e ∆ é um conjunto compacto e convexo.

Pelo teorema do ponto fixo de Brouwer, F possui um ponto fixo p∗ . Pelo Teorema 8.4, p∗ é
um equilı́brio de Nash. 
O corolário 8.3 acima apresenta também um método para calacular os equilı́brios de
Nash de um jogo. Eles são as soluções do seguinte problema de otimização não-linear:

mi
n X
X
2
minimizar gij ( p)
i=1 j=1
sujeito a p ∈ ∆.
De fato, a soma dos quadrados é zero se, e somente se, cada parcela é nula.
No caso do dilema do prisioneiro (p, q) = ( p, 1 − p; q, 1 − q) ∈ ∆2 × ∆2 é um equilı́brio
de Nash se, e somente se, ( p, q) é solução do seguinte problema

Minimizar G ( p, q) = (max{0, −(−1 + p)(4q + 1)})2 + (max{0, −p(4q + 1)})2 +

+(max{0, −(4p + 1)(−1 + q)})2 + (max{0, −q(4p + 1)})2

sujeito a 0 ≤ p ≤ 1, 0 ≤ q ≤ 1.
50 Doherty Andrade (FEITEP) & Thiago Zanko (UEM)

Figura 2: superfı́cie para o dilema dos prisioneiros

Sabemos que (p, q) = (1, 0; 1, 0) é o único equilı́brio de Nash para o dilema dos prisio-
neiros . A figura 2 mostra a superfı́cie.
No caso do jogo a batalha dos sexos, devemos maximizar a função

(max{0, 5 (−1 + p) (3 q − 1)})2 + (max{0, −5 p (3 q − 1)})2 + (max{0, −5 (3 p − 2) (−1 + q)})2 +

+ (max{0, −5 q (3 p − 2)})2

Sabemos que (p, q) = (1, 0; 1, 0) ou (0, 1; 0, 1) ou ( 32 , 31 ; 13 ; 32 ) são os únicos equilı́brios de

Nash para a batalha dos sexos. A figura 3 mostra a superfı́cie.
 Introdução à teoria dos Jogos 51

Figura 3: superfı́cie para a batalha dos sexos

Referências

1. Max Oliveira de Souza e Jorge Zubelli .Modelagem matemática em finanças quantitativas em tempo
discreto. Notas de Matemática aplicada, 2007.

2. D. Andrade et.al. Introdução à teoria dos Jogos. Notas de Minicurso na XXII semana de Matemática
da UEM. 2011.

3. H. Bortolossi, G. Garbugio, Brigida Sartini. Uma introdução à teoria do jogos. 260 colóquio Brasileiro
de Matemática, 2007.

4. Avner Friedman, Foundations of Modern Analysis. Holt, Reinehart and Winston, Inc., 1970.

5. S. Kesavan, Topics in Functional Analysis and Applications. Bangalores, John Wiley and Sons, 1988.