Teoria dos Jogos - Mauricio Bugarin's Blog · PDF fileEntão a conseqüência do jogo para um jogador i quando todos jogam de acordo ... (Cap 1 do livro-texto) – 1. A Forma Normal

1

Aula 7 Teoria dos Jogos Maurício Bugarin

Teoria dos Jogos

Prof. Maurício Bugarin ECO/UnB

2013-I


Roteiro •  Capítulo 2. Jogos Estáticos com Informação Completa (Cap 1 do livro-texto)

–  1. A Forma Normal e o Conceito de Equlíbrio de Nash •  1. A: A Forma Normal •  1. B: Solução por Dominância •  1. C: Equilíbrio de Nash

–  2. Aplicações •  2. A: Duopólio de Cournot •  2. B: Duopólio de Bertrand •  2. C: Negociação com arbitragem

–  3. Estratégias mistas e existência de Equilíbrio de Nash •  3.A: Estratégias mistas: Definição e exemplos •  3.B: Existência de Equilíbrio de Nash

Cap. 2. Jogos Estáticos com Informação Completa

2


3. Estratégias mistas

Experimento: par ou ímpar? 2

p i

1 P 1, −1 −1, 1

I −1, 1 1, −1


Definição- Seja J=(n; S1,..., Sn; u1,..., un) um jogo na forma normal no qual os conjuntos de estratégias dos agentes são finitos: |Si|=ni, i=1,…, n.

Uma estratégia mista para o agente i é uma distribuição de probabilidades

definida sobre o conjunto Si: σi: Si → [0, 1] tal que ∑k σi(sik) = 1 sik σi(sik)

Um perfil de estratégias mistas σ=(σ1,…, σn) é uma seleção de uma estratégia

mista para cada jogador i, i=1,…, n.


3


Exemplo: par ou ímpar? σ=(σ1, σ2)=((1/4, 3/4), (2/3, 1/3)) =((1/4)P+(3/4)I, (2/3)p+(1/3)i)

2

p i

1 P 1, −1 −1, 1

I −1, 1 1, −1



Exemplo- Pedra, papel ou tesoura? σ=(α PE + β PA + γ TE, λ pe + µ pa +ν te)=((α, β, γ), (λ, µ,ν)) em que α+β+γ=λ+µ+ν=1

2

pe pa te

PE 0, 0 −1, 1 1, −1

1 PA 1, −1 0, 0 −1, 1

TE −1, 1 1, −1 0, 0


4


Definição- Sejam N=(n; S1,..., Sn; u1,..., un) um jogo na forma normal e σ=(σ1,…,σn) um perfil de estratégias (mistas).

Então a conseqüência do jogo para um jogador i quando todos jogam de acordo

com o perfil σ é dada por: Eui(σ)=∑ σ1(s1)…σn(sn) ui(s1,…,sn)

O somatório é tomado sobre todos os possíveis perfis de estratégias puras s=(s1,

…, sn). O produto σ1(s1)…σn(sn) corresponde à probabilidade do perfil s ser o perfil

jogado, e ui(s1,…,sn) é o payoff do jogador i quando esse perfil é de fato realizado.

Portanto, Eui(σ) é o payoff esperado (a utilidade esperada) do jogador i quando

cada jogador j escolhe a estratégia mista σj, j=1,…, n.



Exemplo: par ou ímpar? σ=(σ1, σ2)=((1/4, 3/4), (2/3, 1/3)) =((1/4)P+(3/4)I, (2/3)p+(1/3)i) Eu1(σ)=(1/4)(2/3)1 +(1/4)(1/3)(-1) +(3/4)(2/3)(-1) +(3/4)(1/3)1 = 1/12 -3/12 = -1/6 Eu2(σ)=(1/4)(2/3)(-1) +(1/4)(1/3)1 +(3/4)(2/3)1 +(3/4)(1/3)(-1) = -1/12 +3/12 = 1/6

2

p i

1 P 1, −1 −1, 1

I −1, 1 1, −1


5



Exemplo- Pedra, papel ou tesoura? σ=(α PE + β PA + γ TE, λ pe + µ pa +ν te)=((α, β, γ), (λ, µ,ν)) em que α+β+γ=λ+µ+ν=1 σ=(0, 1/2, 1/2), µ=(1/3, 0, 2/3) Eu1(σ,µ) = (1/2)(1/3)1 +(1/2)(2/3)(-1) +(1/2)(1/3)(-1) +(1/2)(2/3)0 = -1/3 Eu2(σ,µ) = (1/2)(1/3)(-1) +(1/2)(2/3)1 +(1/2)(1/3)1 +(1/2)(2/3)0 = 1/3


2

pe pa te

PE 0, 0 −1, 1 1, −1

1 PA 1, −1 0, 0 −1, 1

TE −1, 1 1, −1 0, 0


Definição: Seja J=(n; S1,..., Sn; u1,..., un) um jogo na forma normal. Pode-se definir a partir de J o jogo ΔJ=(n; ΔSi; Eui, i=1,…, n). Portanto, uma estratégia mista do jogo J nada mais é que uma estratégia pura do

