Теорема Неймана — Моргенштерна о минимаксе

В теории игр, теорема о минимаксе описывает условия, при выполнении которых для функции $f:Z\times W\to \mathbb {R}$ верно, что $\sup _{x\in Z}\inf _{y\in W}f=\inf _{y\in W}\sup _{x\in Z}f.$ Первой теоремой такого рода стала теорема фон Неймана, доказанная в 1928 году. Именно с её доказательства началось развитие теории игр. Впоследствии её неоднократно обобщали и переформулировали^[1]^[2].

Игры с нулевой суммой

Эту теорему впервые доказал в 1928 году Джон фон Нейман^[3] ^[4].

Формально, теорема фон Неймана утверждает, что

Пусть $X\subset \mathbb {R} ^{n}$ и $Y\subset \mathbb {R} ^{m}$ ― компактные выпуклые множества. Если функция $f:X\times Y\rightarrow \mathbb {R}$ непрерывна, выпукла в $X$ , но вогнута в $Y$ , т.е.

f(\cdot ,y):X\rightarrow \mathbb {R}

выпукла при любом заданном

y

, но

f(x,\cdot ):Y\rightarrow \mathbb {R}

вогнута при любом заданном

x

то

\max _{x\in X}\min _{y\in Y}f(x,y)=\min _{y\in Y}\max _{x\in X}f(x,y).

Примеры

Если $f(x,y)=x^{T}Ay$ для конечной матрицы $A\in \mathbb {R} ^{n\times m}$ , то $\max _{x\in X}\min _{y\in Y}x^{T}Ay=\min _{y\in Y}\max _{x\in X}x^{T}Ay.$

См. также

Теорема Сиона о минимаксе^[англ.]
Теорема Партасарати^[англ.], являющаяся обобщением теоремы о минимаксе
Двойственная задача линейного программирования, облегчающая поиск оптимальных стратегий в играх с нулевой суммой
Принцип Яо

Примечания

↑ Minimax and Applications. — Boston, MA : Springer US, 1995. — ISBN 9781461335573.
↑ Brandt, Felix; Brill, Markus; Suksompong, Warut (2016). "An ordinal minimax theorem". Games and Economic Behavior. 95: 107—112. arXiv:1412.4198. doi:10.1016/j.geb.2015.12.010.
↑ Von Neumann, J. (1928). "Zur Theorie der Gesellschaftsspiele". Math. Ann. 100: 295—320. doi:10.1007/BF01448847.
↑ John L Casti. Five golden rules: great theories of 20th-century mathematics – and why they matter. — New York : Wiley-Interscience, 1996. — P. 19. — ISBN 978-0-471-00261-1.

Похожие исследовательские статьи

Теоре́мой Ха́на — Ба́наха называют несколько связанных между собой классических результатов функционального анализа, в частности

Теорему о продолжении линейного функционала с сохранением мажоранты;
Теорему о разделении выпуклых множеств;
Теорему о непрерывном или положительном продолжении линейного функционала.

Метрика Хаусдорфа есть естественная метрика, определённая на множестве всех непустых компактных подмножеств метрического пространства. Таким образом, она превращает множество всех непустых компактных подмножеств метрического пространства в метрическое пространство.

<span class="mw-page-title-main">Интеграл Римана</span> простейшее определение интеграла

Интегра́л Ри́мана — наиболее широко используемый вид определённого интеграла. Очень часто под термином «определённый интеграл» понимается именно интеграл Римана, и он изучается самым первым из всех определённых интегралов во всех курсах математического анализа. Введён Бернхардом Риманом в 1854 году, и является одной из первых формализаций понятия интеграла.

Точная верхняя граница и точная нижняя граница — обобщение понятий максимума и минимума множества соответственно.

Решётка — частично упорядоченное множество, в котором каждое двухэлементное подмножество имеет как точную верхнюю (sup), так и точную нижнюю (inf) грани. Отсюда вытекает существование этих граней для любых непустых конечных подмножеств.

Теоре́ма Вейерштра́сса — теорема математического анализа и общей топологии, которая гласит, что функция, непрерывная на компакте, ограничена на нём и достигает своих точных верхней и нижней граней.

В математическом анализе вариацией функции называется числовая характеристика функции одного действительного переменного, связанная с её дифференциальными свойствами. Для функции из отрезка на вещественной прямой в $\text{[math]}$ является обобщением понятия длины кривой, задаваемой в $\text{[math]}$ этой функцией.

Ле́мма Фату́ — техническое утверждение, используемое при доказательстве различных теорем в функциональном анализе и теории вероятностей. Оно даёт одно из условий, при которых предел почти всюду сходящейся функциональной последовательности будет суммируемым.

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

Теоре́ма Тоне́лли — Фуби́ни в математическом анализе, теории вероятностей и смежных дисциплинах сводит вычисление двойного интеграла к повторным.

Теорема Гливе́нко — Канте́лли в математической статистике уточняет результат о сходимости выборочной функции распределения к её теоретическому аналогу.

Марковский момент времени — это случайная величина, не зависящая от будущего рассматриваемого случайного процесса.

Квазивыпуклая функция — обобщение понятия выпуклой функции, нашедшее широкое применение в нелинейной оптимизации, в частности, при применении оптимизации к вопросам экономики.

Сетевое исчисление — совокупность математических результатов, которые позволяют исследовать граничные значения характеристик функционирования таких сложных технических систем, как сети связи, цифровые электрические цепи, конкурирующие программы. Сетевое исчисление даёт теоретическую основу для анализа гарантированной производительности телекоммуникационных пакетных сетей. Потоки трафика, проходящие через сеть, имеют различные ограничения, обусловленные такими свойствами и механизмами, используемыми в сети, как пропускная способность канала связи, формирователи трафика, управление трафиком и доступом, фоновый трафик. Эти ограничения могут быть выражены и проанализированы с использованием методов теории сетевого исчисления. Сетевое исчисление основано на использовании функций (кривых) входящего и исходящего трафика, а также функций обслуживания в сетевых узлах. Эти функции могут быть получены с использованием свёртки в min-плюс алгебре. Сетевое исчисление использует альтернативную идемпотентную алгебру, позволяющую преобразовать сложные нелинейные сетевые системы в линейные, легко поддающиеся аналитическому исследованию.

В математике теория момента остановки или марковский момент времени связана с проблемой выбора времени, чтобы принять определённое действие, для того чтобы максимизировать ожидаемое вознаграждение или минимизировать ожидаемые затраты. Проблема момента остановки может быть найдена в области статистики, экономики и финансовой математики. Самым ярким примером, относящимся к моменту остановки, является Задача о разборчивой невесте. Проблема момента остановки часто может быть указана в форме уравнения Беллмана и поэтому часто решается с помощью динамического программирования.

Двойственность, или принцип двойственности, — принцип, по которому задачи оптимизации можно рассматривать с двух точек зрения, как прямую задачу или двойственную задачу. Решение двойственной задачи даёт нижнюю границу прямой задачи. Однако, в общем случае, значения целевых функций оптимальных решений прямой и двойственной задач не обязательно совпадают. Разница этих значений, если она наблюдается, называется разрывом двойственности. Для задач выпуклого программирования разрыв двойственности равен нулю при выполнении условий регулярности ограничений.

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

Теорема двойственности Фенхеля — это результат в теории выпуклых функций, носящий имя немецкого математика Вернера Фенхеля.

<span class="mw-page-title-main">Выпуклый анализ</span>

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

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

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.