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

В теории игр, теорема о минимаксе описывает условия, при выполнении которых для функции f : Z × W → R {displaystyle f:Z imes W o mathbb {R} } верно, что sup x ∈ Z inf y ∈ W f = inf y ∈ Z sup x ∈ W f . {displaystyle sup _{xin Z}inf _{yin W}f=inf _{yin Z}sup _{xin W}f.} Первой теоремой такого рода стала теорема фон Неймана, доказанная в 1928 году. Именно с её доказательства началось развитие теории игр. Впоследствии её неоднократно обобщали и переформулировали.

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

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

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

Примеры

Если f ( x , y ) = x T A y {displaystyle f(x,y)=x^{T}Ay} для конечной матрицы A ∈ R n × m {displaystyle Ain mathbb {R} ^{n imes m}} , то max x ∈ X min y ∈ Y x T A y = min y ∈ Y max x ∈ X x T A y . {displaystyle max _{xin X}min _{yin Y}x^{T}Ay=min _{yin Y}max _{xin X}x^{T}Ay.}