jogo ΔJ. Equilíbrio de Nash para estratégias mistas: Um perfil de estratégias σ*=(σ1

*,…,σn*)∈ΔS1×…×ΔSn é um equilíbrio de Nash em

estratégias mistas (ENM) se e somente se, para cada jogador i,

Eui(σ*)≥Eui(σi, σ-i*), ∀σi ∈ΔSi


6


Exemplo: par ou ímpar? Jogador 1: Eu1(λ, µ) = λµ - λ(1-µ) - µ(1-λ) + (1-λ)(1-µ) = (1 - 2λ)(1-2µ) Jogador 2: Eu2(λ, µ) = - (1 - 2λ)(1-2µ)

2

p i

1 P 1, −1 −1, 1

I −1, 1 1, −1



Exemplo: par ou ímpar? Jogador 1: Eu1(λ, µ) = (1 - 2λ)(1-2µ) Jogador 2: Eu2(λ, µ) = - (1 - 2λ)(1-2µ) Se µ<1/2 então MR1: λ=0 Se µ=1/2 então qualquer valor de λ é

uma MR1 Se µ>1/2 então MR1: λ=1 Se λ<1/2 então MR2: µ=1 Se λ=1/2 então qualquer valor de µ é

uma MR2 Se λ>1/2 então MR2: µ=0

2

p i

1 P 1, −1 −1, 1

I −1, 1 1, −1

0 1/2 1 λ

µ

1/2

1 MR2

ENM

0

MR1


7


Exemplo- Jogo do Banana ENM: (λ, µ). Abordagem alternativa: UE1(D|µ), .... (quadro)

2

d m

1 D 0, 0 10, 50

M 50, 10 –100, –100



Roteiro •  Capítulo 2: Jogos Estáticos com Informação Completa (Cap 1 do livro-texto)

–  1. A Forma Normal e o Conceito de Equlíbrio de Nash •  1. A: A Forma Normal •  1. B: Solução por Dominância •  1. C: Equilíbrio de Nash

–  2. Aplicações •  2. A: Duopólio de Cournot •  2. B: Duopólio de Bertrand •  2. C: Negociação com arbitragem

–  3. Estratégias mistas e existência de Equilíbrio de Nash •  3.A: Estratégias mistas: Exemplos: Batalha dos Sexos Assimétrica e Cidadania •  3.B: Existência de Equilíbrio de Nash


8


Exemplo- Batalha dos Sexos Assimétrico ENM: (λ, µ) (quadro) Discussão: ENM como mecanismo para disciplinar o outro jogador

Radicalismo estratégico

2

B S

1 B 7, 4 3, 2

S 0, 0 4, 6



Observações: •  Todo EN em estratégias puras é um ENM •  EIED?

2

t1 t2 t3

1 s1 14, 12 18, 2 12, 6

s2 10, 2 16, 12 16, 6


9


3.A. Estratégia Mistas: Jogo da Cidadania

Denunciar crimes N=2, n>2


2

d n

1 D v−c, v−c v−c, v

N v, v−c 0, 0


3.B. Existência de Equilíbrio de Nash

Definição-Sejam A, B⊆Rk e seja ℘(B)=2B o conjunto dos subconjuntos de B.

(i) Uma aplicação f: A→℘(B) é chamada uma correspondência de A em B.

(ii) O gráfico da correspondência f é dado pelo conjunto:

Graf(f)={(x,y) | x∈ A, y∈ f(x)}.

(iii) O gráfico de f é dito fechado se quaisquer que sejam as seqüências {an} em A e {bn} em B, tais que ∀n, bn∈ f(an), se an converge para a e bn converge para b, então a∈A e b∈f(a).

Exemplo-Toda função g: A→B pode ser vista como um caso particular de uma correspondência de A em B, fg, definida por fg(a)={g(a)}. Nesse caso, o gráfico de fg é fechado se e somente se A é um subconjunto fechado de Rk e g é contínua.


10



Exemplo- f(x)=2x.

Exemplo-Seja f: R+→℘(R) definida por f(x)=[-x, x]. Então o gráfico de f é fechado e pode ser representado pela figura 6.1 abaixo. Observe que se f for definida por f(x)=(-x, x), então o gráfico de f não é mais fechado.


x

y y=x

y=−x

Figura 6.1: Gráfico da correspondência f(x)=[−x, x]



Exemplo-Considere um consumidor que possui uma renda I a ser usada na aquisição dos bens 1, 2, ..., m. Seja x=(x1,..., xm)∈ uma cesta genérica desses bens. Se p=(p1,..., pm) ∈ for o vetor de preços de mercado dos bens na economia, então pode-se definir:

O conjunto B(p) é chamado conjunto orçamentário associado ao vetor de preços p e representa todas as cestas que o consumidor pode comprar, dada sua renda, se os preços de mercado forem dados por p. Assim, B define uma correspondência de em , que é chamada de correspondência orçamentária.

