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

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

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

Игры с нулевой суммойПравить

 

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

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

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

Пусть $X\subset <!--\; \subset \; -->{\mathbb{R}}^n$$X\subset \mathbb {R} ^{n}$  и $Y\subset <!--\; \subset \; -->{\mathbb{R}}^m$$Y\subset \mathbb {R} ^{m}$  ― компактные выпуклые множества. Если функция $f:X\times <!--\; \times \; -->Y\to <!--\; \to \; -->\mathbb{R}$$f:X\times Y\rightarrow \mathbb {R}$  непрерывна, выпукла в $X$$X$ , но вогнута в $Y$$Y$ , т.е. $f(\cdot <!--\; \cdot \; -->,y):X\to <!--\; \to \; -->\mathbb{R}$$f(\cdot ,y):X\rightarrow \mathbb {R}$  выпукла при любом заданном $y$$y$ , но $f(x,\cdot <!--\; \cdot \; -->):Y\to <!--\; \to \; -->\mathbb{R}$$f(x,\cdot ):Y\rightarrow \mathbb {R}$  вогнута при любом заданном $x$$x$ , то $\underset{x\in <!--\; \in \; -->X}{max}\underset{y\in <!--\; \in \; -->Y}{min}f(x,y)=\underset{y\in <!--\; \in \; -->Y}{min}\underset{x\in <!--\; \in \; -->X}{max}f(x,y).$$\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$$f(x,y)=x^{T}Ay$  для конечной матрицы $A\in <!--\; \in \; -->{\mathbb{R}}^{n\times <!--\; \times \; -->m}$$A\in \mathbb {R} ^{n\times m}$ , то $\underset{x\in <!--\; \in \; -->X}{max}\underset{y\in <!--\; \in \; -->Y}{min}{x}^{T}Ay=\underset{y\in <!--\; \in \; -->Y}{min}\underset{x\in <!--\; \in \; -->X}{max}{x}^{T}Ay.$$\max _{x\in X}\min _{y\in Y}x^{T}Ay=\min _{y\in Y}\max _{x\in X}x^{T}Ay.$ 

См. такжеПравить

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