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

В математике и экономике теорема о конверте является основным результатом о свойствах дифференцируемости функции цены параметризованной задачи оптимизации. ^[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}(x,\alpha )\geq 0,j=1,2,\ldots ,m}$${\displaystyle x\geq 0}$

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

${\displaystyle {\mathcal {L}}(x,\lambda ,\alpha )=f(x,\alpha )+\lambda \cdot g(x,\alpha )}$

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

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

и определим функцию ценности

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

Тогда справедлива следующая теорема. ^{[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 ),\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 t\in \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{ for each }}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: Пусть и . Если оба и существуют, формула конверта ( 3 ) верна.${\displaystyle t\in \left(0,1\right)}$${\displaystyle x\in X^{\ast }\left(t\right)}$${\displaystyle V^{\prime }\left(t\right)}$${\displaystyle f_{t}\left(x,t\right)}$

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

${\displaystyle \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.}$

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

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

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

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

( 4 )

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

${\displaystyle |V(t^{\prime \prime })-V(t^{\prime })|\leq \sup _{x\in X}|f(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.}$

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

Этот результат развеивает распространенное заблуждение, что хорошее поведение функции значения требует соответственно хорошего поведения максимизатора. Теорема 2 гарантирует абсолютную непрерывность функции цены, даже если максимайзер может быть разрывным. Аналогичным образом, из теоремы 3 Милгрома и Сигала (2002) следует, что функция цены должна быть дифференцируемой в точке и, следовательно, удовлетворять формуле оболочки ( 3 ), когда семейство равно-дифференцируемо в точке и однозначно и непрерывно в точке , даже если максимайзер не дифференцируем в (например, если описывается набором ограничений неравенства, а набор ограничений привязки изменяется в ). ^[5]${\displaystyle t=t_{0}}$${\displaystyle \left\{f\left(x,\cdot \right)\right\}_{x\in 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}}$

Приложения [ править ]

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

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

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

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

${\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})}$${\displaystyle i}$

Приложения к проектированию механизмов и теории аукционов [ править ]

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

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

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

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

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

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

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

${\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\subseteq {\bar {X}}}$${\displaystyle x\in X\subseteq \mathbb {R} ^{L}}$${\displaystyle t\in \mathbb {R} ^{L}}$${\displaystyle f\left(x,t\right)=t\cdot x}$${\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 X\left(t\right)}$

${\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\left(t\right)=\left\{x\in X:g\left(x,t\right)\geq 0\right\}}$${\displaystyle g:X\times \left[0,1\right]\rightarrow \mathbb {R} ^{K}.}$

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

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

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

Другие приложения [ править ]

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

См. Также [ править ]

Ссылки [ править ]