§ 5. К ТЕОРИИ СТРАТЕГИЧЕСКИХ ИГР
1. В 1926 г. Дж. фон Нейман занимается игровыми вопросами *). Он обсуждает их с Д. Кёнигом, а 7 декабря, накануне дня, когда ему исполнилось двадцать три года, выступает перед гёттингенским математическим обществом с докладом о теории игр. Через полтора года в томе 100 журнала «Mathematische Annalerm появляется статья фон Неймана «К теории стратегических игр».
Эта статья содержит важнейшие идеи современной теории игр и ее основополагающие результаты.
Сам фон Нейман формулирует цель этой статьи как попытку дать ответ на следующий вопрос: «Пусть п игроков Si, S2, . • Sn играют данную стратегическую игру @; как должен действовать отдельный игрок Sm, чтобы добиться по возможности наиболее благоприятного результата?». Он, правда, не перечисляет возможных практических интерпретаций этого вопроса, но замечает, что «едва ли найдется в повседневной жизни ситуация, в которой он бы не возникал». Однако сама постановка, по мнению фон Неймана, недостаточно ясна.
В сущности, основным достижением данной статьи и является четкая математическая формулировка этого вопроса, которая позволила не только дать на него ответ, но и указать своеобразное «исчисление» вопросов такого рода.
Статья начинается определением стратегической игры п игроков Si, . . . , Sn путем задания системы событий («ходов»), которые делаются игроками или же случаем. Тем самым игра @ задается как позиционная с нулевой суммой (т. е. при любом исходе игры сумма выигрышей всех игроков равна нулю). Такие игры называются также антагонистическими.
Далее фон Нейман устанавливает, что фактически стратегиями игроков являются системы из возможных действий в различных информационных состояниях. Это дает возможность при решении основных теоретических вопросов ограничиться нормальной формой игры, в которой стратегии игрока рассматриваются независимо от их происхождения, т. е. как элементы абстрактного множества стратегий.
Случаи, когда число п участников игры равно 0 или 1, не представляют интереса. Случай же п = 2 не только является простейшим из нетривиальных, но, как окажется в дальнейшем, принципиально важным для всей теории. Поэтому фон Нейман переходит к подробному изучению игры двух лиц с нулевой суммой, правила которой он формулирует так:
«Игроки Si, S2 выбирают каждый, не зная выбора другого, соответственно по одному из чисел 1, 2, . . ., 24 и 1, 2, . . ., 22. Если они выбрали числа х и у, то получают соответственно суммы g (х, у) и - g (х, у). При этом функция g (х, у) может быть совершенно произвольной (определенной для х = 1, 2, . . ., у = 1, 2, . . ., 22)».
После этого идут рассуждения, которые в наше время выглядят трафаретными и даже примитивными, но именно они составляют ядро теории игр, выделяющее ее из остальных разделов математики. Речь идет о том, что игрок Si при любом своем выборе х получает выигрыш не меньший, чем min g (х, у), и поэтому должен выбрать х так, чтобы макси-у
мизировать этот минимум, т. е. обеспечить себе получение max ming (х, у).
х у
Игрок же #2 может не дать Si большего выигрыша, чем
min max g (х, у).
у х
Равенство
max min g (х, у) = min max g (х, у)
х у ух
освобождает оптимальность действий игроков от какого-либо психологического налета. Те значения х и у, на который достигаются в этом равенстве внешние экстремумы, очевидно, оказываются оптимальными стратегиями игроков Si и S2- Общее значение частей этого равенства есть та сумма, которую Si уверенно выигрывает, но больше которой ему при правильной игре противника получить не удастся. Оно называется значением рассматриваемой игры.
То обстоятельство, что это равенство не обязательно имеет место, фон Нейман пытается преодолеть тем яе способом, каким Борель за несколько лет до него, именно введением смешанных стратегий I = (£ь • • •> £zx) и т) = (r\i, . . ., г]22). Но у Бореля логическая цель выражалась в виде некоторого довольно сложного утверждения (см. 1.4.2). Фон Нейман же придает ей вид равенства
max min h (£, n) = min max h (g, ту), (1)
где fe(£, r) есть билинейная форма:
т])= 2 2 g(p, 9)lPi\q;
p=l q=i
Таким образом, фон Нейман устанавливает существование значения для любой конечной антагонистической игры и оптимальных (возможно, смешанных) стратегий игроков в ней. Тем самым он рассеивает сомнения Бореля и опровергает то предположение, к которому Борель в своих сомнениях склонялся.
Предложенное фон Нейманом доказательство равенства (1) является весьма сложным и неконструктивным. Оно опирается на теорему Брауэра о неподвижной точке. Это представляется тем более удивительным, что фактически доказываемое утверждение устанавливалось ранее неоднократно, правда в терминах выпуклых множеств (Минковским [1]) и линейных неравенств (Штимке [1]). Однако прошло еще десять лет, прежде чем Билль [1] обнаружил связь между этой игровой проблемой и теорией выпуклых множеств и дал элементарное доказательство равенства мини-максов.
2. После того как принципиальные основы поведения участников антагонистической игры (т. е. игры двух лиц с нулевой суммой) оказываются вполне ясными, фон Нейман переходит к анализу игр с числом участников, превосходящим 2. Но уже в случае игр трех лиц (и даже для игр двух лиц с ненулевой суммой) возникают дополнительные трудности. Не пытаясь их преодолевать (заметим попутно, что и до сих пор не удалось построить исчерпывающей теории игр трех лиц), фон Нейман встает на путь изучения возможных редукций игр многих лиц к антагонистическим играм. Он подробно рассматривает эти редукции для случая п = 3 и намечает осуществление аналогичной программы для игр, в которых более трех игроков. Идея фон Неймана состоит в следующем.
Пусть мы имеем игру трех лиц с нулевой суммой, в которой игроки Si, S2 и S3, выбирая независимо друг от друга стратегии х = 1, . . . , Si, у =1, . . . , 22 и z = l, . . ., 3, получают соответственно выигрыши ,£1 (# , г/, z), g2 (х, у, z), и g3 (х, у, z), для которых тождественно выполняется равенство
#1 + £2 + £з = 0.
Рассмотрим всевозможные антагонистические игры, получающиеся в результате объединения любых двух игроков против оставшегося (очевидно, всего в данном случае мы будем иметь три таких антагонистических игры). Найдем значения этих игр: Si s2 s3
max min 2 2 2 (.?i(P» q,r) + gz(p, q,r))lpqr\r = Mu2,
g TJ p=lg=lr=l
Si s2 s3
max min 2 2 2 (giiPi Ъ r)+g3(P, r)) lprV\q = Mit3,
I T) Tp=lq=lr=l
Si s2 s3
max min 2 2 2 (#2 (P, Q, r) + g3 (p, q, r)) lqrv\p = M2, 3.
I T) p=l q=l r=l
Здесь %pq образуют систему вероятностей на множестве пар (р, q); аналогично 1рг и l~qr. Нетрудно показать, что
Ми2 + Миз + М2,30. % (2)
Целью каждого игрока является получение возможно большего выигрыша. Какую же цель, скажем, для Si можно считать осуществимой?
Предположим, что St стремится выиграть w. Его противники, объединившись друг с другом, дадут ему не более чем -M2t3. Значит, если
Wi-M2t3, (3)
то цель Si осуществима. В противном случае ему необходимо вступить в коалицию с одним из своих партнеров по игре.
Если Зимея в виду получить wu объединится с S2, то на долю S2 останется Miy2 - ш4, а если Si объединится с S3, то S3 получит Mii3 - w±. Значит, S2 и S3 «вместе» получат Mit2 + Mit3 - 2u?i. Но, отвергнув предложения о союзе со стороны Si и вступив в коалицию друг с другом, они получат M2j3. Если
M2t3>Mit2 + MU3-2Wi,
то как для S2, так и для S3 нет смысла откликаться на призывы 5, который, таким образом, остается в одиночестве. Следовательно, чтобы найти союзника, Si должен преследовать умеренные цели:
Wt 4 \ \{Миг + Л/1,8 - 2,з) = Щ
(ввиду (2) это ограничение все-таки менее стеснительно, чем (3)). Аналогично получается, что желательные выигрыши w2 и w3 игроков S2 is. S3 -ограничиваются соответственно неравенствами:
w3±(Mit3 + M2,3-Mu2) = w3.