Супермодульная функция

В математике функция

$f\colon \mathbb {R} ^{k}\to \mathbb {R}$

является супермодулярным, если

$f(x\uparrow y)+f(x\downarrow y)\geq f(x)+f(y)$

для всех $x$, $y\in \mathbb {R} ^{k}$, где $x\uparrow y$ обозначает покомпонентный максимум и $x\downarrow y$ покомпонентный минимум $x$ и $y$.

Если −f супермодулярна, то f называется субмодулярной , а если неравенство заменить равенством, функция будет модулярной .

Если f дважды непрерывно дифференцируема, то супермодулярность эквивалентна условию

${\frac {\partial ^{2}f}{\partial z_{i}\,\partial z_{j}}}\geq 0{\mbox{ for all }}i\neq j.$

Супермодульность в экономике и теории игр

Концепция супермодульности используется в социальных науках для анализа того, как решение одного агента влияет на стимулы других.

Рассмотрим симметричную игру с гладкой функцией выигрыша. $\,f$ определяется действиями $\,z_{i}$ двух и более игроков $i\in {1,2,\dots ,N}$. Предположим, что пространство действий непрерывно; для простоты предположим, что каждое действие выбрано из интервала: $z_{i}\in [a,b]$. В этом контексте супермодульность $\,f$ подразумевает, что увеличение количества игроков $\,i$выбор $\,z_{i}$ увеличивает предельный выигрыш $df/dz_{j}$ действия $\,z_{j}$ для всех остальных игроков $\,j$. То есть, если какой-либо игрок $\,i$ выбирает более высокий $\,z_{i}$, все остальные игроки $\,j$ иметь стимул повышать свой выбор $\,z_{j}$ слишком. Следуя терминологии Бюлова, Геанакоплоса и Клемперера (1985), экономисты называют эту ситуацию стратегической взаимодополняемостью , поскольку стратегии игроков дополняют друг друга. Это основное свойство, лежащее в основе примеров множественного равновесия в координационных играх .

Противоположный случай супермодульности $\,f$, называемая субмодульностью, соответствует ситуации стратегической взаимозаменяемости . Увеличение $\,z_{i}$ снижает предельный выигрыш по сравнению с выбором всех остальных игроков $\,z_{j}$, поэтому стратегии являются заменителями. То есть, если $\,i$ выбирает более высокий $\,z_{i}$, у других игроков есть стимул выбрать более низкую цену. $\,z_{j}$.

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

Супермодульная функция полезности часто связана с дополняющими друг друга товарами . Однако эта точка зрения оспаривается.

Субмодулярные функции подмножеств

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

Пусть S — конечное множество. Функция $f\colon 2^{S}\to \mathbb {R}$ является субмодулярным, если для любого $A\subset B\subset S$ и $x\in S\setminus B$, $f(A\cup \{x\})-f(A)\geq f(B\cup \{x\})-f(B)$. Для супермодульности неравенство меняется на противоположное.

Определение субмодулярности эквивалентно можно сформулировать как

$f(A)+f(B)\geq f(A\cap B)+f(A\cup B)$

для всех подмножеств A и B из S .

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

См. также

• Псевдобулева функция
• Теорема Топкиса
• Субмодульная функция множества
• Супердобавка
• Функции полезности для неделимых благ.