2.1. Позиционная форма игры

Информационную структуру игры можно охарактеризовать несколькими способами. Первый подразделяет игры на игры с совершенной и игры с несовершенной информацией. (Хотя мы еще не дали строгого определения позиционной формы игры, мы кратко описали ее в начале гл. 1.)

В игре с совершенной информацией19 каждое информационное множеств одноточечно. В противном случае игра является игрой с несовершенной информацией20.

В игре с совершенной информацией каждый игрок всегда знает точно, в каком месте дерева игры он находится, нет одновременных ходов, и все игроки наблюдают ходы Природы (если таковые есть).

В игре с неполной информацией21. Природа делает ход первой и он ненаблюдаем по крайней мере одним из игроков. В противном случае игра является игрой с полной информацией22.

Игра с неполной информацией является игрой с несовершенной информацией, так как информационные множества некоторых игроков содержат более одной вершины.

Необходимо особо подчеркнуть, что термин «неполная информация» используется в литературе часто и в другом, старом смысле, согласно которому в игре с полной информацией все игроки знают правила игры, а в противном случае игра называется игрой с неполной информацией. До 1967 г. об играх с неполной информацией (в этом смысле) говорили, когда хотели сказать, что их невозможно анализировать. Затем Дж.Харшаньи23 заметил, что любая игра с неполной информацией может быть переформулирована как игра с полной, но несовершенной информацией просто за счет добавления начального хода Природы, когда Природа выбирает между различными правилами.

Итак, рассмотрим теперь более подробно позиционную форму игры.

Рассмотрим простейший пример — игру «крестики- нолики» на поле 3x3. Перенумеруем соответствующие клетки 1 2 3 4 5 6 7 8 9 Будем обозначать игроков соответственно — X и 0 . Тогда дерево этой игры (в нем информационные множества одноточечны) будет иметь вид, изображенный на рис. 1 (цифры у ребер означают номера клеток, в которых ставится соответствующий X или 0, а в вершине, обозначенной N, ход делает Природа, равновероятно (например, подбрасывается монетка) выбирая очередность хода. При этом необходимо иметь в виду, что дерево отображает все возможные ходы независимо от их разумности. N

X Мы не изображаем это дерево полностью, поскольку очевидно, как оно строится. Разумеется, как только выстраивается ряд из трех крестиков или ноликов, то игра заканчивается и победивший игрок получает, скажем, от проигравшего 1 рубль (доллар и пр.). В случае ничьей соответствующие выигрыши — это (0,0), т.е. никто никому ничего не платит и ничего не получает.

Формально позиционная форма игры описывается с помощью следующих элементов: списка игроков; дерева игры; указания для каждой вершины номера игрока (или Природы — игрок номер 0 ), который должен ходить в этой вершине; списка ходов, доступных игроку в каждой вершине и соответствия между ходами и непосредственно следующими вершинами; информационных множеств; указания выигрышей в каждой терминальной (окончательной) вершине; вероятностного распределения на множестве ходов в каждой вершине, в которой ход делает Природа.

Таким образом, мы считаем24, что заданы следующие элементы: 1.

/ = {1,...,га} — конечное множество игроков. 2.

Мы имеем дерево игры с конечным множеством вершин X и конечным множеством ходов А.

При этом должно быть определено отображение р : X —> X U {0}, которое каждой верщине х ставит в соответствие единственную непосредственно предшествующую вершину р(х) , за исключением начальной вершины xq , для которой р(хо) = 0 .

Далее мы должны иметь отображение а : X \ {х0} —> А , ставящее в соответствие каждой вершине х , кроме начальной, ход, который из непосредственно предшествующей вершины р(х) приводит к ж и такой, что если х', х" ? в(ж) и х' ф х" , то а(х') ф а(х") . Множество возможных ходов, доступных в вершине х , есть с(х) = {а ? А : а = а(х') для некоторого х' ? в(ж)} . 4.

Набор информационных множеств % и отображение Н : X \ Т —> % , ставящее в соответствие каждой вершине (кроме терминальной) информационное множество Н(х) ? % . Информационные множества образуют разбиение множества X \ Т. Необходимое требование: все вершины, лежащие в одном информационном множестве имеют одни и те же допустимые ходы, т.е. формально с(х) = с(х') , если Н(х) = Н(х') . Мы можем, таким образом, определить выбор, который доступен игроку в информационном множестве Н :

с(Н) = {а ? А : а ? с(х) для х ? Н}. 5.

Отображение ц : % —> I U {0} , ставящее в соответствие каждому информационному множеству Н ? Ц игрока (или Природу, т.е. игрока i = 0), который должен ходить в вершине из этого множества. Будем обозначать через Hi = {Н ? И : fJ,(H) = i} те информационные множества, в которых очередь хода принадлежит игроку i. 6.

Функция р : Hq X А —> [0,1], ставящая в соответствие ходам в информационных множествах Природы вероятности, удовлетворяющие условию

р(Н, а) = 0 для а ? С(Н)

и

? р(Н,а) = 1 V Не По-

аеС(Н) 7.

Набор функций выигрышей и = {tti(-),..., ип(-)} , иг(-) : Т U.

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

Рис. 2.

для простейшего варианта «крестиков-ноликов» это не очень просто), но все формальности можно было бы соблюсти, приписывая, скажем, выигрыши не терминальным вершинам, а путям, соответствующим разыгрыванию игры.

