Теорема о минимаксе - Minimax theorem

Не путать с Теорема мин-макс.

В математической области теория игры, а теорема о минимаксе это теорема, дающая условия, гарантирующие, что max – min неравенство тоже равенство. Первая теорема в этом смысле такова: фон Нейман теорема о минимаксе 1928 года, которая считалась отправной точкой теория игры. С тех пор в литературе появилось несколько обобщений и альтернативных версий исходной теоремы фон Неймана.^[1][2]

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

Функция ж(Икс,у)=Икс²-у² вогнуто-выпуклый.

Теорема о минимаксе была впервые доказана и опубликована в 1928 г. Джон фон Нейман,^[3] кто цитируется как говорящий "Насколько я понимаю, теории игр не могло бы быть ... без этой теоремы ... Я думал, что нечего публиковать, пока не будет доказана теорема о минимаксе.".^[4]

Формально минимаксная теорема фон Неймана гласит:

Позволять ${\displaystyle X\subset \mathbb {R} ^{n}}$ и ${\displaystyle Y\subset \mathbb {R} ^{m}}$ быть компактный выпуклый наборы. Если ${\displaystyle f:X\times Y\rightarrow \mathbb {R} }$ - непрерывная функция, вогнуто-выпуклая, т. е.

${\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).}$

Смотрите также

• Минимаксная теорема Сиона
• Теорема Партасарати
• Двойная линейная программа может использоваться для доказательства теоремы о минимаксе для игр с нулевой суммой.

использованная литература

1. Ду, Дин-Чжу; Пардалос, Панос М., ред. (1995). Минимакс и приложения. Бостон, Массачусетс: Springer США. ISBN  9781461335573.
2. Брандт, Феликс; Брилл, Маркус; Суксомпонг, Варут (2016). «Порядковая минимаксная теорема». Игры и экономическое поведение. 95: 107–112. arXiv:1412.4198. Дои:10.1016 / j.geb.2015.12.010.
3. Фон Нейман, Дж. (1928). "Zur Theorie der Gesellschaftsspiele". Математика. Анна. 100: 295–320. Дои:10.1007 / BF01448847.
4. Джон Л. Касти (1996). Пять золотых правил: великие теории математики ХХ века - и почему они важны. Нью-Йорк: Wiley-Interscience. п.19. ISBN  978-0-471-00261-1.