Промышленный лизинг Промышленный лизинг  Методички 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 [ 207 ] 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227

Игрок же #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.



Но вместе с тем цели wu тгж w3 осуществимы для любой пары игроков* при объединении пары в коалицию претензии ее членов удовлетворяются!. Разумеется, оставшийся вне коалиции игрок при этом полностью обЙ* рается .

3. Для произвольного числа игроков п можно рассуждать аналогичным образом. Именно произвольное разбиение всего множества игройбв на две противостоящие друг другу коалиции р,!, . . . , \ik и vi, ... , определяет некоторую антагонистическую игру и тем самым, как ее зМче-ние, величину ...tiiky для любой коалиции ци . . ., \ik.

Как нетрудно убедиться,

1) М{} = 0;

2) M{lll.....м+ M{vu ..Vn k} = 0,

если теоретико-множественная сумма коалиций (Hi, . . ., и v1? . . ., составляет все множество игроков;

3) Minl.....и,> + M{Vi.....v M{lli.....Vl.....v}, если коалиции (Xi, . . . , \ik и vi, . . ., не пересекаются.

Свойства величины М, как функции коалиции, являются вместе с тем существенными свойствами исходной игры. В дальнейшем эта функция получила название характеристической функции и изучалась в многочисленных работах.

Описанный подход в какой-то мере напоминает корреляционную теорию случайных функций, где изучение совместных распределений многих случайных величин ограничивается лишь нахождением и сравнением i между собой коэффициентов корреляции всевозможных пар случайных величин. Вводимая при этом характеристическая функция по своей роли в теории игр напоминает корреляционную функцию. Разумеется, это сходство носит чисто логический, а не формальный характер.

4. Мы видим, что в статье фон Неймана содержится большинство фундаментальных идей современной теории стратегических игр, и историю теории игр следует начинать именно с нее. Поэтому фон Неймана можно по праву называть основоположником теории игр. Однако в ближайшие последующие годы статья фон Неймана не нашла ни откликов, ни продолжений в математической литературе того времени. Единственным исключением является уже упоминавшаяся работа Билля [1], содержащая упрощенное доказательство теоремы о минимаксе и полученное на основе исследования игр типа покера распространение ее на случай игр с бесконечными множествами стратегий. В частности, в ней доказывается, что всякая бесконечная антагонистическая игра, в которой множество стратегий каждого игрока является единичным сегментом (такие игры теперь принято называть играми на единичном квадрате), а функция выигрыша непрерывна, имеет значение в смешанных стратегиях.

Между прочим, уже в этой статье приводится пример игры (разумеется, с бесконечным множеством стратегий), которая не имеет значения (в смешанных стратегиях). Тем самым вновь возник вопрос, поднятый в свое время Борелем (см. 1.4.2), о возможной ограниченности вероятностного подхода к стратегическим играм и о необходимости психологического подхода к ним.

Таким образом, если говорить о 20-х и 30-х годах, фон Неймана также нельзя признать (пользуясь терминологией Легуве - Фреше) за инициатора теории игр.



1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 [ 207 ] 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227