Важно также отметить, что мы ограничиваемся рассмотрением игр с полной памятью, в которых игроки не забывают то, что они раньше знали, включая свои собственные ходы, сделанные ранее. Игры, изображенные на рис. 2, таковыми не являются.

Определение 2.1.1. Игра в позиционной форме называется игрой с совершенной информацией, если каждое информационное множество состоит из единственной вершины. В противном случае игра называется игрой с несовершенной информацией.

Здесь мы должны остановиться на центральном для бескоалиционной теории игр понятии стратегии. Стратегия — это полный возможный план, который описывает то, как игрок будет действовать в каждых возможных обстоятельствах, когда ему, может быть, придется делать ход.

С точки зрения игрока, множества возможных обстоятельств представлены набором его информационных множеств, причем каждое информационное множество представляет различные различимые обстоятельства, в которых ему может потребоваться ходить. Тем самым стратегия игрока сводится к описанию того, как он планирует ходить в каждом из его информационных множеств.

Определение 2.1.2. Пусть %i — семейство всех информационных множеств игрока i, А — множество всех возможных ходов (действий) в игре, С(Н) С А — множество ходов, возможных в информационном множестве Н. Стратегия игрока i — это отображение S; : %i —> А такое, что Si(H) ? С(Н) для каждого Н ? %i .

То, что стратегия — это полный возможный план, нельзя недооценивать, особенно, как мы увидим, это будет важно в дальнейшем. Определение игроком своей стратегии подобно написанию перед игрой инструкции относительно того, как его представитель может действовать, просто заглядывая в эту инструкцию. Или, иначе, определение игроком i своей стратегии можно трактовать следующим образом: в каждом информационном множестве игрока i находится его агент, которому он сообщает, какой ход должен будет сделать этот агент, если ему придется делать ход, т.е. игра «дойдет» до соответствующего информационного множества.

Здесь очень важно иметь в виду следующее. Как полный план стратегия часто определяет действия игрока в информационных множествах, которые могут быть даже не достигнуты во время действительного разыгрывания игры. Так, в крестиках-ноликах стратегия игрока О описывает, в частности, то, что он будет делать, если на 1-м ходу X сыграет в центр. Но в действительной игре можно сыграть вовсе не в центр. Более того, стратегия игрока может включать планы действий, которые его собственная стратегия делает неуместными. Опять же в «крестиках-ноликах» стратегия игрока X включает описание того, что он будет делать после того, что он сыграет на первом ходу в «центр», а 0 ответит в «левый нижний угол», даже если X на первом ходу играет «верхний левый». Это, возможно, кажется странным, но играет очень важную роль в динамическом случае. Итак, еще раз:

