Понятие о матричных играх со смешанными стратегиями

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

Рассмотрим, например, игру:

 

В этой игре и . Следовательно, первый игрок может гарантировать себе выигрыш, равный 4, а второй может ограничить свой проигрыш 5. Область между и является как бы ничейной и каждый игрок может попытаться улучшить свой результат за счет этой области. Каковы же должны быть в этом случае оптимальные стратегии игроков?

Если каждый из игроков применяет отмеченную звездочкой стратегию ( и ), то выигрыш первого игрока и проигрыш второго будут равны 5. Это невыгодно второму игроку, так как первый выигрывает больше, чем он может себе гарантировать. Однако если второй игрок каким-либо образом раскроет замысел первого о намерении использовать стратегию , то он может применить стратегию и уменьшить выигрыш первого до 4. Правда, если первый игрок раскроет замысел второго применить стратегию , то, используя стратегию , он увеличит свой выигрыш до 6. Таким образом, возникает ситуация, когда каждый игрок должен хранить в секрете ту стратегию, которую он собирается использовать. Однако, как это сделать? Ведь если партия играется многократно и второй игрок применяет все время стратегию , то первый игрок скоро разгадает замысел второго и, применив стратегию , будет иметь добавочный выигрыш. Очевидно, что второй игрок должен менять стратегию в каждой новой партии, но делать это он должен так, чтобы первый не догадался, какую стратегию применит он в каждом случае.

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

 

Для механизма случайного выбора выигрыши и проигрыши игроков будут случайными величинами. Результат игры в этом случае можно оценить средней величиной проигрыша второго игрока. Вернемся к примеру. Так, если второй игрок использует стратегию и случайным образом с вероятностями 0.5; 0.5, то при стратегии первого игрока среднее значение его проигрыша будет:

 

а при стратегии первого игрока

 

.

 

Следовательно, второй игрок может ограничить свой средний проигрыш значением 4,5 независимо от стратегии, применяемой первым игроком.

Стратегию, основанную на случайном выборе, называют смешанной стратегией.

Смешанной стратегией игрока называется полный набор вероятностей применения его чистых стратегий.

Стратегии, применённые с вероятностью, отличной от нуля, называются активными стратегиями.

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

Аналогично для игрока 2. Обозначим через вероятности, с которыми он использует свои чистые стратегии . Смешанная стратегия для игрока 2 – набор чисел , удовлетворяющих соотношениям

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

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

При этом условии величина v называется ценой игры. Если  – оптимальная стратегия первого игрока, а  – оптимальная стратегия второго игрока, то число

 

является ценой игры.

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

Доказано, что всякая матричная игра с нулевой суммой имеет решение в смешанных стратегиях. Для того чтобы число v было ценой игры, а  и  оптимальными стратегиями необходимо и достаточно выполнение неравенств

 



 

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