Теорема о конверте

редактировать

Теорема о конверте является результатом о свойствах дифференцируемости функции значения параметризованная задача оптимизации. Когда мы изменяем параметры цели, теорема о конверте показывает, что в определенном смысле изменения в оптимизаторе цели не влияют на изменение целевой функции. Теорема о конверте является важным инструментом для сравнительной статики моделей оптимизации.

Содержание

1 Утверждение
2 Для произвольных наборов выбора
3 Приложения
- 3.1 Приложения к теории производителей
- 3.2 Приложения к разработке механизмов и теории аукционов
- 3.3 Приложения к многомерным пространствам параметров
- 3.4 Приложения к параметризованным ограничениям
- 3.5 Другие приложения
4 См. Также
5 Ссылки

Утверждение

Пусть $f (x, α) {\ displaystyle f (x, \ alpha)}$ ${\ displaystyle f (x, \ альфа)}$ и $gj (x, α), j = 1, 2,…, m {\ displaystyle g_ {j} (x, \ alpha), j = 1,2, \ ldots, m}$ ${\ displaystyle g_ {j} (x, \ alpha), j = 1,2, \ ldots, m}$ непрерывно действительнозначные дифференцируемые функции на $R n + l {\ displaystyle \ mathbb {R} ^ {n + l}}$ ${\ displaystyle \ mathbb {R} ^ {n + l}}$ , где $x ∈ R n {\ displaystyle x \ in \ mathbb {R } ^ {n}}$ ${\ displaystyle x \ in \ mathbb {R} ^ {n}}$ - переменные выбора, а $α ∈ R l {\ displaystyle \ alpha \ in \ mathbb {R} ^ {l}}$ ${\ displaystyle \ alpha \ in \ mathbb {R} ^ {l}}$ - параметры, и рассмотрим проблему выбора $x {\ displaystyle x}$ $x$ для заданного $α {\ displaystyle \ alpha}$ $\ alpha$ , чтобы:

max xf (x, α) {\ displaystyle \ max _ { x} f (x, \ alpha)}

{\ displaystyle \ max _ {x} f (x, \ alpha)}

с учетом

gj (x, α) ≥ 0, j = 1, 2,…, m {\ displaystyle g_ {j} (x, \ альфа) \ geq 0, j = 1,2, \ ldots, m}

{\ displaystyle g_ {j} (x, \ alpha) \ geq 0, j = 1,2, \ ldots, m}

x ≥ 0 {\ displaystyle x \ geq 0}

x \ geq 0

Лагранжево выражение этой проблемы дается

L (x, λ, α) знак равно е (x, α) + λ ⋅ g (x, α) {\ displaystyle {\ mathcal {L}} (x, \ lambda, \ alpha) = f (x, \ alpha) + \ lambda \ cdot g (x, \ alpha)}

{\ Displaystyle {\ mathcal {L}} (х, \ лямбда, \ alp ha) = f (x, \ alpha) + \ lambda \ cdot g (x, \ alpha)}

где $λ ∈ R m {\ displaystyle \ lambda \ in \ mathbb {R} ^ {m}}$ ${\ displaystyle \ lambda \ in \ mathbb {R} ^ {m}}$ - множители Лагранжа. Теперь пусть $x ∗ (α) {\ displaystyle x ^ {\ ast} (\ alpha)}$ ${\ displaystyle x ^ {\ ast} (\ alpha)}$ и $λ ∗ (α) {\ displaystyle \ lambda ^ {\ ast} ( \ alpha)}$ $\lambda ^{\ast }(\alpha)$ вместе будут решением, которое максимизирует целевую функцию f с учетом ограничений (и, следовательно, являются седловыми точками лагранжиана),

L ∗ (α) ≡ е (Икс ∗ (α), α) + λ ∗ (α) ⋅ г (Икс ∗ (α), α), {\ Displaystyle {\ mathcal {L}} ^ {\ Ast} (\ альфа) \ эквив f (x ^ {\ ast} (\ alpha), \ alpha) + \ lambda ^ {\ ast} (\ alpha) \ cdot g (x ^ {\ ast} (\ alpha), \ alpha),}

{\mathcal {L}}^{\ast }(\alpha)\equiv f(x^{\ast }(\alpha),\alpha)+\lambda ^{\ast }(\alpha)\cdot g(x^{\ast }(\alpha),\alpha),

и определим функцию значения

V (α) ≡ f (x ∗ (α), α). {\ Displaystyle V (\ alpha) \ Equiv f (x ^ {\ ast} (\ alpha), \ alpha).}

{\ displaystyle V (\ alpha) \ Equiv f (x ^ {\ ast} (\ alpha), \ alpha).}

Тогда имеем следующую теорему.

Теорема: Предположим, что $V {\ displaystyle V}$ $V$ и $L {\ displaystyle {\ mathcal {L}}}$ ${\ mathcal {L}}$ непрерывно дифференцируемы. Тогда

∂ V (α) ∂ α k = ∂ L ∗ (α) ∂ α k = ∂ L (x ∗ (α), λ ∗ (α), α) ∂ α k, k = 1, 2, …, L {\ displaystyle {\ frac {\ partial V (\ alpha)} {\ partial \ alpha _ {k}}} = {\ frac {\ partial {\ mathcal {L}} ^ {\ ast} (\ альфа)} {\ partial \ alpha _ {k}}} = {\ frac {\ partial {\ mathcal {L}} (x ^ {\ ast} (\ alpha), \ lambda ^ {\ ast} (\ alpha), \ alpha)} {\ partial \ alpha _ {k}}}, k = 1,2, \ ldots, l}