Стратегия — это полный возможный план действий, который говорит, что игрок будет делать в каждом его информационном множестве.

Рассмотрим следующую простую игру (рис.3).

Рис. 3.

У первого игрока две стратегии: Н и Т. А у игрока 2 их четыре; поскольку у него 2 информационных множества, следовательно, каждая стратегия должна определять ход в каждом из этих информационных множеств. А именно:

si : Н , если 1-й сыграл Н ; Н , если 1-й сыграл Т ;

«2 : Н , если 1-й сыграл Н ; Т , если 1-й сыграл Т ; 53

: Т , если 1-й сыграл Н ; Н , если 1-й сыграл Т ; 54

: Т , если 1-й сыграл Н ; Г , если 1-й сыграл Г .

Отметим здесь еще одно чрезвычайно важное обстоятельство. Имея набор стратегий каждого игрока, мы можем построить нормальную форму данной игры: поскольку выбор игроками своих стратегий определяет ход в каждом информационном множестве, значит, полностью определяет траекторию или «путь», по которому будет развиваться игра. Нормальная форма игры, изображенной на рис. 3, есть Sl s2 s3 s4

Я / (аь61) (аь61) (a2,b2) (a2,b2) \

T V (a3,b3) (а4,64) (аз, 63) (a4,b4) у

Каждый набор стратегий определяет траекторию «движения» по дереву и тем самым определяет исход игры. Ясно также, что мы имеем возможность говорить о равновесии по Нэшу.

Прежде чем обратиться к более подробному рассмотрению равновесия по Нэшу приведем теорему существования.

Теорема 2.1.1. (Kuhn, 1953)25. В конечной игре с совершенной информацией существует равновесие по Нэшу в чистых стратегиях.

Мы начнем со следующего примера, который покажет, что равновесие по Нэшу не всегда дает разумное предсказание.

Пример (Mas-Colell, Whinston, Green). Фирма Е (entrant) — новичок — рассматривает вопрос о том, входить ли на рынок, где в текущий момент есть одна единственная укоренившаяся фирма I (incumbent). Если Е решается на вход, то I может ответить двумя способами: она может предоставить вход, отдавая часть своих продаж, но не изменяя цену, либо она может вступить в хищническую войну, которая приведет к «драматическому» снижению цен. Дерево, соответствующее рассматриваемой ситуации, изображено на рис.4.

Нормальная форма этой игры имеет следующий вид (рис. 5):

I вх

од

Е

нет

Предоставить (если «вход») (0,2)

(2,1)

Война (если «вход») (0,2)

(-3,-1)

Рис. 5.

Здесь две ситуации равновесия по Нэшу в чистых стратегиях: (нет, война) и (да, предоставить). Но первая из этих ситуаций — это не разумное предсказание: фирма Е может предвидеть, что если она изберет «вход», то I в действительности изберет «предоставить», т.е. «война, если вход» — не заслуживает доверия.

Для того чтобы исключить ситуации типа (нет; война, если вход), мы рассмотрим «принцип последовательной рациональности»: стратегия игры должна предписывать оптимальный ход в каждой вершине дерева. Т.е. если игрок находится в некоторой вершине дерева, его стратегия должна предписывать

оптимальный выбор, начиная с этой точки, при данных стратегиях его оппонентов. В этом смысле стратегия «война, если вход» таковой не является, ибо после входа единственная оптимальная стратегия для I — «предоставить». В нашем примере сделать все очень просто: начнем с того, что определим оптимальное поведение для I в игре на этапе «после входа» — это, очевидно, «предоставить». Теперь мы можем определить оптимальное поведение фирмы Е до этого момента, с учетом предвидения того, что произойдет после входа. Это можно сделать, рассмотрев «редуцированную» позиционную форму, где «пост-входное» принятие решения I заменено на соответствующие выигрыши, которые возникают при оптимальном «пост-входном» поведении фирмы I (рис.6). А это уже простейшая задача принятия индивидуального решения, причем решение — «вход».

