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

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

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

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

x

, но вогнута по

y

Эту теорему впервые доказал в 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.$