{\ displaystyle {\ frac {\ partial V (\ alpha)} {\ partial \ alpha _ {k}}} = { \ frac {\ partial {\ mathcal {L}} ^ {\ ast} (\ alpha)} {\ partial \ alpha _ {k}}} = {\ frac {\ partial {\ mathcal {L}} (x ^ {\ ast} (\ alpha), \ lambda ^ {\ ast} (\ alpha), \ alpha)} {\ partial \ alpha _ {k}}}, k = 1,2, \ ldots, l}

где $∂ L / ∂ α k = ∂ f / ∂ α k + λ ⋅ ∂ г / ∂ α К {\ Displaystyle \ partial {\ mathcal {L}} / \ partial \ alpha _ {k} = \ partial f / \ partial \ alpha _ {k} + \ lambda \ cdot \ partial g / \ partial \ alpha _ {k}}$ ${\ displaystyle \ partial {\ mathcal {L}} / \ partial \ alpha _ {k} = \ partial f / \ partial \ alpha _ {k} + \ lambda \ cdot \ partial g / \ partial \ alpha _ {k}}$ .

Для произвольных наборов выбора

Пусть $X {\ displaystyle X}$ $Икс$ обозначает набор выбора и пусть соответствующий параметр будет $t ∈ [0, 1] {\ displaystyle t \ in \ lbrack 0,1]}$ $t \ in \ lbrack 0,1]$ . Пусть $f: X × [0, 1] → R {\ displaystyle f: X \ times \ lbrack 0,1] \ rightarrow R}$ $f: X \ times \ lbrack 0,1] \ rightarrow R$ обозначает параметризованную целевую функцию, функцию значения $V {\ displaystyle V}$ $V$ и соответствие оптимального выбора (многозначная функция) $X ∗ {\ displaystyle X ^ {\ ast}}$ $X ^ {{\ ast}}$ задаются следующим образом:

V (T) знак равно sup x ∈ X е (x, t) {\ displaystyle V (t) = \ sup _ {x \ in X} f (x, t)}

V (t) = \ sup _ {{x \ in X}} f (x, t)

(1)

Икс * (t) = {x ∈ X: f (x, t) = V (t)} {\ displaystyle X ^ {\ ast} (t) = \ {x \ in X: f (x, t) = V (t) \}}

X ^ {{\ ast}} (t) = \ {x \ in X: f (x, t) = V (t) \}

(2)

«Теоремы о конверте» описывают достаточные условия для того, чтобы функция значения $V {\ displaystyle V}$ $V$ была дифференцируемые по параметру $t {\ displaystyle t}$ $t$ и описываем его производную как

V ′ (t) = ft (x, t) для каждого x ∈ X ∗ (t), { \ Displaystyle V ^ {\ prime} \ left (t \ right) = f_ {t} \ left (x, t \ right) {\ text {для каждого}} x \ in X ^ {\ ast} \ left (t \ right),}

{\ displaystyle V ^ {\ prime} \ left (t \ right) = f_ {t} \ left (x, t \ right) {\ text {для каждого}} x \ in X ^ {\ ast} \ left(t\right),}

(3)

где $ft {\ displaystyle f_ {t}}$ $f _ {{t}}$ обозначает частную производную тив $f {\ displaystyle f}$ $f$ по отношению к $t {\ displaystyle t}$ $t$ . А именно, производная функции значения по параметру равна частной производной целевой функции по $t {\ displaystyle t}$ $t$ , удерживая максимизатор на оптимальном уровне. (Термин происходит от описания графика $V {\ displaystyle V}$ $V$ как «верхней оболочки» графиков параметризованного семейства функций ${f (x, ⋅)} x ∈ X {\ displaystyle \ left \ {f \ left (x, \ cdot \ right) \ right \} _ {x \ in X}}$ $\ left \ {f \ left (x, \ cdot \ right) \ right \} _ {{x \ in X}}$ .)

Традиционная теорема о конверте в выводах используется условие первого порядка для (1), которое требует, чтобы выборка $X {\ displaystyle X}$ $Икс$ имела выпуклую и топологическую структуру, а целевая функция $f {\ displaystyle f}$ $f$ быть дифференцируемым в переменной $x {\ displaystyle x}$ $x$ . (Аргумент состоит в том, что изменения в максимизаторе имеют только «эффект второго порядка» в оптимуме и поэтому их можно игнорировать.) Однако во многих приложениях, таких как анализ ограничений стимулов в теории контрактов и теории игр, невыпуклые производственные задачи, и «монотонная» или «устойчивая» сравнительная статика, наборы выбора и целевые функции обычно лишены топологических свойств и свойств выпуклости, требуемых традиционными теоремами о конвертах.

Пол Милгром и Сигал (2002) отмечают, что традиционная формула огибающей верна для задач оптимизации с произвольными наборами выбора в любой точке дифференцируемости функции цены при условии, что целевая функция дифференцируема по параметру:

