ИГРЫ С ПОЛНОЙ ИНФОРМИРОВАННОСТЬЮ

Определение игры в развернутой форме
Развернутая форма – естественный способ представления са-
лонных игр, вроде шахмат или преферанса. Однако и другие игры
(по крайней мере, дискретные), обычно сначала рассматриваются
в развернутой форме.
Для того чтобы продемонстрировать основные элементы
описания игры в развернутой форме, вспомним пример 4 «Ми-
нипокер» (см. рисунок 5).
Игры в развернутой форме представляются в виде дерева,
вершины которого представляют собой текущие игровые ситуа-
ции. Вершины соединяются дугами, которые означают возможные
переходы между ситуациями. Если из данной вершины выходят
несколько дуг, это значит, что в данной ситуации ход игры зависит
от выбора одного из игроков или от реализации внешнего
события. Самая левая вершина («корень» дерева) означает си-
туацию в начале игры, конечные (терминальные) вершины озна-
чают возможные исходы игры. Каждой конечной вершине по-
ставлен в соответствие вектор выигрышей игроков. В случае двух
игроков этот вектор состоит из пары чисел – значений полезности
игроков при заданном исходе игры.
52
Для каждой нетерминальной вершины необходимо указать,
какой игрок контролирует данную вершину, то есть осуществляет
выбор. Вершина может и не контролироваться ни одним из
игроков, тогда эту вершину контролирует природа (как, например,
стартовую вершину в примере 4). Вершина, контролируемая
игроком с номером i, называется еще «точкой выбора i-го игро-
ка».
При каждом розыгрыше игроки (и реализация природных
факторов) выбирают путь в этом дереве от стартовой вершины до
одной из терминальных вершин.
Немаловажной деталью описания игры в развернутой форме
является информированность игрока в каждой контролируемой им
игровой ситуации. Из рисунка 5 видно, что, поскольку первый
игрок знает, выпала ему красная или черная карта, он может раз-
личить две ситуации принятия решения, в отличие от второго
игрока, который не знает цвета масти выпавшей карты, но должен
принять решение: принять ставку или спасовать. Значит, для
полноты описания необходимо, помимо игрока, контролирующего
данную вершину, указать информационное состояние, в котором
он находится. На рисунке 5 контролируемые вершины второго
игрока объединены пунктиром, чтобы показать, что им соот-
ветствует одно информационное состояние, названное – «Наугад».
Заметим, что возможные альтернативы вершин, объединенных
одним информационным состоянием, должны совпадать, иначе
нарушается предположение об одинаковой информированности
игрока в обеих ситуациях.
Таким образом, для описания игры n лиц в развернутой фор-
ме необходимо определить:
1) Дерево, ребрам и вершинам которого присвоены сле-
дующие метки:
2) Каждой терминальной вершине Fi ставится в соот-
ветствие метка-«вектор выигрышей», то есть числовой вектор
f(Fi)=(f1, f2, …, fn) (размерности n) выигрышей (полезностей)
игроков.
3) Каждой нетерминальной вершине ставится в соответ-
ствие метка контроля – номер игрока i Î N = {1, 2, …, n},
53
контролирующего вершину. Если данную вершину контроли-
рует природа (внешние обстоятельства, случай и т.д.), то эта
метка равна нулю.
4) Каждой нетерминальной вершине ставится в соответ-
ствие метка информационного состояния игрока (обычно она
отделяется от номера игрока точкой).
5) Каждое ребро помечено возможными альтернативами,
доступными для выбора игрока, контролирующего вершину,
из которой выходит данное ребро. Если вершину контролирует
природа, метки должны обозначать вероятности реализации
данной альтернативы, причем сумма вероятностей должна рав-
няться единице.
6) Набор исходящих ребер множества вершин с одним
информационным состоянием имеет одинаковый набор мар-
кировок.
Определение 1: Игрой в развернутой форме называется систе-
ма 1-6.
Описание игры в развернутой форме довольно сложно, хотя и
содержательно богато. Следует ожидать, что и формулировка
понятия решения для таких игр будет громоздка. Поэтому вместо
того, чтобы подробно исследовать игры в развернутой форме,
введем новую, более простую форму игры (нормальную, или
стратегическую форму), определим формальную процедуру пе-
рехода от игр в развернутой форме к играм в нормальной форме, и
на время забудем о существовании развернутой формы вообще.