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

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

Термин «конверт» происходит от описания графика функции ценности как «верхнего конверта» графиков параметризованного семейства функций. $\left\{f\left(x,\cdot \right)\right\}_{x\in X}$ которые оптимизированы.

Заявление

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

$\max _{x}f(x,\alpha )$ при условии $g_{j}(x,\alpha )\geq 0,j=1,2,\ldots ,m$ и $x\geq 0$.

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

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

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

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

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

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

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

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

${\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$

где $\partial {\mathcal {L}}/\partial \alpha _{k}=\partial f/\partial \alpha _{k}+\lambda \cdot \partial g/\partial \alpha _{k}$.

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

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

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

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

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

$V^{\prime }\left(t\right)=f_{t}\left(x,t\right){\text{ for each }}x\in X^{\ast }\left(t\right),$ ( 3 )

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

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

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

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

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

$\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$, а условием первого порядка для этой максимизации является в точности уравнение ( 3 ). КЭД

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

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

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

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

$|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.$

Это подразумевает, что $V$ абсолютно непрерывен. Поэтому, $V$ дифференцируемо почти всюду, и использование ( 3 ) дает ( 4 ). КЭД

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

Приложения

к

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

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

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

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

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

к конструкции механизмов и

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

• Отличная теория
• Теорема Данскина
• Лемма Хотеллинга
• Принцип Ле Шателье
• Личность Роя
• Функция значения