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

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

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

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

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

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

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

Пусть ${\displaystyle X\subset \mathbb {R} ^{n}}$ и ${\displaystyle Y\subset \mathbb {R} ^{m}}$ ― компактные выпуклые множества. Если функция ${\displaystyle f:X\times Y\rightarrow \mathbb {R} }$ непрерывна, выпукла в ${\displaystyle X}$, но вогнута в ${\displaystyle Y}$, т.е. ${\displaystyle f(\cdot ,y):X\rightarrow \mathbb {R} }$ выпукла при любом заданном ${\displaystyle y}$, но ${\displaystyle f(x,\cdot ):Y\rightarrow \mathbb {R} }$ вогнута при любом заданном ${\displaystyle x}$, то ${\displaystyle \max _{x\in X}\min _{y\in Y}f(x,y)=\min _{y\in Y}\max _{x\in X}f(x,y).}$

Примеры

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

См. также

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