Existência de Equilíbrio de Nash

Prévia do material em texto

Existência de Equilíbrio de Nash1
Resumo
Vamos apresentar nesta nota uma simples maneira de se provar
a existência de Equilíbrio de Nash para um jogo com um número
finito de jogadores e estratégias. Originalmente, Nash (1950) apre-
sentou uma prova utilizando o teorema do ponto fixo de Kakutani,
já a maneira que vamos tratar é conceitualmente mais simples e nela
seguiremos o teorema do ponto fixo de Brouwer (Nash, 1951).
1 Apresentação
Vamos considerar um conjunto finito de jogadores I = {1, ..., N}. Para ca-
da jogador i ∈ I associamos um conjunto de estratégias (puras) Si. Um
dos principais elementos da teoria de jogos não-cooperativos é a inter-
dependência estratégica e esta é caracterizada ao considerarmos o espaço
produto
S =
NY
i=1
Si
juntamente com uma família de aplicações, uma para cada jogador, chamadas
funções de payoff :
ui : S → R
s 7→ ui(s)
Notação: É usual denotarmos s = (si, s−i) qualquer que seja o índice i ∈ I,
em que si denota a estratégia adotada pelo jogador i ∈ I e s−i denota a
estratégia escolhida pelos demais jogadores.
1José Heleno Faro (jhfaro@impa.br). IMPA - fevereiro, 2006
1
Dado o conjunto de estratégias puras Si do jogador i ∈ I, definimos o con-
junto de estratégias mistas, denotado por ∆(Si), como sendo o conjunto de
todas as medidas de probabilidades sobre Si, ou seja,
∆(Si) = {σi : Si → [0, 1] :
X
si∈Si
σi(si) = 1}.
Como para cada jogador i ∈ I o conjunto Si é finito, notemos que ∆(Si) é
simplesmente o simplex em R#Si.
Agora, podemos estender cada função ui de Si para
QN
i=1∆(Si) ao fazermos1:
ui :
NY
i=1
∆(Si)→ R
σ 7→ ui(σi,σ−i) =
X
s∈S
"
NY
k=1
σk(sk)
#
ui(s)
Notação: Um jogo (em forma normal) é assim descrito como
ΓN = {∆(Si), ui (·)}Ni=1
2 Equilíbrio de Nash
Após apresentar a estrutura de um jogo com um número finito de par-
ticipantes e estratégias o mais natural seria descrever alguns conceitos de
solução2 mais elementares que o de Equilíbrio de Nash, mas não o faremos
pelo fato de termos como único objetivo apresentar uma prova de existência
de Equilíbrio de Nash via ponto fixo de Brouwer.
Dado um jogo em forma normal ΓN = {∆(Si), ui (·)}Ni=1, um conceito de
solução estabelece propriedades que um perfil de estratégias deve satisfaz-
er. Um conceito de solução fundamental para a teoria é dado na seguinte
definição:
1Neste caso estamos supondo um formato do tipo von Neumann-Morgenstern para a
função de payoff. Por abuso de notação também denotamos a extensão por ui. Ainda,
cada estratégia pura si ∈ Si pode ser indentificada com a estratégia mista δ{si} (associa
probabilidade um para si).
2Por exemplo, processos de elimininação sucessiva de estratégias tendo como critério
os conceitos de estratégia estritamente dominadas e estratégias racionalizáveis.
2
Definição 1: Um perfil de estratégias mistas σ = (σ1, ...,σN) é dito um
Equilíbrio de Nash quando para todo jogador i ∈ I
ui(σi,σ−i) ≥ ui(σ0i,σ−i), ∀σ0i ∈ ∆(Si)
Considere um jogador i ∈ I e alguma de suas estratégias mistas σi: definimos
como sendo o suporte da estratégias mista σi o conjunto de estratégias puras
que sejam escolhidas com probabilidade positiva através de σi, ou seja:
supp [σi] = {si ∈ Si : σi(si) > 0}
Lema 1: Um perfil σ ∈
QN
i=1∆(Si) é um Equilíbrio de Nash se, e só se, para
cada i ∈ I :
(i) ui(si,σ−i) = ui(s0i,σ−i), ∀si, s0i ∈ supp [σi] ; e
(ii) ui(si,σ−i) ≥ ui(s0i,σ−i), ∀si ∈ supp [σi] , ∀s0i /∈ supp [σi] .
Prova:
(⇒)Supondo que σ ∈
QN
i=1∆(Si) é um Equilíbrio de Nash mas que (i) ou
(ii) não seja verdadeiro para algum jogador j ∈ I, obtemos que existem
sj ∈ supp[σj] e s0j ∈ Sj de modo que:
uj(s
0
j,σ−j) > uj(sj,σ−j).
Mas ao escrevermos
uj(σj,σ−j) =
X
sj /∈{sj ,s0j}
σj(sj)uj(sj,σ−j) + σj(sj)uj(sj,σ−j) + σj(s0j)uj(s
0
j,σ−j)
<
X
sj /∈{sj ,s0j}
σj(sj)uj(sj,σ−j) +
£
σj(sj) + σj(s0j)
¤
uj(s
0
j,σ−j)
encontramos uma outra estratégia mista (que tira o peso positivo dado a
estratégia pura sj e transfere todo para a estratégia pura s0j) que é melhor
que σj para o jogador j, uma contradição.
(⇐) Supondo que (i) e (ii) são verdadeiros mas que σ não constitua um
Equilíbrio de Nash. Assim para algum jogador io ∈ I e alguma estratégia
σ0i0 ∈ ∆(Si0) temos:
ui0(σ
0
i0
,σ−i0) > ui0(σi0,σ−i0)
3
Mas daí existe algum s0i0 ∈ supp
£
σ0i0
¤
tal que3
ui0(s
0
i0
,σ−i0) > ui0(σi0 ,σ−i0) (z)
como podemos escrever:
ui0(σi0 ,σ−i0) =
X
si0∈supp[σi0 ]
σi0(si0)ui0(si0 ,σ−i0)
e usando (i) e (ii) temos:
ui0(σi0,σ−i0) = ui(si0,σ−i0), ∀si0 ∈ supp [σi0 ]
ui0(σi0,σ−i0) ≥ ui(si0,σ−i0), ∀si0 /∈ supp [σi0 ]
o que claramente contraria a conclusão obtida em (z).
Agora passamos ao principal objetivo desta nota, mas antes vamos apresentar
o enunciado do teorema de ponto fixo de Brouwer:
Teorema 1: Se φ : C → C é uma função contínua, onde C é um subconjunto
não-vazio, compacto e convexo de Rp, então existe algum ponto fixo para φ,
ou seja, algum x ∈ C tal que φ(x) = x.
A prova deste teorema pode ser encontrada em Dunford e Schwartz (1988,
página 468).
Teorema 2: Todo jogo ΓN = {∆(Si), ui (·)}Ni=1 apresenta algum Equilíbrio
de Nash.
Prova:
Dado um jogador i ∈ I, para cada estratégia pura ski ∈ Si ≡ {s1i , ..., sKii }
vamos definir uma função contínua, que associe a cada estratégia mista um
número real não-negativo:
ϕik(σi,σ−i) = max{0, ui(ski ,σ−i)− ui(σi,σ−i)}
A função ϕik é contínua já que é definida como o máximo entre funções
contínuas.
3Em caso contrário, não é difícil ver que ui0(σ0i0 ,σ−i0) ≤ ui0(σi0 ,σ−i0).
4
Pelo Lema 1, temos que um perfil σ∗ = (σ∗i ,σ
∗
−i) é um Equilíbrio de Nash se,
e só se, ∀i ∈ I
ϕik(σ∗i ,σ
∗
−i) = 0, ∀k ∈ {s1i , ..., sKii }.
Agora vamos definir uma aplicação, a partir do conjunto finito de funções
contínuas {ϕik(·)}i∈I;k∈Si, de modo que seja possível aplicar o teorema do
ponto fixo de Brouwer:
T :
NY
i=1
∆(Si)→
NY
i=1
∆(Si)
σ 7−→ T (σ) = σ0
em que σ0 = (σ01, ..., .σ
0
N) e para todo i ∈ I:
σ0i =
1
1 +
P
k
ϕik(σi,σ−i)
"
σi +
X
k
ϕik(σi,σ−i)ek
#
onde ek = (0, ..., 0, 1, 0, ...., 0) apresenta o número 1na k-ésima coordenada4.
Agora, como T é contínua e
QN
i=1∆(Si) é um não-vazio, compacto e convexo
de algum Rp, por Brouwer, temos que existe algum perfil σ∗ ∈
QN
i=1∆(Si)
que é um ponto fixo, ou seja
σ∗i =
1
1 +
P
k
ϕik(σ∗i ,σ
∗
−i)
"
σ∗i +
X
k
ϕik(σ∗i ,σ
∗
−i)ek
#
, ∀i ∈ I
o que equivale a escrever que ∀i ∈ I:
ϕik(σ
∗
i ,σ
∗
−i) = 0, ∀k ∈ {s1i , ..., sKii },
o que equivale, como já comentamos, ao perfil σ∗ ser um Equilíbrio de Nash.
Referências
[1] Dunford, N. and J. T. Schwartz.(1988): Linear Operators, Part I:
General Theory. A Wiley-Interscience Publication.
4Note que T é contínua já que cada coordenada é contínua.
5
[2] Nash , J. F. (1950): Equilibrium Points in n-Person Games. Proc. Nat.
Acad. Sci. U.S.A. 36, 48-49.
[3] Nash , J. F. (1951): Non-Cooperative Games. Annals of Mathematics
54, 286-295.
6