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

Envelope theorem

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

Термин огибающая происходит от описания графика функции цены как «верхней оболочки» графиков параметризованного семейства функций. которые оптимизированы.

Заявление

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

при условии и .

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

куда являются Множители Лагранжа. Теперь позвольте и вместе быть решением, которое максимизирует целевую функцию ж с учетом ограничений (и, следовательно, седловые точки лагранжиана),

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

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

Теорема: Предположить, что и непрерывно дифференцируемы. потом

куда .

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

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

 

 

 

 

(1)

 

 

 

 

(2)

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

 

 

 

 

(3)

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

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

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

Теорема 1: Позволять и . Если оба и существует формула конверта (3) имеет место.

Доказательство: Уравнение (1) следует, что для ,

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

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

Теорема 2: Предположим, что абсолютно непрерывен для всех . Предположим также, что существует интегрируемая функция такой, что для всех и почти все . потом абсолютно непрерывно. Предположим, кроме того, что дифференцируема для всех , и это почти везде на . Тогда для любого выбора ,

 

 

 

 

(4)

Доказательство: С помощью (1) (1) заметим, что для любого с ,

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

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

Приложения

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

Из теоремы 1 следует Лемма Хотеллинга в любой точке дифференцируемости функции прибыли, и из теоремы 2 следует излишек производителя формула. Формально пусть обозначают функцию прибыли фиксирующей цены фирмы с производственным набором против цен , и разреши обозначают функцию предложения фирмы, т. е.

Позволять (цена товара ) и зафиксировать цены на остальные товары на . Применяя теорему 1 к дает (оптимальные поставки фирмой товаров ). Применяя теорему 2 (предположения которой проверяются при ограничен ограниченным интервалом) дает

то есть излишек производителя может быть получен путем интегрирования по кривой предложения фирмы навсегда .

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

Рассмотрим агента, функция полезности которого по результатам зависит от его типа . Позволять представляют собой «меню» возможных результатов, которые агент может получить в механизме, отправляя различные сообщения. Равновесная полезность агента в механизме тогда задается формулой (1), а множество результатов равновесия механизма определяется выражением (2). Любой выбор - это правило выбора, реализуемое механизмом. Предположим, что функция полезности агента дифференцируема и абсолютно непрерывна в для всех , и это интегрируется на . Тогда из теоремы 2 следует, что равновесная полезность агента в любом механизме, реализующем данное правило выбора должно удовлетворять интегральному условию (4).

Интегральное условие (4) является ключевым шагом при анализе задач проектирования механизмов с непрерывными пространствами типов. В частности, в проведенном Майерсоном (Myerson, 1981) анализе аукционов по продаже отдельных позиций результат с точки зрения одного участника торгов можно описать как , куда вероятность получения объекта покупателем и является его ожидаемым платежом, а ожидаемая полезность участника торгов принимает форму . В этом случае, позволяя обозначают наименьший возможный тип участника торгов, интегральное условие (4) для равновесной ожидаемой полезности участника торгов принимает форму

(Это уравнение можно интерпретировать как формулу излишка производителя для фирмы, чья производственная технология пересчитывает в вероятность выигрыш объекта определяется аукционом и перепродает объект по фиксированной цене ). Это условие, в свою очередь, приводит к знаменитому исследованию Майерсона (1981). теорема об эквивалентности доходов: ожидаемый доход, полученный на аукционе, на котором участники торгов имеют независимые частные значения, полностью определяется вероятностями участников торгов. получения объекта для всех типов а также по ожидаемым выплатам наименьшего типа участников торгов. Наконец, это условие - ключевой шаг в оптимальных аукционах Майерсона (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] который предлагает элегантную и объединяющую основу для анализа конструкции аукционов и механизмов, в основном основанную на теореме о конверте и других известных методах и концепциях теории спроса.

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

Для многомерного пространства параметров , Теорема 1 может быть применена к частным производным и производным по направлениям функции цены. Если и целевая функция и функция цены (полностью) дифференцируемы в Из теоремы 1 следует формула огибающей для их градиентов: для каждого . Хотя обеспечить полную дифференцируемость функции цены может быть нелегко, теорема 2 может применяться на любом гладком пути, соединяющем два значения параметра. и . А именно, предположим, что функции дифференцируемы для всех с для всех . Плавный путь от к описывается дифференцируемым отображением с ограниченной производной такой, что и . Из теоремы 2 следует, что для любого такого гладкого пути изменение функции цены может быть выражено как интеграл по путям частичного градиента целевой функции по пути:

В частности, для , это устанавливает, что циклические интегралы по пути вдоль любого гладкого пути должно быть равно нулю:

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

Когда непрерывно дифференцируемо, это условие интегрируемости эквивалентно симметрии матрица замещения . (В теория потреблениято же рассуждение, примененное к задаче минимизации расходов, дает симметрию Слуцкая матрица.)

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

Предположим теперь, что допустимое множество зависит от параметра, т.е.

куда для некоторых

