Определение игры в развернутой форме

Лекция 3. Игры в развернутой форме. Переход от игры в развернутой форме к игре в нормальной форме. Смешанные стратегии.

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

Игры в развернутой форме представляются в виде дерева, вершины которого представляют собой текущие игровые ситуации. Вершины соединяются дугами, которые означают возможные переходы между ситуациями, Если из данной вершины выходят несколько дуг, это значит, что в данной ситуации ход игры зависит от выбора одного из игроков или от реализации внешнего события. Самая левая вершина («корень» дерева) означает ситуацию в начале игры, конечные (терминальные) вершины означают возможные исходы игры. Каждой конечной вершине поставлен в соответствие вектор выигрышей игроков. В случае двух игроков этот вектор состоит из пары чисел – значений полезности игроков при заданном исходе игры.

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

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

Для описания игры n лиц в развернутой форме необходимо определить:

1) Дерево, ребрам и вершинам которого присвоены следующие метки:

2) Каждой терминальной вершине ставится в соответствие метка-«вектор выигрышей», то есть числовой вектор (размерности n) выигрышей (полезностей) игроков.

3) Каждой нетерминальной вершине ставится в соответствие метка контроля – номер игрока контролирующего вершину. Если данную вершину контролирует природа (внешние обстоятельства, случай и т.д.), то эта метка равна нулю.

4) Каждой нетерминальной вершине ставится в соответствие метка информационного состояния игрока (обычно она отделяется от номера игрока точкой).

5) Каждое ребро помечено возможными альтернативами, доступными для выбора игрока, контролирующего вершину, из которой выходит данное ребро. Если вершину контролирует природа, метки должны обозначать вероятности реализации данной альтернативы, причем сумма вероятностей должна равняться единице.

6) Набор исходящих ребер множества вершин с одним информационным состоянием имеет одинаковый набор маркировок.

Определение 1:Игрой в развернутой форме называется система 1-6.

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