Existência de Equilíbrio de Nash
6 pág.

Existência de Equilíbrio de Nash


DisciplinaTeoria Microeconomica III93 materiais302 seguidores
Pré-visualização1 página
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 \u2208 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 payo\ufb00 :
ui : S \u2192 R
s 7\u2192 ui(s)
Notação: É usual denotarmos s = (si, s\u2212i) qualquer que seja o índice i \u2208 I,
em que si denota a estratégia adotada pelo jogador i \u2208 I e s\u2212i 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 \u2208 I, definimos o con-
junto de estratégias mistas, denotado por \u2206(Si), como sendo o conjunto de
todas as medidas de probabilidades sobre Si, ou seja,
\u2206(Si) = {\u3c3i : Si \u2192 [0, 1] :
X
si\u2208Si
\u3c3i(si) = 1}.
Como para cada jogador i \u2208 I o conjunto Si é finito, notemos que \u2206(Si) é
simplesmente o simplex em R#Si.
Agora, podemos estender cada função ui de Si para
QN
i=1\u2206(Si) ao fazermos1:
ui :
NY
i=1
\u2206(Si)\u2192 R
\u3c3 7\u2192 ui(\u3c3i,\u3c3\u2212i) =
X
s\u2208S
"
NY
k=1
\u3c3k(sk)
#
ui(s)
Notação: Um jogo (em forma normal) é assim descrito como
\u393N = {\u2206(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 \u393N = {\u2206(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 payo\ufb00. Por abuso de notação também denotamos a extensão por ui. Ainda,
cada estratégia pura si \u2208 Si pode ser indentificada com a estratégia mista \u3b4{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 \u3c3 = (\u3c31, ...,\u3c3N) é dito um
Equilíbrio de Nash quando para todo jogador i \u2208 I
ui(\u3c3i,\u3c3\u2212i) \u2265 ui(\u3c30i,\u3c3\u2212i), \u2200\u3c30i \u2208 \u2206(Si)
Considere um jogador i \u2208 I e alguma de suas estratégias mistas \u3c3i: definimos
como sendo o suporte da estratégias mista \u3c3i o conjunto de estratégias puras
que sejam escolhidas com probabilidade positiva através de \u3c3i, ou seja:
supp [\u3c3i] = {si \u2208 Si : \u3c3i(si) > 0}
Lema 1: Um perfil \u3c3 \u2208
QN
i=1\u2206(Si) é um Equilíbrio de Nash se, e só se, para
cada i \u2208 I :
(i) ui(si,\u3c3\u2212i) = ui(s0i,\u3c3\u2212i), \u2200si, s0i \u2208 supp [\u3c3i] ; e
(ii) ui(si,\u3c3\u2212i) \u2265 ui(s0i,\u3c3\u2212i), \u2200si \u2208 supp [\u3c3i] , \u2200s0i /\u2208 supp [\u3c3i] .
Prova:
(\u21d2)Supondo que \u3c3 \u2208
QN
i=1\u2206(Si) é um Equilíbrio de Nash mas que (i) ou
(ii) não seja verdadeiro para algum jogador j \u2208 I, obtemos que existem
sj \u2208 supp[\u3c3j] e s0j \u2208 Sj de modo que:
uj(s
0
j,\u3c3\u2212j) > uj(sj,\u3c3\u2212j).
Mas ao escrevermos
uj(\u3c3j,\u3c3\u2212j) =
X
sj /\u2208{sj ,s0j}
\u3c3j(sj)uj(sj,\u3c3\u2212j) + \u3c3j(sj)uj(sj,\u3c3\u2212j) + \u3c3j(s0j)uj(s
0
j,\u3c3\u2212j)
<
X
sj /\u2208{sj ,s0j}
\u3c3j(sj)uj(sj,\u3c3\u2212j) +
£
\u3c3j(sj) + \u3c3j(s0j)
¤
uj(s
0
j,\u3c3\u2212j)
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 \u3c3j para o jogador j, uma contradição.
(\u21d0) Supondo que (i) e (ii) são verdadeiros mas que \u3c3 não constitua um
Equilíbrio de Nash. Assim para algum jogador io \u2208 I e alguma estratégia
\u3c30i0 \u2208 \u2206(Si0) temos:
ui0(\u3c3
0
i0
,\u3c3\u2212i0) > ui0(\u3c3i0,\u3c3\u2212i0)
3
Mas daí existe algum s0i0 \u2208 supp
£
\u3c30i0
¤
tal que3
ui0(s
0
i0
,\u3c3\u2212i0) > ui0(\u3c3i0 ,\u3c3\u2212i0) (z)
como podemos escrever:
ui0(\u3c3i0 ,\u3c3\u2212i0) =
X
si0\u2208supp[\u3c3i0 ]
\u3c3i0(si0)ui0(si0 ,\u3c3\u2212i0)
e usando (i) e (ii) temos:
ui0(\u3c3i0,\u3c3\u2212i0) = ui(si0,\u3c3\u2212i0), \u2200si0 \u2208 supp [\u3c3i0 ]
ui0(\u3c3i0,\u3c3\u2212i0) \u2265 ui(si0,\u3c3\u2212i0), \u2200si0 /\u2208 supp [\u3c3i0 ]
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 \u3c6 : C \u2192 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 \u3c6,
ou seja, algum x \u2208 C tal que \u3c6(x) = x.
A prova deste teorema pode ser encontrada em Dunford e Schwartz (1988,
página 468).
Teorema 2: Todo jogo \u393N = {\u2206(Si), ui (·)}Ni=1 apresenta algum Equilíbrio
de Nash.
Prova:
Dado um jogador i \u2208 I, para cada estratégia pura ski \u2208 Si \u2261 {s1i , ..., sKii }
vamos definir uma função contínua, que associe a cada estratégia mista um
número real não-negativo:
\u3d5ik(\u3c3i,\u3c3\u2212i) = max{0, ui(ski ,\u3c3\u2212i)\u2212 ui(\u3c3i,\u3c3\u2212i)}
A função \u3d5ik é 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(\u3c30i0 ,\u3c3\u2212i0) \u2264 ui0(\u3c3i0 ,\u3c3\u2212i0).
4
Pelo Lema 1, temos que um perfil \u3c3\u2217 = (\u3c3\u2217i ,\u3c3
\u2217
\u2212i) é um Equilíbrio de Nash se,
e só se, \u2200i \u2208 I
\u3d5ik(\u3c3\u2217i ,\u3c3
\u2217
\u2212i) = 0, \u2200k \u2208 {s1i , ..., sKii }.
Agora vamos definir uma aplicação, a partir do conjunto finito de funções
contínuas {\u3d5ik(·)}i\u2208I;k\u2208Si, de modo que seja possível aplicar o teorema do
ponto fixo de Brouwer:
T :
NY
i=1
\u2206(Si)\u2192
NY
i=1
\u2206(Si)
\u3c3 7\u2212\u2192 T (\u3c3) = \u3c30
em que \u3c30 = (\u3c301, ..., .\u3c3
0
N) e para todo i \u2208 I:
\u3c30i =
1
1 +
P
k
\u3d5ik(\u3c3i,\u3c3\u2212i)
&quot;
\u3c3i +
X
k
\u3d5ik(\u3c3i,\u3c3\u2212i)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\u2206(Si) é um não-vazio, compacto e convexo
de algum Rp, por Brouwer, temos que existe algum perfil \u3c3\u2217 \u2208
QN
i=1\u2206(Si)
que é um ponto fixo, ou seja
\u3c3\u2217i =
1
1 +
P
k
\u3d5ik(\u3c3\u2217i ,\u3c3
\u2217
\u2212i)
&quot;
\u3c3\u2217i +
X
k
\u3d5ik(\u3c3\u2217i ,\u3c3
\u2217
\u2212i)ek
#
, \u2200i \u2208 I
o que equivale a escrever que \u2200i \u2208 I:
\u3d5ik(\u3c3
\u2217
i ,\u3c3
\u2217
\u2212i) = 0, \u2200k \u2208 {s1i , ..., sKii },
o que equivale, como já comentamos, ao perfil \u3c3\u2217 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