Теорема 1: Пусть $t ∈ (0, 1) {\ displaystyle t \ in \ left (0,1 \ right)}$ $t \ in \ left (0,1 \ right)$ и $x ∈ X ∗ (t) {\ displaystyle x \ in X ^ {\ ast} \ left (t \ right)}$ ${\ displaystyle x \ in X ^ {\ ast} \ left (t \ right)}$ . Если оба $V '(t) {\ displaystyle V ^ {\ prime} \ left (t \ right)}$ $V ^ {{\ prime}} \ left (t \ right)$ и $ft (x, t) {\ displaystyle f_ {t} \ left (x, t \ right)}$ ${\ displaystyle f_ {t} \ left (x, t \ right)}$ существует, формула конверта (3) верна.

Доказательство: (1) означает, что для $x ∈ X ∗ (t) {\ displaystyle x \ in X ^ {\ ast} \ left (t \ right)}$ $x \ in X ^ {{\ ast}} \ left (t \ справа)$ ,

max s ∈ [0, 1] [е (х, s) - V (s)] = е (x, t) - V (t) = 0. {\ displaystyle \ max _ {s \ in \ left [0,1 \ right]} \ left [е \ left (x, s \ right) -V \ left (s \ right) \ right] = f \ left (x, t \ right) -V \ left (t \ right) = 0.}

\ max _ {{s \ in \ left [0,1 \ right]}} \ left [f \ left (x, s \ right) -V \ left (s \ right) \ right] = f \ left (x, t \ right) -V \ left (t \ right) = 0.

Согласно предположениям, целевая функция отображаемой задачи максимизации дифференцируема при $s = t {\ displaystyle s = t}$ $s = t$ , и условие первого порядка для этой максимизации ровно (3). Q.E.D.

В то время как дифференцируемость функции цены в целом требует сильных предположений, во многих приложениях достаточно более слабых условий, таких как абсолютная непрерывность, дифференцируемость почти всюду или дифференцируемость слева и справа. В частности, теорема 2 Милгрома и Сигала (2002) предлагает достаточное условие для абсолютной непрерывности $V {\ displaystyle V}$ $V$ , что означает, что оно дифференцируемо почти всюду и может быть представлено как интеграл от производной:

Теорема 2: Предположим, что $f (x, ⋅) {\ displaystyle f (x, \ cdot)}$ $f(x,\cdot)$ абсолютно непрерывно для всех $Икс ∈ Икс {\ Displaystyle х \ в Х}$ $x \ in X$ . Предположим также, что существует интегрируемая функция $b: [0, 1] {\ displaystyle b: [0,1]}$ $b: [0,1]$ $→ {\ displaystyle \ rightarrow}$ $\ rightarrow$ $R + {\ displaystyle \ mathbb { R} _ {+}}$ $\ mathbb {R} _ {+}$ такой, что $| f t (x, t) | ≤ b (t) {\ displaystyle | f_ {t} (x, t) | \ leq b (t)}$ $|f_{{t}}(x,t)|\leq b(t)$ для всех $x ∈ X {\ displaystyle x \ in X}$ $x \ in X$ и почти все $t ∈ [0, 1] {\ displaystyle t \ in \ lbrack 0,1]}$ $t \ in \ lbrack 0,1]$ . Тогда $V {\ displaystyle V}$ $V$ абсолютно непрерывен. Предположим, кроме того, что $f (x, ⋅) {\ displaystyle f (x, \ cdot)}$ $f(x,\cdot)$ дифференцируем для всех $x ∈ X {\ displaystyle x \ in X}$ $x \ in X$ , и что $X ∗ (t) ≠ ∅ {\ displaystyle X ^ {\ ast} (t) \ neq \ varnothing}$ $X^{{\ast }}(t)\neq \varnothing$ почти везде на $[0, 1] {\ displaystyle [0,1]}$ $[0,1]$ . Тогда для любого выбора $x ∗ (t) ∈ X ∗ (t) {\ displaystyle x ^ {\ ast} (t) \ in X ^ {\ ast} (t)}$ $x ^ {{\ ast}} (t) \ in X ^ {{\ ast}} (t)$ ,

V (t) = V (0) + ∫ 0 tft (x ∗ (s), s) ds. {\ displaystyle V (t) = V (0) + \ int _ {0} ^ {t} f_ {t} (x ^ {\ ast} (s), s) ds.}

V (t) = V (0) + \ int _ {{0}} ^ {{t}} f _ {{t}} (x ^ {{\ ast}} (s), s) ds.

( 4)

