- -> -> ->
(17:В:Ь) В есть множество тех г) £ З, для которых max К (£, т])
-> ё
принимает свое минимальное значение, т. е. тех, для которых
-у -У -> ->•
max К г\) = min max К (£, т}) = v.
Т л ?
Теперь можно повторить рассуждения из п. 14.5. При этом мы будем использовать нумерацию, которая соответствует перечислению утверждений (14:С:а) - (14:C:f) в п. 14.5 х).
Во-первых, заметим следующее;
(17:C:d) Игрок 1, играя надлежащим образом, независимо от действий второго игрока может обеспечить себе выигрыш v.
Игрок 2, играя надлежащим образом, независимо от действий первого игрока может обеспечить себе выигрыш - v\
-> -
Доказательство. Пусть игрок 1 выбирает £ А. Тогда независимо от действий игрока, 2, т. е. для всех т), мы имеем К (£, ц) min К (£, т) = v. Пусть игрок 2 выбирает ц £ В. Тогда независимо
от действий игрока 1, т. е. для всех мы имеем К (£, n) 5g max К (£, г]) =
= v. Это завершает доказательство.
Во-вторых, утверждение (17:C:d), очевидно, эквивалентно следующему:
(17:С:е) Игрок 2, играя надлежащим образом, может быть уверен в том, что выигрыш игрока 1 будет v, т. е. он может не дать игроку 1 выиграть > v независимо от того, что делает игрок 1.
Игрок 1, играя надлежащим образом, может быть уверен в том, что выигрыш игрока 2 будет rg - v, т. е. он может не дать выиграть игроку 2 > - v независимо от того, что делает игрок 2.
17.8.2. В третьих, можно утверждать, опираясь на (17:C:d) и(17:С:е) и на рассуждения, приведенные при доказательстве (17:C:d), что
(17:С:а) Оптимальный способ игры (комбинация стратегий) для игрока 1 в игре Г заключается в выборе произвольного I 6 А, где А - множество, определенное в (17:В:а).
(17:С:Ь) Оптимальный способ игры (комбинация стратегий) для игрока 2 в игре Г заключается в выборе произвольного г\ £В, где В - множество, определенное в (17:В:Ь).
В-четвертых, объединение утверждений из (17:G:d) или, что равносильно, из (17:С:е) дает:
(17:С:с) Если оба игрока 1 и 2 оптимально играют в игру Г, т. е. если
£ £ Л, а г] £ то значение К (£, т)) будет равно значению партии (для игрока 1), т. е. v\
г) В связи с этим (а) - (f) появляются в необычном порядке. Это относится также и к п. 14.5, поскольку нумерация в нем основывалась на пп. 14.3.1, 14.3.3, а рассуждения в этих пунктах шли по несколько иному пути.
Используя дополнительно (13:D*) из п. 13.5.2, а также предшествую* щее (17:В:а) замечание о множествах А ж В, мы получаем:
-> -
(17:G:f) Оба игрока 1 и 2 игрют оптимально в игру Г, т. е. £ £А, -у - -> -*
а г\ £ В в том и только в том случае, когда £, ц является седловой
точкой функции К (£, Г]). Все это делает вполне понятным, что v можно в действительности интерпретировать как значение партии игры Г (для 1) и что А и В содержат оптимальные способы игры соответственно для игроков 1 и 2. Во всех рассуждениях (17:G:a) - (17:G:f) нет ничего эвристического или неопределенного. Мы не делали никаких специальных предположений о «способностях» игроков, о том, «кто чью стратегию обнаружил» и т. п. Точно так же наши результаты не основываются и на вере в рациональное поведение противника; важность этого момента мы неоднократно подчеркивали. (См. конец п. 14.1.2, а также п. 15.8.3.)
17.9. Дальнейшие свойства оптимальных стратегий
17.9.1. Результаты (17:С:с) и (17:C:f) в п. 17.8.2 дают также простую и явную характеризацию элементов нашего решения, т. е. число v и множества векторов А ж В.
Согласно (17:С:с) А и В определяют v; следовательно, достаточно только изучить ~А, В, что мы и сделаем, опираясь на утверждение (17:C:f).
На основании этого критерия % £А и г\ £В тогда и только тогда, -у -> -у -у
когда пара £, г\ является седловой точкой функции К (g, rj). Это означает, что
тахК(1\ т)), V
min К (£, т)).
Мы получили это в явном виде, использовав выражение (17:2) из п. 17.4.1 и п. 17.6 для К (, п), а также выражения в лемме (17:А) из п. 17.5.2 для
-У -У -У -у
max К (£\т]) и min К (£, т)). Теперь наши уравнения приобретают такой
вид:
С 02
max 2 & К> Ъ) Пег*
vi vi i Ti T2=1
2j . 2j . fa> t2) ItiTlta = 1 32
min 2 fa, r2) gtl.
Ti=l T2=l
01 32
Замечая, что 2 Sti - 2 т)т2=1> мы можем также написать
n=l т2=1
01 02 02
2 (max ) 2 Ж fa, т2) %2( - 2 W (т4, т2) %2) gTl = О,
Ti=l Т2=1 Т2=1
02 01 01
2 (-min) 2 ЗР(т1,та)&Г1(+ 2 (TbgjnO. т2=1 т: ti=1 xi=l
Слева в этих уравнениях коэффициенты при gtl и rjt2 все О1). Кроме того, все gtl, rjt2 и сами 0. Следовательно, эти равенства имеют место только в том случае, если все слагаемые слева обращаются в нуль. Иными словами, для всех ti = 1, . . ., Pi, для которых коэффициент при £Г1 не равен нулю, должно быть £tl =0; точно так же для всех т2 = 1, . . . 32, для которых коэффициент при г]Т2 не равен нулю, должно бытьг]Г2=0. Резюмируем:
(17:D) 6 А и ц 6 В в том и только в том случае, когда имеет место следующее:
Для всех ti = 1, . . ., Pi, для которых 2 (tu X2J Цх2
Т2=1
не принимает своего максимального значения (по т4), мы имеем Ътг = 0.
Для всех т2 = 1, . . ., р2, для которых 2 Ж (ть t2) In не принимает своего минимального значения (по т2), мы имеем
11X2 = 0.
Легко сформулировать эти принципы словесно. Они выражают следующее.
Если £ и г] - оптимальные смешанные стратегии, то не содержит
-> ->
стратегий т4, которые не оптимальны (для игрока 1) против т), а т) не содержит стратегий т2, которые не оптимальны (для игрока 2)
против Иными словами, т, как и следовало ожидать, оказываются оптимальными друг против друга.
17.9.2. Другое замечание, которое можно сделать в связи с этим, таково:
(17:Е) Игра вполне определена в частном в том и только в том случае, когда для каждого игрока существует оптимальная чистая стратегия.
С точки зрения наших предыдущих рассуждений, в особенности процесса обобщения, с помощью которого мы перешли от чистых стратегий к смешанным, это утверждение можно считать интуитивно убедительным. Однако мы приведем математическое доказательство, которое столь же просто. Оно состоит в следующем.
В последней части п. 17.5.2 мы видели, что как у4, так и v[ получаются
применением операции шах к min 2 3T(ti, т2) £Tl, но по различным
1 Т2 Tl=1
множествам изменения . Для v4 это будет множество всех 8Ti (т4 = = 1, . . ., Pi), а для у[ - множество S. Таким образом, максимизация производится по множеству чистых стратегий в первом случае и по множеству смешанных стратегий во втором. Следовательно, v4 = v, т. е. равенство двух максимумов возможно в том и только в том случае, когда максимум во втором множестве достигается (хотя бы однажды) в пределах первого множества. Это, согласно (17:D), означает, что множеству А должна принадлежать хотя бы одна чистая стратегия, т. е. хотя бы одна чистая стратегия должна быть оптимальной. Таким образом,
г) Проследите, как появились здесь max и min.