(Gráfico)


{ }IxpRxpB m ≤∈= + .|)(

mR+

mR+mR+

mR+

11



Teorema (lema)-Teorema do Ponto Fixo de Kakutani. Seja A⊆Rn não vazio, convexo e compacto e seja f: A→℘(A) uma correspondência. Suponha que:

(i) Para todo a∈A, f(a) é um subconjunto não-vazio e convexo de A.

(ii) O gráfico de f é fechado.

Então existe z∈A tal que z∈f(z). O ponto z é chamado um ponto fixo da correspondência f.

Exemplo-No exemplo anterior, f(x)=[-x, x], todo ponto x∈R+ é um ponto fixo de f.

E se f(x)=[-x/2, x/2]? E se f(x)=[1-x, x-1], x∈[0,1]?

Exemplo-No caso particular em que f é uma função, um ponto fixo é um ponto z∈A tal que f(z)=z. Se A=[a, b] e f: A→ A, então o conhecido Teorema do Valor Intermediário pode ser visto como um caso particular do Teorema de Kakutani.


Quadro



Teorema (lema)-Existência de Equilíbrio de Nash. Seja J=(n; S1,…, Sn; u1,…, un) um jogo na forma normal tal que:

(i) Para todo jogador i, Si é um subconjunto não-vazio, convexo e compacto de algum espaço euclidiano.

(ii) Para todo jogado i, ui é uma função contínua em s=(s1, …, sn) e quase-côncava em si.

Então existe pelo menos um equilíbrio de Nash no jogo J.

Demonstração. Defina, para cada i=1,…, n, a correspondência melhor resposta:

MRi: S-i → ℘(Si)

s-i MRi(s–i)=argmax ui(si, s-i)={si∈ Si | ui(si, s-i)≥ ui(r, s-i), ∀r∈Si}.

Então:

(i) Como Si é compacto e ui é contínua em si, então para todo s-i∈S-i, MRi(s-i) é não-vazio.


12






Então existe pelo menos um equilíbrio de Nash no jogo J.

Demonstração. Defina, para cada i=1,…, n, a correspondência melhor resposta:

MRi: S-i → ℘(Si)

s-i MRi(s–i)=argmax ui(si, s-i)={si∈ Si | ui(si, s-i)≥ ui(r, s-i), ∀r∈Si}.

Então:

(ii) Como ui é quase-côncava em si, ∀si, siʹ′∈Si, ∀α∈[0,1],

si, siʹ′∈ MRi(s-i) ⇒ ui(si, s-i)≥ ui(siʹ′, s-i) ⇒ ui(αsi + (1-α)siʹ′, s-i)≥ ui(siʹ′, s-i) ⇒

αsi + (1-α)siʹ′ ∈ MRi(s-i), ∀s-i∈S-i. Assim, MRi(s-i) é um conjunto convexo.







Demonstração. MRi: S-i → ℘(Si)

s-i MRi(s–i)

(iii) Seja s-i,k uma seqüência em S-i e, para cada k, seja si,k∈ MRi(s-i,k), tais que s-i,k→ s-i e si,k→ si.

Como Si e S-i são conjuntos compactos si∈Si e s-i∈S-i. Além disso, por construção, para cada k, ui(si,k, s-i,k)≥ ui(siʹ′, s-i,k), ∀ siʹ′∈Si.

Como ui é contínua em S, tomando o limite quando k→+∞ temos:

ui(si, s-i)≥ ui(siʹ′, s-i), ∀ siʹ′∈Si ⇒ si∈MRi(s-i).

Logo, o gráfico de MRi é fechado.


13






Demonstração. MRi: S-i → ℘(Si)

s-i MRi(s–i)

(iv) Defina agora MR: S→℘(S) por MR(s)=MR1(s-1)×…× MRn(s-n). Então, MR satisfaz as condições do teorema de Kakutani. Assim, existe s=(s1,…, sn)∈S tal que si∈MR(s-i), para todo i=1,…, n. Logo s é um equilíbrio de Nash do jogo.







Exemplos.

Cournot, Bertrand com produtos não homogêneos, cidadania visto como escolha de estratégias mistas.


14



Teorema-Existência de Equilíbrio de Nash (Nash 1950). Seja J=(n; S1,…, Sn; u1,…, un) um jogo na forma normal onde cada jogador possui um número finito de estratégias. Então J possui pelo menos um equilíbrio de Nash em estratégias mistas.

Demonstração. Basta considerar o jogo associado ΔJ=(n; ΔS1,…,ΔSn; Eu1,…,Eun) e observar que os simplexos ΔSi satisfazem as condições (i) do teorema anterior e que as funções de utilidade esperada Eui são lineares, e portanto contínuas e quase-côncavas, em seus argumentos.

Diagrama de Venn


Documents

Teoria dos Jogos - Mauricio Bugarin's Blog · PDF fileEntão a conseqüência do jogo para um jogador i quando todos jogam de acordo ... (Cap 1 do livro-texto) – 1. A Forma Normal