Доказательство: Используя (1), заметьте, что для любых $t ′, t ′ ′ ∈ [0, 1] {\ displaystyle t ^ {\ prime}, t ^ {\ prime \ prime} \ in \ lbrack 0,1]}$ ${\ displaystyle t ^ {\ prime}, t ^ {\ prime \ prime} \ in \ lbrack 0,1]}$ с $t ′ < t ′ ′ {\displaystyle t^{\prime }$ $t ^ {{\ prime }} <t ^ {{\ prime \ prime}}$ ,

| V (t ′ ′) - V (t ′) | ≤ sup x ∈ X | f (x, t ′ ′) - f (x, t ′) | = sup x ∈ X | ∫ t ′ t ′ ′ f t (x, t) d t | ≤ ∫ t ′ t ′ ′ sup x ∈ X | f t (x, t) | d t ≤ ∫ t ′ t ′ ′ b (t) d t. {\ Displaystyle | V (T ^ {\ prime \ prime}) - V (t ^ {\ prime}) | \ Leq \ sup _ {x \ in X} | е (х, t ^ {\ prime \ prime}) -f (x, t ^ {\ prime}) | = \ sup _ {x \ in X} \ left \ vert \ int _ {t ^ {\ prime}} ^ {t ^ {\ prime \ prime}} f_ {t} (x, t) dt \ right \ vert \ leq \ int _ {t ^ {\ prime}} ^ {t ^ {\ prime \ prime}} \ sup _ {x \ in X} | f_ { t} (x, t) | dt \ leq \ int _ {t ^ {\ prime}} ^ {t ^ {\ prime \ prime}} b (t) dt.}

{\ Displaystyle | V (t ^ {\ prime \ prime}) - V (t ^ {\ prime}) | \ leq \ sup _ {x \ in X} | е (x, t ^ {\ prime \ prime}) - f (x, t ^ {\ prime}) | = \ sup _ {x \ in X} \ left \ vert \ int _ {t ^ {\ prime}} ^ {t ^ {\ prime \ prime}} f_ {t} (x, t) dt \ right \ vert \ leq \ int _ {t ^ {\ prime}} ^ {t ^ {\ prime \ prime}} \ sup _ {x \ in X} | f_ {t} (x, t) | dt \ leq \ int _ {t ^ {\ prime}} ^ {t ^ {\ prime \ prime}} b (t) dt. }

Отсюда следует, что $V {\ displaystyle V}$ $V$ абсолютно непрерывен. Следовательно, $V {\ displaystyle V}$ $V$ дифференцируем почти всюду, и использование (3) дает (4). Q.E.D.

Этот результат развенчивает распространенное заблуждение, что хорошее поведение функции значения требует соответственно хорошего поведения максимизатора. Теорема 2 гарантирует абсолютную непрерывность функции ценности, даже если максимизатор может быть прерывистым. Аналогичным образом, из теоремы 3 Милгрома и Сигала (2002) следует, что функция цены должна быть дифференцируемой в $t = t 0 {\ displaystyle t = t_ {0}}$ $t=t_{{0}}$ и, следовательно, удовлетворять условиям оболочки формула (3), когда семья ${е (х, ⋅)} x ∈ X {\ displaystyle \ left \ {f \ left (x, \ cdot \ right) \ right \} _ {x \ in X} }$ $\ left \ {f \ left (x, \ cdot \ right) \ right \} _ {{x \ in X}}$ равно-дифференцируемо в $t 0 ∈ (0, 1) {\ displaystyle t_ {0} \ in \ left (0,1 \ right)}$ $t _ {{0}} \ in \ left (0,1 \ right)$ и $ft (X ∗ (t), t 0) {\ displaystyle f_ {t} \ left (X ^ {\ ast} \ left (t \ right), t_ {0} \ right)}$ ${\ displaystyle f_ {t} \ left (X ^ {\ ast} \ left (t \ right), t_ {0} \ right)}$ является однозначным и непрерывным при $t = t 0 {\ displaystyle t = t_ {0}}$ $t=t_{{0}}$ , даже если максимизатор не дифференцируемый при $t 0 {\ displaystyle t_ { 0}}$ $t_{{0}}$ (например, если $X {\ displaystyle X}$ $Икс$ описывается набором ограничений неравенства, а набор ограничений привязки изменяется в $t 0 { \ displaystyle t_ {0}}$ $t_{{0}}$ ).

Приложения

Приложения к теории производителей

Из теоремы 1 следует лемма Хотеллинга при любом различии точка способности функции прибыли, а из теоремы 2 следует формула излишка производителя. Формально, пусть $π (p) {\ displaystyle \ pi \ left (p \ right)}$ $\ pi \ left (p \ right)$ обозначает функцию прибыли фиксирующей цену фирмы с производственным набором $X ⊆ RL {\ displaystyle X \ substeq \ mathbb {R} ^ {L}}$ $X \ substeq {\ mathbb {R}} ^ {{L}}$ с учетом цен $p ∈ RL {\ displaystyle p \ in \ mathbb {R} ^ {L}}$ $p \ in {\ mathbb {R}} ^ {{L}}$ , и пусть $x ∗ (p) {\ displaystyle x ^ {\ ast} \ left (p \ right)}$ $x ^ {{\ ast}} \ left (p \ right)$ обозначает функцию предложения фирмы, т. е.

π (p) = max x ∈ X p ⋅ x = p ⋅ x ∗ (p). {\ displaystyle \ pi (p) = \ max _ {x \ in X} p \ cdot x = p \ cdot x ^ {\ ast} \ left (p \ right) {\ text {.}}}

\ pi (p) = \ max _ {{x \ in X}} p \ cdot x = p \ cdot x ^ {{\ ast}} \ left (p \ right) { \ text {.}}

Пусть $t = pi {\ displaystyle t = p_ {i}}$ $t = p _ {{i}}$ (цена товара $i {\ displaystyle i}$ $i$ ) и исправит другие товары ' цены на $p - i ∈ RL - 1 {\ displaystyle p _ {- i} \ in \ mathbb {R} ^ {L-1}}$ $p_{-i}\in \mathbb {R} ^{L-1}$ . Применение теоремы 1 к $f (x, t) = txi + p - i ⋅ x - i {\ displaystyle f (x, t) = tx_ {i} + p _ {- i} \ cdot x _ {- i} }$ $f (x, t) = tx _ {{i}} + p _ {{- i}} \ cdot x _ {{- i}}$ дает $∂ π (p) ∂ pi = xi ∗ (p) {\ displaystyle {\ frac {\ partial \ pi (p)} {\ partial p_ {i}}} = x_ {i} ^ {\ ast} (p)}$ ${\ frac {\ partial \ pi (p)} {\ partial p _ {{i}}}} = x _ {{i}} ^ {{\ ast}} (p)$ (оптимальное предложение товаров фирмы $i {\ displaystyle i}$ $i$ ). Применение теоремы 2 (предположения которой проверяются, когда $pi {\ displaystyle p_ {i}}$ $p_ {i}$ ограничено ограниченным интервалом) дает

π (t, p - i) - π (0, п - я) знак равно ∫ 0 pixi ∗ (s, p - я) ds, {\ displaystyle \ pi (t, p _ {- i}) - \ pi (0, p _ {- i}) = \ int _ { 0} ^ {p_ {i}} x_ {i} ^ {\ ast} (s, p _ {- i}) ds,}

{\ displaystyle \ pi (t, p _ {- i}) - \ pi (0, p _ {- i}) = \ int _ {0} ^ {p_ {i}} x_ {i} ^ {\ ast} (s, p_ { -i}) ds,}

т.е. излишек производителя $π (t, p - i) - π (0, p - i) {\ displaystyle \ pi (t, p _ {- i}) - \ pi (0, p _ {- i})}$ ${\ displaystyl e \ pi (t, p _ {- i}) - \ pi (0, p _ {- i})}$ можно получить путем интегрирования по кривой предложения фирмы для товара $i {\ displaystyle i}$ $i$ .

Приложения к моделированию механизмов и теории аукционов

Рассмотрим агента, функция полезности которого $f (x, t) {\ displaystyle f (x, t)}$ $f ( x, t)$ по результатам $x ∈ X ¯ {\ displaystyle x \ in {\ bar {X}}}$ ${\ displaystyle x \ in {\ bar {X}}}$ зависит от его типа $t ∈ [0, 1] {\ displaystyle t \ in \ lbrack 0,1]}$ $t \ in \ lbrack 0,1]$ . Пусть $X ⊆ X ¯ {\ displaystyle X \ substeq {\ bar {X}}}$ $X \ substeq {\ bar {X}}$ представляет «меню» возможных результатов, которые агент может получить в механизме, посылая различные сообщения. Тогда равновесная полезность агента $V (t) {\ displaystyle V (t)}$ $V (t)$ в механизме задается выражением (1), а множество $X ∗ (t) {\ displaystyle X ^ {\ ast} (t)}$ $X^{{\ast }}(t)$ результатов равновесия механизма определяется выражением (2). Любой выбор $x ∗ (t) ∈ X ∗ (t) {\ displaystyle x ^ {\ ast} (t) \ in X ^ {\ ast} (t)}$ $x ^ {{\ ast}} (t) \ in X ^ {{\ ast}} (t)$ является правилом выбора реализуется механизмом. Предположим, что функция полезности агента $f (x, t) {\ displaystyle f (x, t)}$ $f ( x, t)$ дифференцируема и абсолютно непрерывна в $t {\ displaystyle t}$ $t$ для всех $x ∈ Y {\ displaystyle x \ in Y}$ $x\in Y$ , и что $sup x ∈ X ¯ | f t (x, t) | {\ displaystyle \ sup _ {x \ in {\ bar {X}}} | f_ {t} (x, t) |}$ $\ sup _ {{x \ in {\ bar {X}}}}} | f _ {{t}} (x, t) |$ интегрируется на $[0, 1] {\ displaystyle [0,1]}$ $[0,1]$ . Тогда из теоремы 2 следует, что равновесная полезность агента $V {\ displaystyle V}$ $V$ в любом механизме, реализующем данное правило выбора $x ∗ {\ displaystyle x ^ {\ ast}}$ $x ^ {{\ ast}}$ должен удовлетворять интегральному условию (4).

