Reticulados e Supermodularidade

Prévia do material em texto

Microeconomia I – Monitoria 1
Professor: Leonardo Rezende
Monitor: Igor Rigolon
1 Reticulados e supermodularidade
1.1 Join e meet
Definição 1.1: Join e meet
Em um conjunto X com ordem ≥, definimos as operações de join (∨)
e meet (∧):
• x ∨ y ∈ X é uma cota superior dos elementos (x ∨ y ≥ x, y), e é
a menor cota superior (se z ≥ x, y é cota superior, z ≥ x ∨ y).
• x∧ y ∈ X é uma cota inferior dos elementos (x∧ y ≤ x, y), e é a
maior cota inferior (se z ≤ x, y é cota inferior, z ≤ x ∧ y).
Exerćıcio 1.1. Para cada conjunto ordenado abaixo, calcule as operações
de meet (∨) e join (∧) para elementos arbitrários.
(a) Conjunto de subconjuntos de X com a ordem A ≥ B ⇐⇒ A ⊇ B.
(b) Conjunto de intervalos [a, b] ⊆ R, também com a ordem ≥=⊇.
(c) Espaço de funções f : Rn → R com a relação de ordem f ≥ g ⇐⇒
f(x) ≥ g(x)∀x.
(d) Números naturais N, mas com a ordem n ≥ m ⇐⇒ n é diviśıvel por
m.
Exerćıcio 1.2. Prove que, no espaço Rn com a norma euclidiana e a ordem
elemento a elemento,
||x ∨ y − x ∧ y|| = ||x− y||.
1
1.2 Reticulados e subreticulados
Definição 1.2: Reticulado
Um conjunto ordenado X é um reticulado se, para todos x, y ∈ X,
existem x ∨ y e x ∧ y.
Exerćıcio 1.3. Prove que todo subconjunto X ⊂ R é um reticulado.
Exerćıcio 1.4. Prove que o quadrado com um buraco X = ([0, 2]× [0, 2]) \
{(1, 1)} não é um reticulado.
Definição 1.3: Subreticulado
Um subconjunto A ⊆ X é um subreticulado de X se, usando as
operações de join e meet de X, todos x, y ∈ A têm x ∨ y ∈ A e
x ∧ y ∈ A. (A é fechado para essas operações)
Exerćıcio 1.5. Sejam X = R2 e A = {(0, 0), (2, 1), (1, 2), (3, 3)}. Prove que
A é um reticulado, mas não é um subreticulado de X.
*Exerćıcio 1.6. Para um reticulado arbitrário (X,≥), sejam x1, x2 ∈ X e
defina [x1, x2] := {x ∈ X : x ≥ x1, x2 ≥ x}. Mostra que essa espécie de
intervalo fechado é um subreticulado de X.
1.3 Supermodularidade e Diferenças Crescentes
Definição 1.4: Supermodularidade
Uma função f : X → R definida em um reticulado X é supermodular
se, para todos x, y ∈ X,
f(x ∨ y) + f(x ∧ y) ≥ f(x) + f(y).
Exerćıcio 1.7. Prove que toda f : X ⊆ R → R é supermodular.
Teorema 1.1: Caracterização com derivadas em R2
Uma função f : X → R duas vezes diferenciável, definida em um retic-
ulado X ⊆ R2 aberto, é supermodular se, e somente se, f12 ≥ 0.
2
Esboço da prova. Tome ε1, ε2 > 0 e (a, b) ∈ X. (⇒) Se f é super-
modular, vale a desigualdade para todos ε1, ε2. Reescrevendo como
quociente diferencial e tomando ε → 0, chegamos ao reultado. (⇐) Se
a derivada mista é positiva, o Teorema do Valor Médio garante que vale
a mesma desigualdade, caso contrário a derivada mista seria negativa
em algum ponto.
Definição 1.5: Diferenças Crescentes
Uma função f : X × T → R tem diferenças crescentes se, para
x′ ≥ x ∈ X e t′ ≥ t ∈ T ,
f(x′, t′)− f(x, t′) ≥ f(x′, t)− f(x, t).
Teorema 1.2: Caracterização com derivadas em Rn
Seja f(x, t) = f(x1, . . . , xk, t1, . . . , tℓ) uma função de X×T ⊆ Rn → R
duas vezes diferenciável. A função f tem diferenças crescentes em (x, t)
se, e somente se, para todos i, j,
∂2f
∂tj∂xi
≥ 0.
Prova. Por definição, f tem DC sse para x′ ≥ x e t′ ≥ t vale
f(x′, t′)− f(x, t′) ≥ f(x′, t)− f(x, t).
Fixe x ∈ X, t ∈ T , e escolha x′ = x + h1ei, t
′ = t + h2ej, onde ek é o
vetor k da base canônica, (0, . . . , 0, 1, 0, . . . , 0), com 1 na posição k, e
h1, h2 > 0.
(⇒) Se f tem DC, a desigualdade tem que valer para essas escolhas
espećıficas de x′, t′. Então
f(x+ h1ei, t
′)− f(x, t′)
h1
≥ f(x+ h1ei, t)− f(x, t)
h1
h1→0−→ ∂f
∂x
(x, t′)− ∂f
∂x
(x, t) ≥ 0.
3
Repetindo o truque, substituindo a expressão para t′, dividindo por
h2, e deixando h2 → 0, chegamos a ∂tj∂xi
f ≥ 0.
(⇐) Se a derivada mista é positiva, a derivada ∂f/∂xi tem de ser
crescente em tj, valendo
∂f
∂x
(x, t′)− ∂f
∂x
(x, t) =
∂
∂x
[f(x, t′)− f(x, t)] ≥ 0.
Como a derivada da diferença é positiva, a diferença tem que ser cres-
cente em x. Então
f(x′, t′)− f(x, t′) ≥ f(x′, t)− f(x, t),
para quaisquer x, t e x′ = x + h1ei e t′ = t + h2ej. Mas, como isso
deve valer para todos i, j, dado um x′ ≥ x arbitrário, escrevemos x′ =
x+ (u1, . . . , uk). Defina x1 = x+ e1u1 como primeiro passo.
f(x′, t′)− f(x, t′) = f(x′, t′)− f(x1, t′) +
[
f(x1, t′)− f(x, t′)
]
≥ f(x′, t′)− f(x1, t′) + f(x1, t)− f(x, t)
= f(x′, t′)−
[
f(x1, t′)− f(x1, t)
]
− f(x, t)
Agora, seja t1 = t+ e1v1.
f(x′, t′)− f(x, t′) ≥ f(x′, t′)− [f(x, t′)− f(x, t)]− f(x, t) = 0,
para x′ ≥ x, t′ ≥ t arbitrários.
Teorema 1.3: SM =⇒ DC
Se f : Y → R definida em um reticulado Y = X × T é supermodular,
então f : X × T → R tem diferenças crescentes.
4
Teorema 1.4: DC (às vezes) =⇒ SM
Se f(x, t) definida em um reticulado Y = X × T tem diferenças
crescentes e é supermodular em x e em t, então f é supermodular.
Obs: f(x, t) é supermodular em x se, fixando t, a função f(·, t) é
supermodular. Mais explicitamente, g(x) := f(x, t) é supermodular.
Prova. Tome x1, x2 ∈ X e t1, t2 ∈ T , usando (x1, t1) ∨ (x2, t2) = (x1 ∨
x2, t1 ∨ t2), o mesmo para o meet.
f(x1 ∨ x2, t1 ∨ t2)− f(x1, t1) = f(x1 ∨ x2, t1 ∨ t2)− f(x1 ∨ x2, t1)︸ ︷︷ ︸
A
+ f(x1 ∨ x2, t1)− f(x1, t1)︸ ︷︷ ︸
B
.
A
SM t
≥ f(x1 ∨ x2, t2)− f(x1 ∨ x2, t1 ∧ t2)
DC
≥ f(x2, t2)− f(x2, t1 ∧ t2)
B
SM t
≥ f(x2, t1)− f(x1 ∧ x2, t1)
DC
≥ f(x2, t1 ∧ t2)− f(x1 ∧ x2, t1 ∧ t2).
Unindo as peças, chegandos na definição de supermodularidade.
Exerćıcio 1.8. Justifique por que f(x1, x2, x3, x4) = x1x2x3x4 para x > 0 é
supermodular.
Exerćıcio 1.9. Seja
f(x1, x2, x3, t1, t2) =
x1t
2
1
x2t2
+ x3, x, t > 0.
Veja que f não é SM em x nem tem DC em (x, t). Mas, trocando alguns
sinais, justifique porque f é SM em (x1,−x2, x3) e tem DC em
(
(x1,−x2, x3), (t1,−t2)
)
.
5
Corolário 1.1: DC (às vezes) =⇒ SM (Generalização)
Se X = X1×· · ·×Xn, e f : X → R tem diferenças crescentes em todas
as formas de decompor X = Z1 × Z2 e é supermodular em cada Xi, f
é supermodular em X..
*Exerćıcio 1.10. Indutivamente, pense como o Teorema anterior implica o
Corolário acima.
Exerćıcio 1.11. Algumas dificuldades ao afirmar que uma f : Rn → R é
supermodular: (Suponha que as coordenadas são ≥ 0)
(a) Veja que f(x, y, z) = xy/z é supermodular e diferenças crescentes em
(x, y), também é supermodular em z, mas não é supermodular em
(x, y, z).
(b) Veja que f(x, y, z, w) = xy/zw tem diferenças crescentes em (x, y) e
em (z, w), mas não é supermodular como um todo.
*Exerćıcio 1.12. Seja f : Rn → R uma função com diferenças crescentes
em cada par (xi, xj). Iremos mostrar que, no Rn, essa condição coincide com
a supermodularidade.
(a) Mantenha todas as outras coordenadas fixas, e considere, por enquanto,
f(x, y, z). Mostre, pelas desigualdades, que como f tem DC em (x, z)
e em (y, z), também tem DC em
(
(x, y), z
)
.
(b) Repetindo esse processo para várias combinações de coordenadas, veja
que f tem diferenças crescentes em qualquer combinação de coorde-
nadas
(
(xi1 , . . . , xik), (xj1 , . . . , xjℓ)
)
. Nesse caso, o corolário se aplica,
garantindo que f é supermodular.
(c) Relembre o Teorema 1.2. Veja que, pelo item (b) acima, se f é duas
vezes diferenciável e todas as derivadas parciais mistas atendem ∂j∂if ≥
0, f é supermodular.
*Exerćıcio 1.13 (Supermodularidade de diferenças crescentes). Demonstre
as seguintes afirmações:
(a) Suponha que g1, g2 : R → R sejam não-decrescentes. Se f : R2 → R é
supermodular, então f (g1 (x1) , g2 (x2)) também é supermodular.
6
(b) Seja h : R → R duas vezes diferenciável. Mostre que g(x, t) := h(x− t)
satisfaz diferenças crescentes se, e somente se, h é côncava.
Exerćıcio 1.14. Uma função f : X → R é dita log-supermodular se, para
todos x, y ∈ X,
f(x ∨ y) f(x ∧ y) ≥ f(x) f(y).
(a) Observe que, para funções positivas, com f(x) > 0 para todo x, f é
log-supermodular se, e somente se, log f é supermodular.
(b) Dê um exemplo de f : X ⊆ R2 → R que é supermodular, masnão é
log-supermodular.
(c) Dê um exemplo de função log-supermodular, mas não supermodular.
2 Estática comparativa
2.1 Teorema do Envelope
Definição 2.1: Continuidade Absoluta
Uma função G : [a, b] → R é absolutamente cont́ınua se, para todo
ε > 0 e n ∈ N, existe δ > 0 tal que, para toda coleção de subinter-
valos disjuntos (a1, b1), . . . , (an, bn) que satisfaz
∑
i(bi − ai) < δ, vale∑
i|G(bi)−G(ai)| < ε.
Lema 2.1: Caracterização de continuidade absoluta
Uma função G : [a, b] → R é absolutamente cont́ınua se, e somente se,
G(x) = G(a) +
∫ x
a
g(t) dt,
onde G é diferenciável em quase todo ponto, com G′(x) = g(x) nesses
pontos.
7
Teorema 2.1: Teorema do Envelope
Seja f : X × [a, b] → R diferenciável em t e com derivada parcial
limitada |∂f/∂t| ≤ M . Defina V (t) := maxx f(x, t) e x∗(t) :=
argmaxx f(x, t). Tomando x(t) ∈ x∗(t),
V (y) = V (a) +
∫ y
a
∂f
∂t
(x(t), t) dt.
Ou seja, V é diferenciável em quase todo ponto, com V ′(t) = ∂f/∂t.
Prova (Parte 1). Primeiro, iremos provar que f é absolutamente
cont́ınua. Fixe ε > 0 e n ∈ N. Para qualquer subintervalo com
ai < bi ∈ [a, b],
|V (bi)− V (ai)| = |f(x∗(bi), bi)− f(x∗(ai), ai)|
≤ sup
x
|f(x, bi)− f(x, ai)|
= sup
x
∣∣∣∣∂f∂t (x, ti) (bi − ai)
∣∣∣∣ para ti ∈ (ai, bi), pelo TVM
≤ M (bi − ai), pela derivada parcial ser limitada.
Escolhendo δ = ε/M , sempre que
∑
i(bi − ai) < δ, vale∑
i
|V (bi)− V (ai)| ≤ M
∑
i
(bi − ai) < M δ = ε.
Isso prova que V é absolutamente cont́ınua.
Prova (Parte 2). Pelo Lema anterior, V pode ser representada por
V (x) = V (a) +
∫ x
a
v(t) dt,
sendo V ′(t) = v(t) em q.t.p., quando a derivada existe. Resta mostrar
que, se V é diferenciável, vale, necessariamente, que V ′(t) = ∂f/∂t.
Nos pontos t onde V ′(t) existe, seja x(t) ∈ x∗(t) e considere a derivada
pela direita, V ′
+.
V ′
+(t) = lim
h→0+
V (t+ h)− V (t)
h
= lim
h→0+
f(x(t+ h), t+ h)− f(x(t), t)
h
= lim
h→0+
f(x(t+ h), t+ h)− f(x(t), t+ h)
h
+
f(x(t), t+ h)− f(x(t), t)
h
8
Pelo máximo, f(x(t+h), t+h) ≥ f(x(t), t+h). Eliminando o primeiro
termo,
V ′
+(t) ≥ lim
h→0+
f(x(t), t+ h)− f(x(t), t)
h
=
∂f
∂t
.
Também podemos escrever
V ′
+(t) =
lim
h→0+
f(x(t+ h), t+ h)− f(x(t+ h), t)
h
+
f(x(t+ h), t)− f(x(t), t)
h
.
Pelo mesmo truque, usando f(x(t), t) ≥ f(x(t+ h), t),
V ′
+(t) ≤ lim
h→0+
f(x(t+ h), t+ h)− f(x(t+ h), t)
h
=
∂f
∂t
.
O mesmo pode ser feito para V ′
−(t), provando que, quando a derivada
existe, vale V ′(t) = ∂f/∂t
Exerćıcio 2.1. Suponha que uma firma produza um produto q. A firma
não é tomadora de preço, tal que o preço que obtém pela produção de uma
quantidade q é dado pela função demanda inversa P (q). Sua receita, R(q),
pode ser escrita como: R(q) = P (q) · q. Seu custo de produção é dado
por c(q; θ), onde θ ∈ R é um parâmetro e c(q; θ) é diferenciável em θ e
estritamente crescente em q. A empresa escolhe q∗(θ) de forma a maximizar
R(q) − c(q; θ). Suponha que você só observe q∗(θ) e c (q∗(θ), θ) e o lucro da
empresa quando θ = 0. Como identificar a função P (q∗(θ)) ? Derive sua
expressão.
9
2.2 Teorema de Topkis
Definição 2.2: Funções e correspondências crescentes
Dado um conjunto ordenado T e um reticulado X, seja t′ ≥ t ∈ T .
• Uma função f : T → X é crescente se f(t′) ≥ f(t).
• Uma correspondência A : T ⇒ X é crescente se A(t) ∨ A(t′) ⊆
A(t′) e A(t) ∧ A(t′) ⊆ A(t), onde uso a notação A ∨ B para o
conjunto formado por a ∨ b para todos a ∈ A, b ∈ B.
Exerćıcio 2.2. Verifique se as definições acima são coerentes: tome uma
função qualquer f : T → X e defina a correspondência equivalente A : T ⇒ X
definida por A(t) = {f(t)}. Prove que f é crescente se, e somente se, A é
crescente.
*Exerćıcio 2.3. Seja A : R → R uma correspondência que mapeia cada
ponto em um intervalo fechado [a(t), b(t)]. Prove que A é crescente se, e
somente se, a e b são crescentes.
Teorema 2.2: Topkis
Seja T um conjunto ordenado e X um reticulado. Se f : X × T tem
diferenças crescentes e é supermodular em x, e se A : T ⇒ X é cres-
cente, então a correspondência x∗(t) := argmaxx∈A(t) f(x, t) é cres-
cente.
Exerćıcio 2.4. Verifique se valem as premissas e as conclusões do Teorema
de Topkis nos casos abaixo, sempre com um problema de maximização
f : X × T → R max
x∈A(t)
f(x, t).
(a) X = T = R, f(x, t) = x, A(t) = {t}.
(b) X = T = {0, 1}, f(x, t) = xt− x, A(t) ≡ X.
(c) X = [0, 2]2 \ {(1, 1)} (quadrado com buraco), T = {0, 1}, f(x1, x2, t) =
(x1 − t)2 + (x2 − t)2 , A(t) ≡ X.
(d) X = [0, 2]2 \ {(1, 1)} (quadrado com buraco), T = {0, 1}, f(x1, x2, t) =
−
[
(x1 − t)2 + (x2 − t)2
]
, A(t) ≡ X.
10
(d) X = {(1, 0), (0, 2)}, T = {0, 1}, f(x1, x2, t) = x1x2+x1+tx2, A(t) ≡ X.
*Exerćıcio 2.5. Seja f : R2 → R duas vezes diferenciável, e supermodular.
Supondo que x∗(t) = argmaxx f(x, t) é diferenciável e sempre atinge um
ponto de máximo interior, use o Teorema da Função Impĺıcita na CPO de
maximização para mostrar que x∗ é crescente em t.
2.3 Teorema do Máximo de Berge
Definição 2.3: Continuidade de Correspondências
Para uma correspondência C : T ⇒ X,
• C é semicont́ınua superiormente (SCS) se, para toda sequência
(tn) ⊆ T com tn → t ∈ T , e para toda sequência xn ∈ C(tn), se
xn → x, então x ∈ C(t).
• C é semicont́ınua inferiormente (SCI) se, para toda sequência
(tn) ⊆ T com tn → t ∈ T , e para todo x ∈ C(t), existe xn ∈ C(tn)
tal que xn → x.
• C é cont́ınua se é SCS e SCI.
*Exerćıcio 2.6. Considere uma correspondência A(t) ≡ A constante.
(a) Mostre que A é SCI.
(b) Mostre que A é SCS se, e somente se, cada A(t) é um conjunto fechado.
Exerćıcio 2.7. Mostre, em cada item, que a correspondência é ou não SCS
e/ou SCI.
• Para mostrar que não é SCS, encontre sequências tn → t e xn ∈ A(tn)
tais que xn → x e x /∈ A(t).
• Para mostrar que não é SCI, encontre uma sequência tn → t e x ∈ A(t)
tais que nenhuma xn ∈ A(tn) converge para x.
(a) Não é SCS nem SCI:
A(t) =
{
{−1}, t ≤ 0,
{+1}, t > 0
11
(b) É SCS, mas não SCI:
A(t) =

{−1}, t < 0,
{−1,+1}, t = 0,
{+1}, t > 0
(c) Não é SCS, mas é SCI
A(t) =

{−1}, t < 0,
∅, t = 0,
{+1}, t > 0
*Exerćıcio 2.8. (Closed graph theorem) Dada uma correspondênciaA : T ⇒
X, defina o gráfico de A como
Gr(A) := {(t, x) : t ∈ T, x ∈ A(t)}.
(a) Mostre que, se o gráfico de A é fechado, A é SCS.
(b) Agora a rećıproca: se A é SCS, Gr(A) é um conjunto fechado.
*Exerćıcio 2.9. (Open graph theorem) Mostre que, se Gr(A) é um conjunto
aberto, A é SCI.
Teorema 2.3: Teorema do máximo de Berge
Seja a função objetivo f : X ⊆ Rn × T ⊆ Rk → R cont́ınua, e a
correspondência A : T ⇒ X cont́ınua, com cada A(t) compacto. Então
o problema de maximização
max
x∈A(t)
f(x, t)
tem função valor V (t) cont́ınua, e solução x∗(t) SCS.
Prova. Como, para cada t, f(·, t) é cont́ınua em A(t) compacto,
Weierstraß garante que existe máximo, logo x∗(t) nunca é o conjunto
vazio. Tome qualquer (tn) ⊆ T tal que tn → t ∈ T e qualquer
(xn) ⊂ X tal que cada xn ∈ x∗(tn) e tal que xn → x ∈ X. Sabemos
que x∗(t) ⊆ A(t) e que A é SCS, então x ∈ A(t). Mas suponha que
12
x /∈ x∗(t). Então existe z ∈ A(t) tal que f(z, t) > f(x, t). Como A é
SCI, existe alguma sequência (zn) ⊂ T tal que zn ∈ A(tn) e zn → z.
Como xn tem que ser o máximo de cada A(tn), para todo n vale
f(xn, tn) ≥ f(zn, tn). Como f é cont́ınua, isso implica f(x, t) ≥ f(z, t),
o que contradiz a existência de z. Portanto, x ∈ x∗(t), mostrando que
x∗ é SCS.
Usando o fato de x∗ ser SCS, iremos mostrar que V (t) := f
(
x∗(t), t
)
é cont́ınua. Defina x̃(t) = x ∈ x∗(t), onde escolhemos apenas um
elemento de cada x∗(t). Tome qualquer sequência (tn) → t. Como x∗
é SCS e cada x̃(tn) ∈ x∗(tn), x̃(tn) → x̃(t). Como f é uma função
cont́ınua e
(
x̃(tn), tn
)
→
(
x̃(t), t
)
,
V (tn) = f
(
x̃(tn), tn
)
→ f
(
x̃(t), t
)
= V (t).
Como isso vale para tn → t arbitrária, V é cont́ınua.
Exerćıcio 2.10. Para cada exemplo abaixo, resolva a maximização echeque
se as implicações do Teorema de Berge valem.
(a) Função descont́ınua em t:
f(x, t) =
{
−(x− t− 1)2, t ≤ 0
1− (x+ t+ 1)2, t > 0
e A(t) = R.
(b) Função descont́ınua em x:
f(x, t) =
{
−1, x ≤ 0,
+1, x > 0
e A(t) = (−∞, t].
(c) Correspondência não-SCS:
f(x, t) = x e A(t) =
{
{−1}, t ≤ 0,
{+1}, t > 0
.
(d) Correspondência não-SCI:
f(x, t) = x e A(t) =

{−1}, t < 0,
{−1,+1}, t = 0,
{+1}, t > 0
.
13
Exerćıcio 2.11. Considere o problema de minimização de custo da firma que
escolhe a quantidade dos insumos x e y (com preço unitário) para produzir
z unidades de produto:
C(z) = min
f(x,y)≥z
x+ y onde f(x, y) = max
{
2x
1
3 , y
2
3
}
(a) Encontre a solução (x, y)∗(z).
(b) A correspondência (x, y)∗(z) é SCS? é SCI?
(c) O teorema de Berge se aplica?
2.4 Teorema do Hiperplano Separador
Teorema 2.4: Hiperplano Separador
Sejam o conjunto A ⊆ Rn convexo e fechado, e o ponto x /∈ A. Então,
existem p ∈ Rn \ {0} e c ∈ R tais que, para todo y ∈ A,
p · x ≥ c ≥ p · y.
Definição 2.4
O hiperplano gerado por p ∈ Rn \ {0} e c ∈ R é o conjunto H := {x ∈
Rn : p · x = c}. Diz-se que os pontos x ∈ Rn tais que pẋ > c estão
acima de H, e os pontos com pẋ < c estão abaixo de H.
Teorema 2.5: Hiperplano de Suporte
Sejam A ⊆ Rn convexo e x na fronteira de A. Então, existem p ∈
Rn \ {0} e c ∈ R tais que, para todo y ∈ A,
p · x ≥ c ≥ p · y.
Teorema 2.6: Hiperplano Separador para dois conjuntos
Sejam A,B ⊆ Rn convexos e disjuntos. Então, existem p ∈ Rn \ {0} e
14
c ∈ R tais que, para todos x ∈ A e y ∈ B,
p · x ≥ c ≥ p · y.
*Exerćıcio 2.12. (Segundo Teorema fundamental do Bem-Estar – Produção)
Seja Y a tecnologia de produção da firma 1 tal que Y seja um conjunto con-
vexo.
Definição. Um vetor de produção y ∈ Y é eficiente se não existe outro
vetor y′ ∈ Y tal que y′ ≥ y e y′ ̸= y
Prove que todo vetor de produção eficiente y ∈ Y , existe um vetor de
preços p ≥ 0 tal que y é a escolha maximizadora de lucro.
3 Questões de provas antigas
Questão (P1 2018). Uma firma produz um produto q ∈ R+ a partir de um
insumo z ∈ {1, 2}. Sua tecnologia Y é um conjunto de combinações viáveis
de (q, z). Há uma coleção de posśıveis tecnologias Y1. Nesse exerćıcio vamos
tentar obter resultados de estática comparativa prevendo como a firma reage
a mudanças de sua tecnologia. A firma busca maximizar o lucro:
π(Y ) = max
(q,z)∈Y
pq − wz,
onde p e w são preços positivos arbitrários, e fixos.
(a) Uma posśıvel relação de ordem em Y é Y ≤ Y ′ ⇐⇒ Y ⊂ Y ′. Para
essa relação de ordem, o que é um meet e o que é um join de duas
tecnologias Y e Y ′?
(b) Proponha uma relação de ordem em Y que garanta que π(Y ) seja cres-
cente em Y , para todos os preços p, w.
1Para evitar problemas com vazios, suponha que para todas as tecnologias Y ∈ Y,
temos que (0, 1) e (0, 2) ∈ Y .
15
(c) Para essa relação de ordem, é posśıvel garantir que π(Y ) seja super-
modular?
(d) Proponha uma relação de ordem em Y que garanta que a demanda pelo
fator z seja crescente em Y , para todos preços p, w.
Questão (P1 2020). Um agente decide com o objetivo de maximizar a
seguinte função:
yf(x)− zg(y)− tx,
onde f e g são funções estritamente crescentes e x, y, z e t são números reais
positivos.
Usando o Teorema de Topkis, investigue a validade de afirmações de
estática comparativa entre cada variável que o agente controla e o parâmetro
t (ou seja, afirme se cada variável é fracamente crescente ou decrescente em
t ou se não é posśıvel concluir nada a esse respeito), supondo que:
(a) O agente controla x e (y, z, t) são parâmetros.
(b) O agente controla (x, y) e (z, t) são parâmetros.
(c) O agente controla (x, y, z) e t é parâmetro.
Lembre-se de justificar cada resposta com base no Teorema de Topkis.
Questão (P2 2022 – Micro 2). Coautorias, nesse exerćıcio, são restritas a
duas pessoas que podem se juntar e escrever um paper de qualidade f(xi, yj),
em que xi é a habilidade do coautor i ∈ I ≡ {1, . . . , I} e yj é a habilidade
do coautor j ∈ J ≡ {1, . . . , J}, sendo que I > J . Com um paper de qual-
idade f(xi, yj), i pode receber ti, e, igualmente, j pode receber tj, tal que
ti + tj ≤ f(xi, yj) (ti é a utilidade do autor i e tj do autor j).
Definição. Um pareamento é dito estável se, para qualquer par (i, j),
não há incentivos para que eles briguem e formem pares alternativos (i, j′) e
(i′, j).
(a) Suponha que f : I × J → R seja supermodular. Prove que i’s maiores
se parearão com j’s maiores em um pareamento estável.
(b) Quais i’s ficarão sem coautores?
16
Questão (P1 2023). Um professor tem a tarefa de elaborar um prova para
seus alunos. Representamos formalmente esse processo como uma maxi-
mização envolvendo três quantidades: o grau de dificuldade da prova d ∈ R+,
o grau de criatividade das questões c ∈ R+ e o comprimento da prova ℓ ∈ R+.
Sua função objetivo é
a(−d2 − c/ℓ) + r(d) + b(c) + ℓp(x/c)
onde a, r, e p são funções crescentes (pode supor que elas são tantas vezes
diferenciáveis quanto desejar) que medem a acurária das notas, a reputação
de que o curso é dif́ıcil, a beleza da prova, e o número esperado de reclamações
que os alunos vão fazer sobre a correção da prova. x ∈ R+ é o grau de
exigência (ou “xatura”) dos alunos, um parâmetro exógeno que afeta as es-
colhas do professor.
(a) Usando o Teorema de Topkis, obtenha um resultado de estática com-
parativa para como c e d variam em resposta a um aumento de x,
considerando ℓ fixo. Você pode fazer suposições sobre a curvatura de
algumas das funções a, r, b, ou p (ie se são côncavas ou convexas),
conforme necessário. Mas deixe claro a suposição que está fazendo.
(b) Refaça o item acima, mas agora supondo que c, d, e ℓ variam em
resposta a um aumento de x. Explique porque o teorema pode não ser
aplicável dependendo da concavidade de p.
4 Gabaritos selecionados
*Exerćıcio 4.1. Seja f : Rn → R uma função com diferenças crescentes em
cada par (xi, xj). Iremos mostrar que, no Rn, essa condição coincide com a
supermodularidade.
(a) Mantenha todas as outras coordenadas fixas, e considere, por enquanto,
f(x, y, z). Mostre, pelas desigualdades, que como f tem DC em (x, z)
e em (y, z), também tem DC em
(
(x, y), z
)
.
Solução. Para mostrar que f tem DC em
(
(x, y), z
)
, precisamos mostrar
que vale
f(x′, y′, z′)− f(x, y, z′) ≥ f(x′, y′, z)− f(x, y, z).
17
Então manipulamos a expressão à esquerda, com o truque de subtrair
e somar:
f(x′, y′, z′)− f(x, y, z′) =
= f(x′, y′, z′)− f(x′, y, z′)︸ ︷︷ ︸
DC (y, z)
+ f(x′, y, z′)− f(x, y, z′)︸ ︷︷ ︸
DC (x, z)
≥ f(x′, y′, z)− f(x′, y, z) + f(x′, y, z)− f(x, y, z)
= f(x′, y′, z)− f(x, y, z).
(b) Repetindo esse processo para várias combinações de coordenadas, veja
que f tem diferenças crescentes em qualquer combinação de coorde-
nadas
(
(xi1 , . . . , xik), (xj1 , . . . , xjℓ)
)
. Nesse caso, o corolário se aplica,
garantindo que f é supermodular.
Solução. Podemos escrever qualquer combinação de variáveis do enun-
ciado como (y1, . . . , yn, t1, . . . , tn), sendo f DC em cada par (yi, tj). Pelo
item (a), f DC em (y1, t1), (y1, t2) =⇒ f DC em (y1, (t1, t2)). Como
f é DC em (y1, t3), (y1, t4), . . . , é DC em (y1, t). Mas, pelo mesmo
processo, f é DC em (y2, t). Logo, é DC em ((y1, y2), t). Repetindo,
sucessivamente, f é DC em (y, t).
Sabemos que f é SM em x1 e em x2, pois são números reais. Como é
DC em (x1, x2), o corolário 1.1 diz que f é SM em (x1, x2). Pelo que
provamos acima, f é DC em ((x1, x2), x3). Como f também é SM em
(x1, x2) e em x3, é SM em (x1, x2, x3). Repita para todas as coordenadas
e temos f supermodular.
(c) Relembre o Teorema 1.2. Veja que, pelo item (b) acima, se f é duas
vezes diferenciável e todas as derivadas parciais mistas atendem ∂j∂if ≥
0, f é supermodular.
Solução. Consequência imediata do item (b), as derivadas dizem que é
DC em todas as combinações (x, t), e o item (b) dizque isso garante
SM.
18
*Exerćıcio 4.2. (Closed graph theorem) Dada uma correspondênciaA : T ⇒
X, defina o gráfico de A como
Gr(A) := {(t, x) : t ∈ T, x ∈ A(t)}.
(a) Mostre que, se o gráfico de A é fechado, A é SCS.
Solução. Sejam (tn) ⊆ T com tn → t e xn ∈ A(tn) tal que xn →
x. Para que seja SCS, temos que mostrar que x ∈ A(t). Temos que
Gr(A) é um conjunto fechado, e a sequência (xn, tn) está contida no
conjunto e é convergente, já que as duas coordenadas convergem. Por
isso (xn, tn) → (x, t) ∈ Gr(A). Pela definição do gráfico, x ∈ A(t),
provando SCS.
(b) Agora a rećıproca: se A é SCS, Gr(A) é um conjunto fechado.
Solução. Tome uma sequência convergente (xn, tn) ∈ Gr(A), e seja seu
limite (x, t). Para que o conjunto seja fechado, precisamos mostrar
que (x, t) ∈ Gr(A). Por definição do gráfico, xn ∈ A(tn), e pelo con-
vergência do vetor, xn → x e tn → t. Como A é SCS, vale x ∈ A(t).
*Exerćıcio 4.3. (Open graph theorem) Mostre que, se Gr(A) é um conjunto
aberto, A é SCI.
Solução. Tome alguma tn → t ∈ T e x ∈ A(t). Queremos mostrar que existe
sequência xn ∈ A(tn) tal que xn → x. Temos que (x, t) ∈ Gr(A), um conjunto
aberto. Então existe ε > 0 tal que todo ponto com ∥(x′, t′)− (x, t)∥ < ε está
contido em Gr(A). Pela convergência de tn, existe N ∈ N tal que, para todo
n ≥ N , |tn − t| < ε. Por isso, o ponto (x, tn) tem distância < ε de (x, t) e
pertence ao gráfico, com x ∈ A(tn). Repetindo para εn = ε/n → 0, vemos
que a sequência constante xn ≡ x atende xn ∈ A(tn) (pelo menos para n
grande, antes disso poderia ter quaisquer outros valores), e xn → x.
*Exerćıcio 4.4. (Segundo Teorema fundamental do Bem-Estar – Produção)
Seja Y a tecnologia de produção da firma 1 tal que Y seja um conjunto con-
vexo.
Definição. Um vetor de produção y ∈ Y é eficiente se não existe outro
vetor y′ ∈ Y tal que y′ ≥ y e y′ ̸= y
19
Prove que todo vetor de produção eficiente y ∈ Y , existe um vetor de
preços p ≥ 0 tal que y é a escolha maximizadora de lucro.
Solução. Temos Y convexo, e y eficiente. Em toda vizinhança Bε(y) ao redor
de y, há pontos fora de Y (todos y′ > y), e há pontos dentro de Y (por ser
convexo, todas as combinações convexas entre y e outro ponto estão em Y ).
Por isso, y ∈ ∂Y . Pelo Teorema do Hiperplano de Suporte, existem p ̸= 0 e
c ∈ R tais que, para todo ỹ ∈ Y ,
py ≥ c ≥ pỹ.
Ou seja, y maximiza lucros. Mas não provamos que p ≥ 0. Suponha, por
absurdo, que p ̸≥ 0. Então existe algum pi < 0. Seja ỹ = y − εei, reduzindo
um pouco a coordenada i de y. Teremos, então, py < pỹ, uma contradição.
Logo, p ≥ 0.
20
	Reticulados e supermodularidade
	Join e meet
	Reticulados e subreticulados
	Supermodularidade e Diferenças Crescentes
	Estática comparativa
	Teorema do Envelope
	Teorema de Topkis
	Teorema do Máximo de Berge
	Teorema do Hiperplano Separador
	Questões de provas antigas
	Gabaritos selecionados