Теорема о минимаксе

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

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

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

Минимаксный теорема была впервые доказана и опубликована в 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).}$

Примеры [ править ]

Если для конечной матрицы имеем:${\displaystyle f(x,y)=x^{T}Ay}$${\displaystyle A\in \mathbb {R} ^{n\times m}}$

${\displaystyle \max _{x\in X}\min _{y\in Y}x^{T}Ay=\min _{y\in Y}\max _{x\in X}x^{T}Ay.}$

См. Также [ править ]

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

Ссылки [ править ]