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

Не следует путать с Теоремой Куранта — Фишера о минимаксе.

В теории игр, теорема о минимаксе описывает условия, при выполнении которых для функции $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 году. Именно с её доказательства началось развитие теории игр. Впоследствии её неоднократно обобщали и переформулировали.

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

Функция f(x,y)=x²-y² выпукла по $x$, но вогнута по $y$

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

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

Пусть $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.$

См. также

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