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

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

Термин огибающая происходит от описания графика функции цены как «верхней оболочки» графиков параметризованного семейства функций. ${ Displaystyle влево {е влево (х, cdot right) вправо } _ {х в X}}$ которые оптимизированы.

Заявление

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

${ Displaystyle макс _ {х} е (х, альфа)}$ при условии ${ Displaystyle g_ {j} (х, альфа) geq 0, j = 1,2, ldots, m}$ и ${ Displaystyle х geq 0}$.

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

${ Displaystyle { mathcal {L}} (х, лямбда, альфа) = е (х, альфа) + лямбда CDOT г (х, альфа)}$

куда ${ displaystyle lambda in mathbb {R} ^ {m}}$ являются Множители Лагранжа. Теперь позвольте ${ Displaystyle х ^ { ast} ( альфа)}$ и ${ Displaystyle лямбда ^ { аст} ( альфа)}$ вместе быть решением, которое максимизирует целевую функцию ж с учетом ограничений (и, следовательно, седловые точки лагранжиана),

${ Displaystyle { mathcal {L}} ^ { ast} ( альфа) эквив е (х ^ { аст} ( альфа), альфа) + лямбда ^ { аст} ( альфа) cdot g (x ^ { ast} ( alpha), alpha),}$

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

${ Displaystyle V ( альфа) эквив f (х ^ { ast} ( альфа), альфа).}$

Тогда справедлива следующая теорема.^[3][4]

Теорема: Предположить, что ${ displaystyle V}$ и ${ Displaystyle { mathcal {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), альфа)} { partial alpha _ {k}}}, k = 1,2, ldots, l}$

куда ${ Displaystyle partial { mathcal {L}} / partial alpha _ {k} = partial f / partial alpha _ {k} + lambda cdot partial g / partial alpha _ {k }}$.

Для произвольных множеств выбора

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

${ Displaystyle V (T) = sup _ {x in X} f (x, t)}$

(1)

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

(2)

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

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

(3)

куда ${ displaystyle f_ {t}}$ обозначает частную производную от ${ displaystyle f}$ относительно ${ displaystyle t}$. А именно, производная функции цены по параметру равна частной производной целевой функции по ${ displaystyle t}$ удерживая максимайзер на оптимальном уровне.

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

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

Теорема 1: Позволять ${ Displaystyle т в влево (0,1 вправо)}$ и ${ Displaystyle х в Икс ^ { аст} влево (т вправо)}$. Если оба ${ Displaystyle В ^ { прайм} влево (т вправо)}$ и ${ Displaystyle е_ {т} влево (х, т вправо)}$ существует формула конверта (3) имеет место.

Доказательство: Уравнение (1) следует, что для ${ Displaystyle х в Икс ^ { аст} влево (т вправо)}$,

${ Displaystyle макс _ {s в влево [0,1 вправо]} влево [е влево (х, с вправо) -V влево (s вправо) вправо] = е влево ( x, t right) -V left (t right) = 0.}$

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

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

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

${ Displaystyle V (t) = V (0) + int _ {0} ^ {t} f_ {t} (x ^ { ast} (s), s) ds.}$

(4)

Доказательство: С помощью (1) (1) заметим, что для любого ${ Displaystyle т ^ { прайм}, т ^ { прайм прайм} в lbrack 0,1]}$ с ${ Displaystyle т ^ { прайм} <т ^ { прайм прайм}}$,

${ 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}$ абсолютно непрерывно. Следовательно, ${ displaystyle V}$ дифференцируема почти всюду, и используя (3) дает (4). Q.E.D.

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

Приложения

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

Из теоремы 1 следует Лемма Хотеллинга в любой точке дифференцируемости функции прибыли, и из теоремы 2 следует излишек производителя формула. Формально пусть ${ Displaystyle пи влево (п вправо)}$ обозначают функцию прибыли фиксирующей цены фирмы с производственным набором ${ Displaystyle X substeq mathbb {R} ^ {L}}$ против цен ${ displaystyle p in mathbb {R} ^ {L}}$, и разреши ${ Displaystyle х ^ { ast} влево (п вправо)}$ обозначают функцию предложения фирмы, т. е.

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

Позволять ${ displaystyle t = p_ {i}}$ (цена товара ${ displaystyle i}$) и зафиксировать цены на остальные товары на ${ displaystyle p _ {- i} in mathbb {R} ^ {L-1}}$. Применяя теорему 1 к ${ Displaystyle е (х, т) = tx_ {я} + р _ {- я} cdot х _ {- я}}$ дает ${ displaystyle { frac { partial pi (p)} { partial p_ {i}}} = x_ {i} ^ { ast} (p)}$ (оптимальные поставки фирмой товаров ${ displaystyle i}$). Применяя теорему 2 (предположения которой проверяются при ${ displaystyle p_ {i}}$ ограничен ограниченным интервалом) дает

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

то есть излишек производителя ${ Displaystyle пи (т, п _ {- я}) - пи (0, п _ {- я})}$ может быть получен путем интегрирования по кривой предложения фирмы навсегда ${ displaystyle i}$.

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

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

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

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

(Это уравнение можно интерпретировать как формулу излишка производителя для фирмы, чья производственная технология пересчитывает ${ displaystyle z}$ в вероятность ${ displaystyle y}$ выигрыш объекта определяется аукционом и перепродает объект по фиксированной цене ${ displaystyle t}$). Это условие, в свою очередь, приводит к знаменитому исследованию Майерсона (1981). теорема об эквивалентности доходов: ожидаемый доход, полученный на аукционе, на котором участники торгов имеют независимые частные значения, полностью определяется вероятностями участников торгов. ${ Displaystyle у ^ { аст} влево (т вправо)}$ получения объекта для всех типов ${ displaystyle t}$ а также по ожидаемым выплатам ${ displaystyle V ({ underline {t}})}$ наименьшего типа участников торгов. Наконец, это условие - ключевой шаг в оптимальных аукционах Майерсона (1981).^[6]

