Лекция 4. Поведенческие и смешанные стратегии

Поведенческие стратегии. Вооружившись вероятностными понятиями, вернемся к играм в развернутой форме со случайными ходами. Пусть игроки определились со стратегиями; тогда из каждой позиции дерева игры, контро­лируемой игроками, выходит некоторая отмеченная стрелка. Однако есть еще и позиции, где ход делает "природа", и эти ходы имеют случайный характер. Вследствие этого траектория игры теряет определенность и тоже становится случайной.

Объясним это более формально, но предварительно заметим следующее. Раз уж мы допускаем случайные ходы природой, можно предоставить эту воз­можность и игрокам. Это означает, что находясь в некоторой позиции (точ­нее, в информационном множестве /г), игрок может, "бросив монету", сделать случайный ход, то есть выбрать не "чистый" ход (элемент из Д7(//)). а "сме­шанный" (то есть элемент из А(М(/г))). Заметим, что такое вторжение случая не ограничивает суверенитет игрока: выбор по-прежнему принадлежит ему, и при желании он может выбрать "чистый" ход. Зачем ему обращаться к "рулетке" - это отдельный вопрос, к которому мы еще вернемся.

Так мы приходим к понятию поведенческой стратегии. Это выбор игро­ком г смешанного хода (3{К) £ А(М(/г)) в каждом "своем" информационном множестве 1г £ Я^.

Траектория игры. Когда все игроки выберут поведенческие стратегии, то для каждой нетерминальной позиции х дерева игры Г будет указан случай­ный ход (или стрелка) /3(х) £ А(А(х)) (напомним, что А(х) - это множество стрелок, выходящих из вершины х). Каким будет исход (конечно, тоже слу­чайный) в этой ситуации? Иначе говоря, что назвать траекторией развития игры? Ясно, что эта траектория будет "смешанной"; так вот как приписать вероятности каждой конкретной траектории?

Делается это постепенно. Мы припишем число тт(х) каждой позиции х (ве­роятность прохождения игры через эту позицию х). Корневой (начальной) позиции приписывается число 1. Остальным позициям числа приписываются по индукции. Пусть х - некорневая позиция. Тогда существует единственнаястрелка а, которая входит в х. Обозначим через у начало этой стрелки, так что а = (у, х). Позиция у находится "ближе к корню" и поэтому для нее уже определено число тт(у). Положим теперь тт(х) = тт(у)/3(у)(а). (Неявно тут содержится предположение о независимости рандомизации в разных верши­нах, но оно невинно.) Так шаг за шагом мы припишем числа всем позициям, в том числе терминальным. Легко понять (докажите!), что сумма чисел тт(х) по всем терминальным позициям (х £ Т) равна 1, то есть мы получаем веро­ятностную меру на Т. Это и есть исход игры; конечно, он зависит от выбора поведенческих стратегий.

Если в терминальных вершинах указаны выигрыши (в терминах полезно­сти Неймана-Моргенштерна), мы можем перейти к средним и получить уже числовые выигрыши. Тем самым мы по игре в развернутой форме получили некоторую игру в нормальной форме - поведенческое расширение.

Смешанные стратегии. Выше мы исходили из игры в развернутой фор­ме. Похожую операцию "смешанного расширения", и даже еще проще, можно сделать и для игры в нормальной форме. Пусть дана игра в нормальной фор­ме и : —у Шм, или лучше - игровая форма (механизм) г : 5дг —> А. Смешанной стратегией игрока г называется лотерея £ Д(<%) на множестве чистых стратегий 5^. Грубо говоря, вместо того, чтобы четко придерживаться всегда одной и той же стратегии Si7 игрок "бросает монету" и в зависимости от этого применяет ту или иную стратегию.

Что же считать исходом, если игроки придерживаются смешанных страте­гий а{1 Конечно, лотерею г^(а\®.. .®ап) £ А(А). Неявно тут предполагается, что рандомизации отдельных игроков некоррелированы, независимы. В про­тивном случае мы получаем т.н. коррелированные стратегии, о которых еще поговорим в свое время. Если же нас интересуют численные значения вы­игрышей, мы должны брать средние выигрыши, то есть § що1(а\ ® ... ® о~п). Иначе говоря, (средний) выигрыш игрока г при профиле смешанных страте­гий (о"1,..., ап) равен

суммирование ведется по 5дг, то есть по всем профилям чистых стратегий. Полученная игра (в нормальной форме)

хгА(5г) —► Еж

называется смешанным расширением игры С и обозначается Ст.

Сравнение смешанных и поведенческих стратегий. Таким образом, есть два способа введения рандомизации в игру, заданную развернутой фор­мой Г. Один - взять поведенческое расширение. Второй - образовать сначала нормальную форму С и затем ее смешанное расширение. Заматим, что фор­мально они различаются - у них разные стратегические множества. В первой игре стратегия игрока г - это элемент множества х^щ^М^Н)), тогда как во второй - элемент множества А(х/1ея^М$(^))-

Кто-то предложил такую аналогию. Чистая стратегия - это книга, страницы кото­рой соответствуют информационным множествам, а на каждой странице записан тот ход, который нужно сделать в этом месте. Набор всех чистых стратегий - библиотека. Что­бы реализовать смешанную стратегию, нужно случайно выбрать книгу. А поведенческая стратегия - это снова книга, только на каждой странице указан не один ход, а вероятности выбора ходов.

Довольно ясно, что между этими двумя вариантами рандомизации имеет­ся тесная связь. Скажем об этом более точно. Так как речь будет идти про каждого игрока отдельно, мы опускаем индекс игрока г. Тогда поведенче­ская стратегия - это элемент множества Х/1е#Д(М(/г)), а смешанная страте­гия - элемент множества Д(х^еяМ(/г)). Задавшись поведенческой стратегией /3 = (/3(к),к £ Я), мы легко образуем смешанную стратегию <т = ®ф(К). Обратно, если дана смешанная стратегия а £ А(х/!бяМ(^)), можно спроек­тировать эту меру на каждое М(Ь) и получить набор (/?(/г), Н £ Н), то есть поведенческую стратегию (3.

Однако, несмотря на естественность этих операций, соответствующие друг другу смешанная а и поведенческая (3 стратегии могут приводить к разным исходам. Поясним это на примере.

Пример. Игрок на первом шаге может пойти либо направо Д, либо налево Ь. После этого он "забывает", что делал на первом шаге, и снова стоит перед выбором г или I.

/I  \ /I V

а        Ъ с ,

Пример забывчивого игрока

 

а!

Соответствующие 4 исхода обозначим а, 6, с и с^.

Игрок имеет 4 чистые стратегии: (Ь: /) с исходом а, (£, г) с исходом Ъ и т.д. Рассмотрим смешанную стратегию а = 0.5 ® (£,0 + 0.5 ® (Я, г); она приводит к исходу 0.5<8)а+0.5<8)с?. Ассоциированная поведенческая стратегия советует в каждом из информационных множеств с равными вероятностями идти направо или налево; иначе говоря, (3(1) = 0.5 ® Ь + 0.5 II и = 0.5®^ + 0.5(8>г. Такая поведенческая стратегия с равными шансами (по 1/4) приводит к исходам а, 6, с и г/.

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

Совершенная память. Еще более разительный пример отсутствия памяти дает сле­дующий пример (снова с одним игроком).

Здесь всего два хода и две (чистые) стратегии: А (вперед) и В (вниз). Обе дают выигрыш, равный 0. Соответственно, любая смешанная стратегия дает нулевой выигрыш. Однако поведенческая стратегия /3 = 0.5 ® А + 0.5 ® В в среднем дает выигрыш, равный 1!

Не вдаваясь в точные определения и доказательства (см. Майерсона), поясним все же, что означает совершенство памяти. Совершенство памяти означает три требования. Первое. Предположим, что в позиции х игрок делает ход и переводит игру в позицию у. Тогда я; и у не входят в одно информационное множество этого игрока. Неформально -игрок помнит, сделал ли он ход. Во втором примере это требование нарушено. Второе. Предположим, что некоторый игрок в позиции х может сделать два хода, переводящие игру в позиции у и у'. Пусть, далее, позиция г встречается после у, а позиция г' - после у'. Тогда г и г' не могут входить в одно информационное множество для нашего игрока. Это требование нарушено в первом примере этой лекции. Наконец, если ушу'- две позиции, находящиеся в разных информационных множествах, а. у и у' как раньше, то снова гиг' не могут входить в одно информационное множество для нашего игрока.

Тем не менее, даже в случае совершенной памяти, нужно немного модифицировать конструкцию поведенческой стратегии /3 по смешанной стратегии о. Пусть дано информа­

 

Забывчивый шоферционное множество к е Щ игрока ц мы должны указать вероятностную меру /3(/г) е М^К). Приведенное выше "наивное" определение состояло в том, что мы брали в качестве /3(/г) усредненный по о ход в позиции К. То есть считали, что /3(/г)(т) = (здесь т е Мг(/г), а 5 пробегает множество Б{ чистых стратегий. Правильное определение состо­ит в том, что мы вместо усреднения по о должны усреднять по условной мере, полученной при условии, что стратегия 5 в принципе допускает прохождение траектории игры через /г. Более точно, скажем, что стратегия 5 допускает прохождение игры через п, если суще­ствуют стратегии других игроков, при которых вероятность 7г(/г) прохождения траектории игры через К положительна. Обозначим через Б* (К) С Б{ множество стратегий г-го игрока, которые допускают прохождение игры через К. И тогда