Интегральное условие (4) является ключевым этапом в анализе проблем проектирования механизмов с непрерывными пространствами типов. В частности, в проведенном Майерсоном (1981) анализе аукционов отдельных товаров результат с точки зрения одного участника торгов может быть описан как $x = (y, z) {\ displaystyle x = \ left (y, z \ right)}$ $x = \ left (y, z \ right)$ , где $y {\ displaystyle y}$ $Y$ - вероятность того, что участник торгов получит объект, а $z {\ displaystyle z}$ $z$ - его ожидаемый платеж, а ожидаемая полезность участника торгов принимает форму $f ((y, z), t) = ty - z {\ displaystyle f \ left (\ left (y, z \ right), t \ right) = ty-z}$ $f\left(\left(y,z\right),t\right)=ty-z$ . В этом случае, если $t _ {\ displaystyle {\ underline {t}}}$ $\ underline {t}$ обозначает наименьший возможный тип участника торгов, интегральное условие (4) для равновесной ожидаемой полезности участника торгов $V {\ displaystyle V}$ $V$ принимает форму

V (t) - V (t _) = ∫ 0 ty ∗ (s) ds. {\ displaystyle V (t) -V ({\ underline {t}}) = \ int _ {0} ^ {t} y ^ {\ ast} (s) ds.}