О других приложениях теоремы о оболочке к проектированию механизмов см. Mirrlees (1971),^[7] Холмстрем (1979),^[8] Лаффонт и Маскин (1980),^[9] Райли и Самуэльсон (1981),^[10] Фуденберг и Тироль (1991),^[11] и Уильямс (1999).^[12] Хотя эти авторы вывели и использовали теорему о конверте, ограничивая внимание (кусочно) непрерывно дифференцируемыми правилами выбора или даже более узкими классами, иногда может быть оптимальным реализовать правило выбора, которое не является кусочно непрерывно дифференцируемым. (Одним из примеров является класс торговых задач с линейной полезностью, описанный в главе 6.5 Майерсона (1991).^[13]Отметим, что интегральное условие (3) все еще выполняется в этой ситуации и влечет такие важные результаты, как лемма Холмстрома (Holmstrom, 1979),^[8] Лемма Майерсона (Myerson, 1981),^[6] теорема об эквивалентности доходов (для аукционов), теорема Грина – Лаффонта – Холмстрома (Green and Laffont, 1979; Holmstrom, 1979),^[14][8] теорема Майерсона – Саттертуэйта о неэффективности (Myerson and Satterthwaite, 1983),^[15] теоремы невозможности Jehiel – Moldovanu (Jehiel and Moldovanu, 2001),^[16] теорема Макафи-Макмиллана о слабых картелях (McAfee and McMillan, 1992),^[17] и теорема Мартингала Вебера (Weber, 1983),^[18] и т. д. Подробности этих приложений представлены в главе 3 Milgrom (2004),^[19] который предлагает элегантную и объединяющую основу для анализа конструкции аукционов и механизмов, в основном основанную на теореме о конверте и других известных методах и концепциях теории спроса.

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

Для многомерного пространства параметров ${ Displaystyle Т Substeq mathbb {R} ^ {K}}$, Теорема 1 может быть применена к частным производным и производным по направлениям функции цены. Если и целевая функция ${ displaystyle f}$ и функция цены ${ displaystyle V}$ (полностью) дифференцируемы в ${ displaystyle t}$Из теоремы 1 следует формула огибающей для их градиентов: ${ Displaystyle набла В влево (т вправо) = набла _ {т} е влево (х, т вправо)}$ для каждого ${ Displaystyle х в Икс ^ { аст} влево (т вправо)}$. Хотя обеспечить полную дифференцируемость функции цены может быть нелегко, теорема 2 может применяться на любом гладком пути, соединяющем два значения параметра. ${ displaystyle t_ {0}}$ и ${ displaystyle t}$. А именно, предположим, что функции ${ Displaystyle е (х, cdot)}$ дифференцируемы для всех ${ displaystyle x in X}$ с ${ Displaystyle | набла _ {т} е (х, т) | Leq B}$ для всех ${ displaystyle x in X,}$ ${ displaystyle t in T}$. Плавный путь от ${ displaystyle t_ {0}}$ к ${ displaystyle t}$ описывается дифференцируемым отображением ${ Displaystyle гамма: влево [0,1 вправо] rightarrow T}$ с ограниченной производной такой, что ${ Displaystyle гамма влево (0 вправо) = т_ {0}}$ и ${ Displaystyle гамма влево (1 вправо) = т}$. Из теоремы 2 следует, что для любого такого гладкого пути изменение функции цены может быть выражено как интеграл по путям частичного градиента ${ Displaystyle набла _ {т} е (х ^ { аст} (т), т)}$ целевой функции по пути:

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

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

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

Это «условие интегрируемости» играет важную роль в проектировании механизмов с многомерными типами, ограничивая, какие правила выбора ${ displaystyle x ^ { ast}}$ может поддерживаться меню, вызванным механизмами ${ displaystyle X substeq { bar {X}}}$. Применительно к теории производителей с ${ Displaystyle х в Икс substeq mathbb {R} ^ {L}}$ производственный вектор фирмы и ${ Displaystyle т ин mathbb {R} ^ {L}}$ вектор цен, ${ Displaystyle е влево (х, т вправо) = т CDOT х}$, а условие интегрируемости говорит, что любая рационализируемая функция предложения ${ displaystyle x ^ { ast}}$ должен удовлетворить

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

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

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

Предположим теперь, что допустимое множество ${ Displaystyle Х влево (т вправо)}$ зависит от параметра, т.е.

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

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

куда ${ Displaystyle X влево (т вправо) = влево {х в X: г влево (х, т вправо) GEQ 0 вправо }}$ для некоторых ${ displaystyle g: X times left [0,1 right] rightarrow mathbb {R} ^ {K}.}$

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

${ Displaystyle V (T) = V (0) + int _ {0} ^ {t} L_ {t} (x ^ { ast} (s), lambda ^ { ast} left (s справа), s) ds.}$

Для особого случая, когда ${ Displaystyle е влево (х, т вправо)}$ не зависит от ${ displaystyle t}$, ${ displaystyle K = 1}$, и ${ Displaystyle г влево (х, т вправо) = час влево (х вправо) + т}$, из формулы следует, что ${ displaystyle V ^ { prime} (t) = L_ {t} (x ^ { ast} (t), lambda ^ { ast} left (t right), t) = lambda ^ { ast} left (t right)}$ для п.в. ${ displaystyle t}$. То есть множитель Лагранжа ${ Displaystyle лямбда ^ { аст} влево (т вправо)}$ на ограничении его "скрытая цена"в программе оптимизации.^{[21][страница нужна]}

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

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

Смотрите также

Рекомендации