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

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

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

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

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

Формально, теорема фон Неймана утверждает, что Шаблон:Рамка Пусть $X\subset {ℝ}^n$ и $Y\subset {ℝ}^m$ ― компактные выпуклые множества. Если функция $f:X\times Y\to ℝ$ непрерывна, выпукла в $X$, но вогнута в $Y$, т.е.

$f(\cdot ,y):X\to ℝ$ выпукла при любом заданном $y$, но

$f(x,\cdot ):Y\to ℝ$ вогнута при любом заданном $x$,

то

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

Примеры

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

См. также

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