Рис. 6.

Этот тип процедуры, которая начинается с нахождения оптимального поведения «в конце игры», а затем определения оптимального поведения на более ранних шагах в предвидении того, что будет происходить дальше, называется обратной индукцией26. (Подчеркнем, что сказанное относится к конечным играм с совершенной информацией, т.е. конечным играм с «одновершинными» инормационными множествами.)

Однако, прежде чем остановиться на обратной индукции более подробно, мы должны отметить следующее достаточно существенное обстоятельство, касающееся смешанных стратегий. А именно, если мы рассматриваем игры в позиционной форме, то игроки могут рандомизировать свои чистые стратегии способом, отличным от стандартного, в котором используются смешанные стратегии, приписывающие каждой чистой стратегии игрока (множество которых может быть очень большим) вероятность того, что игрок будет ее играть. В позиционной форме появляется возможность рандомизации раздельно в каждом информационном множестве. Такой способ рандомизации приводит к стратегиям поведения.

Определение 2.1.3. В игре в позиционной форме Г^; стратегия поведения игрока i определяет для каждого информационного множества Н ? %i и альтернативы а ? С(Н) вероятность Ai(a,H) > 0, причем Н) = 1 для

всех Н ? %i .

Оказывается (Kuhn, 1953; см. также, например, Петросян, Зенкевич, Семина, 1998), что для игр с полной памятью эти два типа рандомизации эквивалентны. (Важно подчеркнуть, что полная память играет здесь ключевую роль.) А именно, для любой стратегии поведения игрока i существует его смешанная стратегия, дающая в точности такое же распределение выигрышей для любых стратегий (смешанных или стратегий поведения), которые могут играться остальными игроками, и наоборот.

Это соответствие можно установить следующим образом. Будем, как всегда, обозначать чистые стратегии игрока i через Si . Пусть Ui — некоторая его смешанная стратегия. Будем называть некоторую вершину х дерева Г^; возможной для Si , если существует такой набор стратегий s = (s4-,s_j-) , что траектория, определяемая этим набором, проходит через

s . Обозначим множество всех возможных для вершин через P(si) .

Информационное множество Н называется существенным для Si , если оно содержит некоторую возможную для Si вершину. Множество существенных для Si информационных множеств обозначим через R(si) .

Пусть ai — некоторая смешанная стратегия игрока i. Тогда стратегия поведения Аг-, соответствующая смешанной стратегии аг-, определяется следующим образом. Если Н ? R(si) , то

( Е{8г:ЯбД(8г),8г(Я) = а}СТ'(5') ( А г(а,Н)- — —— . (*)

Z^{st-.HeR(st)} ai\si)

Если Н R(si) , то знаменатель этой дроби обращается в ноль, поэтому стратегию Аг- можно определить произвольно, например,

A i(a,H)= crt(st).

{s,:s,(H) = a}

Если Ai — стратегия поведения, то аг- можно определить как

YlXi(Si(H),H).

Я

При этом Ai оказывается стратегией поведения, соответствующей ai. Поэтому в играх с полной памятью (а именно такие игры мы и рассматриваем) безразлично, каким способом ран- домизировать. Терминологически мы всегда будем говорить о смешанных стратегиях.

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

Пример (Osborn, Rubinstein). Рассмотрим игру, изображенную на рис. 7.

Пусть смешанная стратегия игрока а определяется следующим образом: с вероятностью 1/2 играется L , а потом еще

раз L , и с вероятностью 1/2 играется R , а потом еще раз R . Исходом, соответствующим этой стратегии, является распределение (тр 0, 0,-j) на множестве терминальных вершин. Но такой исход не может быть обеспечен ни одной стратегией поведения: стратегия поведения ((р, 1 — р), (q, 1 — q)) инициирует распределение на множестве терминальных вершин, в которых исход, соответствующий и2 , имеет вероятность 0 в случае только, если р = 0 или q = 1 , но тогда вероятность (L,L) или (R, R) есть 0.