V (t) -V (\ underline {t}) = \ int _ {{0}} ^ {{t}} y ^ {{\ ast}} (s) ds.

(Это уравнение можно интерпретировать в качестве формулы излишка производителя для фирмы, чья производственная технология конвертирует numeraire $z {\ displaystyle z}$ $z$ в вероятность $y {\ displaystyle y}$ $Y$ выигрыша объекта определяется аукционом и перепродает объект по фиксированной цене $t {\ displaystyle t}$ $t$ ). Это условие, в свою очередь, приводит к знаменитой теореме эквивалентности доходов Майерсона (1981): ожидаемый доход, полученный на аукционе, на котором участники торгов имеют независимые частные значения, полностью определяется вероятностями участников $y ∗ (t) {\ displaystyle y ^ {\ ast} \ left (t \ right)}$ $y ^ {{\ ast}} \ left (t \ right)$ получения объекта для всех типов $t {\ displaystyle t}$ $t$ , а также ожидаемые выплаты $V (t _) {\ displaystyle V ({\ underline {t}})}$ $V (\ underline {t})$ наименьших типов участников торгов. Наконец, это условие является ключевым шагом в работе Майерсона (1981) об оптимальных аукционах.

О других приложениях теоремы о конверте к конструкции механизмов см. Mirrlees (1971), Holmstrom (1979), Laffont and Maskin (1980)., Райли и Самуэльсон (1981), Фуденберг и Тирол (1991) и Уильямс (1999). Хотя эти авторы вывели и использовали теорему о конверте, ограничивая внимание (кусочно) непрерывно дифференцируемыми правилами выбора или даже более узкими классами, иногда может быть оптимальным реализовать правило выбора, которое не является кусочно непрерывно дифференцируемым. (Одним из примеров является класс торговых задач с линейной полезностью, описанный в главе 6.5 Майерсона (1991).) Обратите внимание, что интегральное условие (3) все еще выполняется в этой ситуации и дает такие важные результаты, как лемма Холмстрома (Holmstrom, 1979), Лемма Майерсона (Myerson, 1981), теорема об эквивалентности доходов (для аукционов), теорема Грина – Лаффонта – Холмстрома (Green, Laffont, 1979; Holmstrom, 1979), теорема Майерсона – Саттертуэйта (Myerson and Satterthwaite, 1983), теоремы невозможности Jehiel – Moldovanu (Jehiel and Moldovanu, 2001), теоремы McAfee – McMillan о слабых картелях (McAfee and McMillan, 1992) и теорема Мартингала Вебера (Weber, 1983) и т. д. Подробности этих приложений представлены в Глава 3 Милгрома (2004), который предлагает элегантную и объединяющую основу для анализа аукционов и проектирования механизмов, в основном основанную на теореме конверта и других знакомых методах и концепциях теории спроса.

Приложения для многомерного пространства параметров

Для многомерного пространства параметров $T ⊆ RK {\ displaystyle T \ substeq \ mathbb {R} ^ {K}}$ $T \ substeq {\ mathbb {R}} ^ {{K}}$ , Теорема 1 может быть применена к частным производным и производным по направлениям функции цены. Если и целевая функция $f {\ displaystyle f}$ $f$ , и функция значения $V {\ displaystyle V}$ $V$ (полностью) дифференцируемы в $t { \ displaystyle t}$ $t$ , теорема 1 подразумевает формулу конверта для их градиентов: $∇ V (t) = ∇ tf (x, t) {\ displaystyle \ nabla V \ left (t \ right) = \ nabla _ {t} f \ left (x, t \ right)}$ $\ nabla V \ left (t \ right) = \ nabla _ {{t}} f \ left (x, t \ right)$ для каждого $x ∈ X ∗ (t) {\ displaystyle x \ in X ^ {\ ast} \ left (t \ вправо)}$ $x \ in X ^ {{\ ast}} \ left (t \ справа)$ . Хотя обеспечить полную дифференцируемость функции ценности может быть непросто, теорему 2 можно по-прежнему применять на любом гладком пути, соединяющем два значения параметра $t 0 {\ displaystyle t_ {0}}$ $t_{{0}}$ и $т {\ displaystyle t}$ $t$ . А именно, предположим, что функции $f (x, ⋅) {\ displaystyle f (x, \ cdot)}$ $f(x,\cdot)$ дифференцируемы для всех $x ∈ X {\ displaystyle x \ in X}$ $x \ in X$ с $| ∇ t f (x, t) | ≤ B {\ displaystyle | \ nabla _ {t} f (x, t) | \ leq B}$ $| \ nabla _ {{t}} f (x, t) | \ leq B$ для всех $x ∈ X, {\ displaystyle x \ in X,}$ $x \ in X,$ $T ∈ T {\ Displaystyle т \ в T}$ $t \ in T$ . Плавный путь от $t 0 {\ displaystyle t_ {0}}$ $t_{{0}}$ до $t {\ displaystyle t}$ $t$ описывается дифференцируемым отображением $γ: [0, 1] → T {\ displaystyle \ gamma: \ left [0,1 \ right] \ rightarrow T}$ ${\ displaystyle \ gamma: \ left [0,1 \ right] \ rightarrow T}$ с ограниченной производной, такой что $γ (0) = t 0 { \ Displaystyle \ gamma \ left (0 \ right) = t_ {0}}$ $\ gamma \ left (0 \ right) = t _ {{0}}$ и $γ (1) = t {\ displaystyle \ gamma \ left (1 \ right) = t}$ $\ gamma \ left (1 \ right) = t$ . Из теоремы 2 следует, что для любого такого гладкого пути изменение функции цены может быть выражено как интеграл по путям частичного градиента $∇ tf (x ∗ (t), t) {\ displaystyle \ nabla _ {t} f (x ^ {\ ast} (t), t)}$ ${\ displaystyle \ nabla _ {t} f (x ^ {\ ast} (t), t)}$ целевой функции вдоль пути:

