3.4.3. Решение позиционной игры с полной информацией

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

Для того чтобы это продемонстрировать, рассмотрим описанную выше игру “Выборы с правом вето”. Поскольку из всех вершин, предшествующих конечным, ходит игрок 3, то остальные игроки, зная его функцию выигрыша U₃, могут легко предвидеть его решения. Это позволяет привести игру, изображенную на рис.3.15, к следующей (рис. 3.17):

Рис.3.17. Игра "Выборы с правом вето" после выбора доминирующих стратегий игроком 3

Поскольку в новом дереве игрок 3 уже по существу не принимает решения, то финальная вершина определяется ходами игрока 2. Игрок 1, зная функцию выигрышей U₂, может предвидеть поведение игрока 2. В итоге получается игра с одним участником – первым игроком и следующим деревом игры (рис. 3.18):

Поскольку для первого игрока желательна победа четвертого претендента, то он отклонит третьего претендента. Далее второй игрок вынужден будет отклонить второго претендента, а третий игрок – первого. Выигрыши игроков в данной игре равны 7, 4 и 4 соответственно.

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

Рис.3.18. Использование теоремы Куна в игре с полной информацией

3.4.4. Нормализация позиционной игры

Процесс сведения позиционной игры к игре в нормальной форме называют нормализацией игры. Любая позиционная игра может быть сведена к игре в нормальной форме, в которой каждый из игроков делает только по одному независимому ходу. Для нормализации игры нужно перечислить все возможные стратегии игроков и для каждой совокупности стратегий определить выигрыш игроков. Рассмотрим процесс нормализации позиционной игры на конкретном примере антагонистической игры. Пусть игра задана деревом, изображённом на рис.3.19.

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

В данной игре у первого игрока (игрока А) имеется две чистых стратегии: Ф₁=A₁, A₂, где стратегия A₁ – всегда выбирать левую ветвь; стратегия A₂ – всегда выбирать правую ветвь. Второй игрок (игрок В) имеет больше стратегий:

Ф₂=В₁,В₂,В₃,В₄,

где стратегия В₁ – всегда выбирать левую ветвь;

стратегия В₂ – всегда выбирать правую ветвь;

стратегия В₃ – выбирать ветвь, которую выбрал игрок А;

стратегия В₄ – выбирать ветвь, противоположную той, которую выбрал игрок А.

Рис. 3.19. Нормализация позиционной игры с полной информацией

Матрица игры в этом случае имеет вид

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

Действительно, так как

;

,

то .

Поэтому S_A=||1,0|| или S_A=||0,1||, а S_B=||0,0,0,1||. Цена игры .

Допустим, что в рассматриваемом примере второму игроку не сообщается выбор, сделанный первым игроком. Тогда в дереве игры на втором ходе появляется класс информации V₁, содержащий две вершины второго игрока (рис.3.20).

Рис. 3.20. Нормализация позиционной игры с неполной информацией

Количество чистых стратегий второго игрока по сравнению с первым случаем сократится до двух:

Ф₂=В₁,В₂,

где В₁ – всегда выбирать левую ветвь;

В₂ – всегда выбирать правую ветвь.

Процесс нормализации приводит к следующей платежной матрице:

В новой игре   , т.е. седловая точка отсутствует. Решение игры в смешанных стратегиях имеет вид

.

Уменьшение информации, имеющейся у второго игрока на момент принятия решения, привело к уменьшению его выигрыша с 2 до проигрыша .

Итак, для нормализации позиционной игры необходимо:

• перечислить все возможные стратегии каждого из игроков;

• определить исходы игры при всех возможных сочетаниях стратегий игроков (выборы стратегий делаются игроками одновременно и независимо).

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