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

{{Не путать|Теорема Куранта — Фишера|Теоремой Куранта — Фишера о минимаксе}}
В [[Теория игр|теории игр]], '''теорема о минимаксе''' описывает условия, при выполнении которых для функции <math>f:Z\times W\to \mathbb{R}</math> верно, что <math>\sup_{x\in Z}\inf_{y\in W} f = \inf_{y\in W} \sup_{x\in Z} f.</math> Первой теоремой такого рода стала теорема [[Джон фон Нейман|фон Неймана]], доказанная в 1928 году. Именно с её доказательства началось развитие теории игр. Впоследствии её неоднократно обобщали и переформулировали<ref>{{cite book|editor1-last=Du|editor1-first=Ding-Zhu|editor2-last=Pardalos|editor2-first=Panos M.|title=Minimax and Applications|date=1995|publisher=Springer US|location=Boston, MA|isbn=9781461335573}}</ref><ref>{{Cite journal|last1=Brandt|first1=Felix|last2=Brill|first2=Markus|last3=Suksompong|first3=Warut|year=2016|title=An ordinal minimax theorem|journal=Games and Economic Behavior|volume=95|pages=107–112|doi=10.1016/j.geb.2015.12.010|arxiv=1412.4198}}</ref>.

== Игры с нулевой суммой ==
[[File:Saddle point.svg|thumb|Функция ''f''(''x'',''y'')=''x''<sup>2</sup>-''y''<sup>2</sup> выпукла по <math>x</math>, но вогнута по <math>y</math>]]
Эту теорему впервые доказал в 1928 году [[Джон фон Нейман]]<ref>{{cite journal |last=Von Neumann |first=J. |title=Zur Theorie der Gesellschaftsspiele |url=https://archive.org/details/sim_mathematische-annalen_1928_100/page/295 |journal=[[Mathematische Annalen|Math. Ann.]] |volume=100 |year=1928 |pages=295–320 |doi=10.1007/BF01448847 }}</ref> <!-- {{перевод|и заявил, что "''Насколько я понимаю, теории игр не могло бы быть без этой теоремы … Ни один результат не стоил публикации без доказательства этой теоремы.|who is quoted as saying "''As far as I can see, there could be no theory of games … without that theorem … I thought there was nothing worth publishing until the Minimax Theorem was proved''"}}--><ref name=Casti>{{cite book
|author=John L Casti
|title=Five golden rules: great theories of 20th-century mathematics – and why they matter
|url=https://archive.org/details/fivegoldenrulesg00cast/page/19
|publisher=Wiley-Interscience
|location=New York
|year=1996
|page=[https://archive.org/details/fivegoldenrulesg00cast/page/19 19]
|isbn=978-0-471-00261-1
|url-access=registration
}}</ref>.

Формально, теорема фон Неймана утверждает, что 
{{рамка}}
Пусть <math>X \subset \mathbb{R}^n</math> и <math>Y \subset \mathbb{R}^m</math> ― [[компактное множество|компактные]] [[Выпуклое множество|выпуклые]] множества. Если функция <math>f: X \times Y \rightarrow \mathbb{R}</math> непрерывна, выпукла в <math>X</math>, но вогнута в <math>Y</math>, т.е.

: <math>f(\cdot,y):X\rightarrow\mathbb{R}</math> выпукла при любом заданном <math>y</math>, но
: <math>f(x,\cdot):Y\rightarrow\mathbb{R}</math> вогнута при любом заданном <math>x</math>,

то

: <math>\max_{x\in X}\min_{y\in Y} f(x,y)=\min_{y\in Y}\max_{x\in X}f(x,y).</math>
{{конец рамки}}
=== Примеры ===
Если <math>f(x,y) = x^T A y</math> для конечной матрицы <math>A \in \mathbb{R}^{n \times m}</math>, то <math>\max_{x \in X}\min_{y \in Y} x^T A y =\min_{y \in Y}\max_{x \in X} x^T A y. </math>

== См. также ==
* {{Не переведено 5|Теорема Сиона о минимаксе|Теорема Сиона о минимаксе|en|Sion's minimax theorem}}
* {{нп5|Теорема Партасарати|Теорема Партасарати|en|Parthasarathy's theorem}}, являющаяся обобщением теоремы о минимаксе
* [[Двойственная задача линейного программирования]], облегчающая поиск оптимальных стратегий в играх с нулевой суммой
* [[Принцип Яо]]

== Примечания==
{{примечания}}
{{math-stub}}
[[Категория:Теория игр]]
[[Категория:Теория оптимизации]]
[[Категория:Математические теоремы]]