V (t) - V (t 0) = ∫ γ ∇ tf (x ∗ (s), s) ⋅ ds. {\ displaystyle V (t) -V (t_ {0}) = \ int _ {\ gamma} \ nabla _ {t} f (x ^ {\ ast} (s), s) \ cdot ds.}

V (t) -V (t _ {{0}}) = \ int _ {{\ gamma}} \ nabla _ {{t}} f (x ^ {{\ ast}} (s), s) \ cdot ds.

В частности, для $t = t 0 {\ displaystyle t = t_ {0}}$ $t=t_{{0}}$ это устанавливает, что циклические интегралы по пути вдоль любого гладкого пути $γ {\ displaystyle \ gamma}$ $\ gamma$ должен быть равен нулю:

∫ ∇ tf (x ∗ (s), s) ⋅ ds = 0. {\ displaystyle \ int \ nabla _ {t} f (x ^ {\ ast} (s), s) \ cdot ds = 0.}

\ int \ nabla _ {{t}} f (x ^ {{\ ast }} (s), s) \ cdot ds = 0.

Это «условие интегрируемости» играет важную роль в разработке механизмов с многомерными типами, ограничивая тип правил выбора $x ∗ {\ displaystyle x ^ {\ ast} }$ $x ^ {{\ ast}}$ может поддерживаться с помощью меню, вызванного механизмами $X ⊆ X ¯ {\ displaystyle X \ substeq {\ bar {X}}}$ $X \ substeq {\ bar {X}}$ . Применительно к теории производителей, где $x ∈ X ⊆ RL {\ displaystyle x \ in X \ substeq \ mathbb {R} ^ {L}}$ ${\ displaystyle x \ в Икс \ substeq \ mathbb {R} ^ {L}}$ является вектором производства фирмы, а $t ∈ RL {\ displaystyle t \ in \ mathbb {R} ^ {L}}$ $t\in \mathbb {R} ^{L}$ - вектор цен, $f (x, t) = t ⋅ x {\ displaystyle f \ left (x, t \ right) = t \ cdot x}$ $f \ left (x, t \ right) = t \ cdot x$ , а условие интегрируемости говорит, что любая рационализируемая функция предложения $x ∗ {\ displaystyle x ^ {\ ast}}$ $x ^ {{\ ast}}$ должна удовлетворяет

∫ x ∗ (s) ⋅ ds = 0. {\ displaystyle \ int x ^ {\ ast} (s) \ cdot ds = 0.}

\ int x ^ {{\ ast}} (s) \ cdot ds = 0.

Когда $x ∗ {\ displaystyle x ^ {\ ast}}$ $x ^ {{\ ast}}$ непрерывно дифференцируемо, это условие интегрируемости эквивалентно симметрии матрицы подстановки $(∂ xi ∗ (t) / ∂ tj) i, j Знак равно 1 L {\ displaystyle \ left (\ partial x_ {i} ^ {\ ast} \ left (t \ right) / \ partial t_ {j} \ right) _ {i, j = 1} ^ {L}}$ ${\ displaystyle \ left (\ partial x_ {i} ^ {\ ast} \ left (t \ right) / \ partial t_ {j} \ right) _ {i, j = 1} ^ {L}}$ . (В теории потребителей тот же аргумент, примененный к задаче минимизации расходов, дает симметрию матрицы Слуцкого.)

Приложения к параметризованным ограничениям

Предположим теперь, что допустимое множество $X (t) {\ displaystyle X \ left (t \ right)}$ $X\left(t\right)$ зависит от параметра, то есть

V (t) = sup x ∈ X (T) е (Икс, T) {\ Displaystyle V (т) = \ sup _ {х \ в X \ влево (т \ вправо)} f (х, т)}

V (t) = \ sup _ {{x \ in X \ left (t \ right)}} f (x, t)

X * (т) = { Икс ∈ Икс (T): е (Икс, Т) = В (Т)}, {\ Displaystyle X ^ {\ Ast} (т) = \ {х \ в Х \ влево (т \ вправо): е (х, t) = V (t) \} {\ text {,}}}

X ^ {{\ ast}} (t) = \ {x \ in X \ left (t \ right): f (x, t) = V (t) \} {\ text {,}}