Предположим, что выпуклое множество, и вогнуты в , и существует такой, что для всех . При этих предположениях хорошо известно, что указанная выше программа оптимизации с ограничениями может быть представлена ​​как проблема перевала для лагранжиана , куда вектор Множители Лагранжа выбирается противником для минимизации лагранжиана.[20][страница нужна][21][страница нужна] Это позволяет применить теорему о конверте Милгрома и Сигала (2002, теорема 4) для задач перевала,[5] при дополнительных предположениях, что компакт в линейном нормированном пространстве, и непрерывны в , и и непрерывны в . В частности, позволяя обозначают седловую точку лагранжиана для значения параметра , из теоремы следует, что абсолютно непрерывен и удовлетворяет

Для особого случая, когда не зависит от , , и , из формулы следует, что для п.в. . То есть множитель Лагранжа на ограничении его "скрытая цена"в программе оптимизации.[21][страница нужна]

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

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

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

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

  1. ^ Граница, Ким С. (2019). «Разные заметки по теории оптимизации и связанным темам» (PDF). Конспект лекций. Калифорнийский технологический институт: 154.
  2. ^ Картер, Майкл (2001). Основы математической экономики. Кембридж: MIT Press. С. 603–609. ISBN 978-0-262-53192-4.
  3. ^ Африат, С. Н. (1971). «Теория максимумов и метод Лагранжа». Журнал SIAM по прикладной математике. 20 (3): 343–357. Дои:10.1137/0120037.
  4. ^ Такаяма, Акира (1985). Математическая экономика (Второе изд.). Нью-Йорк: Издательство Кембриджского университета. стр.137–138. ISBN 978-0-521-31498-5.
  5. ^ а б c d е Милгром, Пол; Илья Сегал (2002). «Теоремы о конверте для множеств произвольного выбора». Econometrica. 70 (2): 583–601. CiteSeerX 10.1.1.217.4736. Дои:10.1111/1468-0262.00296.
  6. ^ а б Майерсон, Роджер (1981). «Оптимальный дизайн аукциона». Математика исследования операций. 6: 58–73. Дои:10.1287 / moor.6.1.58. S2CID 12282691.
  7. ^ Миррлис, Джеймс (2002). «Исследование теории оптимального налогообложения». Обзор экономических исследований. 38 (2): 175–208. Дои:10.2307/2296779. JSTOR 2296779.
  8. ^ а б c Холмстром, Бенгт (1979). «Схемы Groves на ограниченных доменах». Econometrica. 47 (5): 1137–1144. Дои:10.2307/1911954. JSTOR 1911954. S2CID 55414969.
  9. ^ Лаффон, Жан-Жак; Эрик Маскин (1980). «Дифференцируемый подход к механизмам доминирующей стратегии». Econometrica. 48 (6): 1507–1520. Дои:10.2307/1912821. JSTOR 1912821.
  10. ^ Райли, Джон Дж .; Самуэльсон, Уильям С. (1981). «Оптимальные аукционы». Американский экономический обзор. 71 (3): 381–392. JSTOR 1802786.
  11. ^ Фуденберг, Дрю; Тироль, Жан (1991). Теория игры. Кембридж: MIT Press. ISBN 0-262-06141-4.
  12. ^ Уильямс, Стивен (1999). «Характеристика эффективного механизма, совместимого с байесовским стимулом». Экономическая теория. 14: 155–180. Дои:10.1007 / s001990050286. S2CID 154378924.
  13. ^ Майерсон, Роджер (1991). Теория игры. Кембридж: Издательство Гарвардского университета. ISBN 0-674-34115-5.
  14. ^ Green, J .; Лаффонт, Дж. Дж. (1979). Стимулы в принятии государственных решений. Амстердам: Северная Голландия. ISBN 0-444-85144-5.
  15. ^ Myerson, R .; М. Саттертуэйт (1983). «Эффективные механизмы двусторонней торговли» (PDF). Журнал экономической теории. 29 (2): 265–281. Дои:10.1016/0022-0531(83)90048-0.
  16. ^ Иехиэль, Филипп; Молдовану, Бенни (2001). «Эффективный дизайн с взаимозависимыми оценками». Econometrica. 69 (5): 1237–1259. CiteSeerX 10.1.1.23.7639. Дои:10.1111/1468-0262.00240.
  17. ^ Макафи, Р. Престон; Джон Макмиллан (1992). «Кольца торгов». Американский экономический обзор. 82 (3): 579–599. JSTOR 2117323.
  18. ^ Вебер, Роберт (1983). «Многообъектные аукционы» (PDF). В Engelbrecht-Wiggans, R .; Шубик, М .; Старк, Р. М. (ред.). Аукционы, торги и контракты: использование и теория. Нью-Йорк: Издательство Нью-Йоркского университета. С. 165–191. ISBN 0-8147-7827-5.
  19. ^ Милгром, Пол (2004). Применение теории аукционов на практике. Издательство Кембриджского университета. ISBN 9780521536721.
  20. ^ Люенбергер, Д. Г. (1969). Оптимизация методами векторного пространства. Нью-Йорк: Джон Вили и сыновья. ISBN 9780471181170.
  21. ^ а б Рокафеллар, Р. Т. (1970). Выпуклый анализ. Принстон: Издательство Принстонского университета. ISBN 0691015864.