(13:А*) Всегда
max min ф (х, у) rg min max ф (х, у).
х у ух
(13:В*) Мы имеем
max min ф (х, у) = min max ф (х, у)
х у ух
тогда и только тогда, когда существует седловая точка х0, Уо функции ф.
13.5. Доказательства основных фактов
13.5.1. Во-первых, определим для каждой функции ф (х, у) два множества: Av и В®, min ф (х, у) является функцией от х. Пусть А®
будет множеством всех тех х0, при которых эта функция достигает своего максимального значения. Аналогично max ф (х, у) является функцией
от у. Пусть В® будет множеством всех тех у0, при которых эта функция достигает своего минимального значения. Теперь мы докажем (13:А*) и (13:В*).
Доказательство (13:А*). Выберем х0 из А* и у0 из Бф. Тогда max min ф (х, у) - min ф (х0, у) ф (х0, у о) max ф (х, у0) = min max ф (х, у),
х у у х ух
т. е. max min ф (x, i/) g min max ф (x, г/), что и требовалось.
х у у X
Доказательство необходимости существования седловой точки в (13:В*). Предположим, что
max min ф (х, у) = min max ф (х, у).
х у ух
Выберем х0 в 4Ф и у0 в 5Ф; тогда мы имеем
max ф (х, у о) = min max ф (х, у) = max min ф (х, у) = min ф (х0, у).
х ух х у у
Следовательно, для любого х
Ф (х, у о) max ф (х, у0) = min <р (х0, у) Ф (х0, у0),
т. е. ф (х0, Уо) ф (х, уо), так что ф (х, у0) принимает свое максимальное значение при х = х0. Точно так же для любого у*
Ф (х0, у) min ф (х0, у) = max ф (х, у0) ф (х0, у0),
т. е. ф (яо, у о) Ф (#о, У)\ поэтому ф (х0, у) достигает минимума при у = у0.
Следовательно, пара х0, у0 составляет седловую точку.
Доказательство достаточности существования седловой точки в (13:В*). Пусть х0, Уо - седловая точка. Тогда
max min ф (х, у) min ф (х0, у) = ф (х0, у о),
х у у
min max ф (х, у) max ф (х, у0) = у(х0, Уо)-
ух x
Следовательно,
max min ср (х, у) ср~(#0, у0) min max у(х, у).
х у ~ " ух"
С учетом (13:А*) это дает
max min ср (х, у)=ц> (х0, у0) = min max ср (х, у)
х у ух
и, следовательно, нужное равенство.
13.5.2. Рассуждения п. 13.5.1 приводят к некоторым дальнейшим результатам, которые имеет смысл отметить. Мы предположим теперь существование седловой точки, т. е. справедливость равенства (13:В*).
Для каждой седловой точки х0, у0
(13:С*) ср (#0, уо) =max min ср (х, у) = min max ср у).
х у ух
Доказательство. Это совпадает с последним равенством в доказательстве достаточности (13:В*) в п. 13.5.1.
(13:D*) #0, уо образуют седловую точку тогда и только тогда, когда х0 принадлежит <р, а у0 принадлежит В® 1).
Доказательство достаточности. Пусть х0 принадлежит А®, а уо принадлежит В®. Тогда доказательство необходимости (13:В*) в п. 13.5.1 показывает, что пара х0, у о является седловой точкой.
Доказательство необходимости. Пусть х0, у0 - седловая точка. Воспользуемся (13:С*). Для каждого х должно быть
min ф (#, у) max min ф (х, у) = <р (ж0, у о) = min ф (х0, у)9
уху у
т. е. min ф (х0, у) min ф (хг, у); поэтому min ф (х, у) достигает своего
У У у
максимального значения при х = х0. Следовательно, х0 принадлежит А®. Аналогично для каждого у
max ф (х, у) min max ф (х, у) = ф (х0, у0) = max ф (х, у0),
х у X X
т. е. max ф (х, у0) max ф (х, у)\ поэтому max ф (х, у) достигает
XX X
своего минимального значения при у = у0. Следовательно, у0 принадлежит В®. Это завершает доказательство.
Теоремы (13:С*), (13:D*) указывают, между прочим, на недостатки аналогии, описанной в конце п. 13.4.2, т. е. они показывают, что наше понятие седловой точки уже, чем обиходное представление о седле, или перевале. Действительно, (13:С*) указывает, что все седла, в предположении их существования, имеют одну и ту же высоту. A (13:D*) утверждает, что, если мы изобразим множества А®, В® как два интервала чисел 2), то все седла образуют область, которая имеет форму прямоугольного плато 3).
г) Только при наших предположениях, сформулированных в начале этого пункта. В противном случае седловых точек нет вообще.
2) Если х, у - целые положительные числа, то это, конечно, можно осуществить при помощи двух соответствующих преобразований их областей.
3) Общие математические понятия, упомянутые в сноске 1 на стр. 121, свободны от этих недостатков. Они точно соответствуют обиходному представлению о перевале.
13.5.3. Мы закончим этот раздел доказательством существования седловой точки для одного частного вида х, у и ф (х, у). Далее станет видно, что общность этого частного случая не является незначительной. Пусть дана функция if (х, и) двух аргументов х, и. Рассмотрим все функции / (х) аргумента х, которые принимают значения в области изменения и. Сохраним теперь аргумент х, а вместо аргумента и используем саму функцию /*). Выражение if (х, f (х)) определяется для любых х и /; следовательно, мы можем трактовать if (х, f (х)) как функцию аргументов х, f и взять ее вместо ф (х, у).
Мы хотим доказать, что для этих х, f и if (х, f (х)) (вместо хну и ф (х, у)) существует седловая точка, т. е. что
(13:Е) maxminif(#, f (х)) == min max if (я, f(x)).
! х f fx
Доказательство. Выберем для каждого х значение щ так, чтобы было if (х, щ) = min if) (х, и). Это и0 зависит от х; следовательно,
мы можем определить функцию /0 равенством щ = /0 (#), Тем самым if (х, /о (х)) = min if (х, и). Следовательно,
max if (х, /о (х)) = max min if (i, и).
x х и
Тем более
(13:F) min max if (x, f (x)) :g max min if (#, u).
fx X и
Далее, min if (x, f (x)) есть то же самое, что и min if (х, и), так как /
входит в это выражение только через свое значение при данном х, т. е. / (х), для которого мы можем написать и. Таким образом, min if (х, f (х)) =
= min if (я, и) и потому
(13:G) max min if (x, f (x)) = max min if (x, u).
X f X и
Соотношения (13:F) и (13:G) вместе устанавливают справедливость знака в (13:Е). Знак :g в (13:Е) имеет место благодаря (13:А*). Следовательно, в (13:Е) мы имеем знак равенства, т. е. доказательство завершено.
§ 14. ВПОЛНЕ ОПРЕДЕЛЕННЫЕ ИГРЫ
14.1. Формулировка проблемы
14.1.1. Теперь мы приступаем к рассмотрению игры двух лиц с нулевой суммой. Начнем с использования нормальной формы.
В соответствии с этим игра состоит из двух ходов: игрок 1 выбирает число т4 = 1, . . Pi, а игрок 2 выбирает т2 = 1, . . ., р2 (каждый выбор производится при полном незнании выбора другого игрока), после чего игроки 1 и 2 получают соответственно выигрыши Ж± (тА, т2) и Ж2 (Tl, т2) 2).
х) Читателю предлагается отдать себе отчет в том, что, хотя / является функцией, она вполне может быть аргументом другой функции. 2) См. (11:D) в п. 11.2.3.