где $X (t) = {x ∈ X: g (x, t) ≥ 0} {\ displaystyle X \ left (t \ right) = \ left \ {x \ in X: g \ left (x, t \ right) \ geq 0 \ right \}}$ ${\ displaystyle X \ left (t \ right) = \ left \ {x \ in X: g \ left (x, t \ right) \ geq 0 \ right \}}$ для некоторого $g: X × [0, 1] → РК. {\ displaystyle g: X \ times \ left [0,1 \ right] \ rightarrow \ mathbb {R} ^ {K}.}$ $g: X \ times \ left [0,1 \ right] \ rightarrow {\ mathbb {R}} ^ {{K}}.$

Предположим, что $X {\ displaystyle X}$ $Икс$ - выпуклое множество, $f {\ displaystyle f}$ $f$ и $g {\ displaystyle g}$ $g$ вогнуты по $x {\ displaystyle x}$ $x$ , и существует $x ^ ∈ X {\ displaystyle {\ hat {x}} \ in X}$ ${\ hat {x}} \ in X$ такое, что $g (x ^, t)>0 { \ displaystyle g \ left ({\ hat {x}}, t \ right)>0}$ $g\left({\hat {x}},t\right)>0$ для всех $t ∈ [0, 1] {\ displaystyle t \ in \ left [0,1 \ right]}$ $t\in \left[0,1\right]$ . При этих предположениях хорошо известно, что указанная выше программа оптимизации с ограничениями может быть представлена как задача перевала для лагранжиана $L (x, λ, t) = f ( Икс, T) + λ ⋅ г (Икс, T) {\ Displaystyle L \ влево (х, \ лямбда, т \ справа) = е (х, т) + \ лямбда \ CDOT г \ влево (х, т \ вправо)}$ ${\ displaystyle L \ left (x, \ lambda, t \ right) = f (x, t) + \ lambda \ cdot g \ left (x, t \ right)}$ , где $λ ∈ R + K {\ displaystyle \ lam bda \ in \ mathbb {R} _ {+} ^ {K}}$ ${\ displaystyle \ lambda \ in \ mathbb {R} _ {+} ^ {K}}$ - вектор множителей Лагранжа, выбранный противником для минимизации лагранжиана. Это позволяет применять теорему об конверте Милгрома и Сигала (2002, теорема 4) для задач перевала при дополнительных предположениях, что $X {\ displaystyle X}$ $Икс$ является компактным множеством в нормированной линейной пробел, $f {\ displaystyle f}$ $f$ и $g {\ displaystyle g}$ $g$ непрерывны в $x {\ displaystyle x}$ $x$ и $ft {\ displaystyle f_ {t}}$ $f _ {{t}}$ и $gt {\ displaystyle g_ {t}}$ $g _ {{t}}$ непрерывны в $(x, t) {\ Displaystyle \ влево (х, т \ вправо)}$ $\ left (x, t \ right)$ . В частности, положив $(x ∗ (t), λ ∗ (t)) {\ displaystyle \ left (x ^ {\ ast} (t), \ lambda ^ {\ ast} \ left (t \ right) \ right)}$ ${\ displaystyle \ left (x ^ {\ ast} (t), \ lambda ^ {\ ast} \ left (t \ right) \ right)}$ обозначают седловую точку лагранжиана для значения параметра $t {\ displaystyle t}$ $t$ , из теоремы следует, что $V {\ displaystyle V}$ $V$ абсолютно непрерывен и удовлетворяет

V (t) = V (0) + ∫ 0 t L t (x ∗ (s), λ ∗ (s), s) ds. {\ Displaystyle V (T) = V (0) + \ int _ {0} ^ {t} L_ {t} (x ^ {\ ast} (s), \ lambda ^ {\ ast} \ left (s \ right), s) ds.}

{\ displaystyle V (t) = V (0) + \ int _ {0} ^ {t} L_ { t} (x ^ {\ ast} (s), \ lambda ^ {\ ast} \ left (s \ right), s) ds.}

Для особого случая, когда $f (x, t) {\ displaystyle f \ left (x, t \ right)}$ $f \ left (x, t \ right)$ не зависит от $t {\ displaystyle t}$ $t$ , $K = 1 {\ displaystyle K = 1}$ $K=1$ и $g (x, t) = h (x) + t {\ displaystyle g \ left (x, t \ right) = h \ left (x \ right) + t}$ $g \ left (x, t \ right) = h \ left (x \ right) + t$ , из формулы следует, что $V ′ (t) = L t (x ∗ (t), λ * (Т), т) знак равно λ * (т) {\ Displaystyle V ^ {\ простое} (т) = L_ {т} (х ^ {\ аст} (т), \ лямбда ^ {\ аст} \ влево (t \ right), t) = \ lambda ^ {\ ast} \ left (t \ right)}$ ${\ displaystyle V ^ {\ prime} (t) = L_ { t} (x ^ {\ ast} (t), \ lambda ^ {\ ast} \ left (t \ right), t) = \ lambda ^ {\ ast} \ left (t \ right)}$ для п.в. $т {\ displaystyle t}$ $t$ . То есть множитель Лагранжа $λ ∗ (t) {\ displaystyle \ lambda ^ {\ ast} \ left (t \ right)}$ ${\ displaystyle \ lambda ^ {\ ast} \ left (t \ right)}$ на ограничении является его «теневой ценой "в программе оптимизации.

Другие приложения

Милгром и Сигал (2002) демонстрируют, что обобщенная версия теорем огибающей также может применяться к выпуклому программированию, задачам непрерывной оптимизации, -точечные задачи и задачи оптимальной остановки.