Смешанные стратегии матричных игр.

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

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

Таблица 4.4.

  Минимальные выигрыши игрока А
-2 -3 -3 -3 -2 -3
Максимальные выигрыши игрока А  

 

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

Обратимся к общему случаю матричной игры, представленной в табл. 4.2. Обозначим через вероятности, с которыми игрок А использует в ходе игры свои чистые стратегии . Для этих вероятностей выполняются условия

(4.7)

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

Аналогично, вектор , проекция которого удовлетворяет условиям (4.8),

(4.8)

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

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

. (4.9)

Функция (4.9) называется платежной функцией игры с матрицей, заданной в табл. 4.5.

Нижней ценой игры называется число , рассчитываемое по формуле:

. (4.10)

Верхней ценой игры называется число , рассчитываемое по формуле:

. (4.11)

Таблица 4.5.

  Вероятности использования чистых стратегий игроком А
Вероятности использования чистых стратегий игроком В  

 

Оптимальными смешанными стратегиями называются стратегии, удовлетворяющие соотношению (сравнить с формулой (4.6)).

. (4.12)

Величину

,

определенную соотношением (4.12), называют ценой игры.

Дадим другое определение оптимальных смешанных стратегий.

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

. (4.13)

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

1. Какие матричные игры имеют решение в смешанных стратегиях?

2. Как находить решение матричной игры, если оно существует?

Ответы на данные вопросы дают две следующие теоремы.

Теорема 4.1. Основная теорема теории матричных игр. (Дж. фон Нейман). Для матричной игры с любой матрицей А величины и существуют и равны между собой:

.

Более того, существует хотя бы одна ситуация в смешанных стратегиях , для которой выполняется соотношение

.

Теорема 4.2. Основные свойства оптимальных смешанных стратегий.Пусть

, - оптимальные смешанные стратегии и - цена игры.

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

.

Аналогично, только те вероятности , могут отличаться от нуля, для которых

.

Имеют место соотношения

Рассмотрим методы решения некоторых матричных игр.