7.4. Смешанные стратегии
Наличие у игры седловой точки вынуждает обоих игроков обязательно реализовывать только одну из чистых стратегий. Но, как уже отмечалось выше, далеко не каждая игра ее имеет. В таком случае невозможно дать какие-либо содержательные рекомендации по такому вопросу, как следует поступать участникам однократно проводимой игры. Однако принципиально отличной является ситуация, когда игра становится многократно повторяющимся процессом. Появляется возможность реализовать принцип рандомизации, т.е. внести в процесс выбора элемент случайности или фактор вероятности. В таких условиях применяется принцип смешанных стратегий. Рассмотрим его на следующем примере.
Предположим,
имеется игра, заданная матрицей:
.
Для нее αmax=2, βmin=4, т.е. игра не имеет седловой точки. Предположим, что игроки сыграли 10 игровых циклов, причем игрок А использовал за этот период чистые стратегии: первую - 3 раза, вторую - 5 раз, третью -2 раза. Второй игрок В за этот же период использовал свои чистые стратегии: первую – 2 раза, вторую -3 раза, третью – 1 раз, четвертую – 4 раза. В таком случае говорят, что игроки использовали смешанные стратегии, которые записываются в виде вектор-строки (в принятых обозначениях):
смешанная
стратегия первого игрока - 
,
смешанная
стратегия второго игрока - 
.
Смешанной
стратегией игрока (например, А )в игре
с матрицей 
называется
упорядоченный набор действительных
чисел ui
(i=1…m),
удовлетворяющих условиям
ui
> 0,
.
Числа, составляющие вектор-строку смешанной стратегии, интерпретируются как относительные частоты или вероятности применения игроком соответствующей чистой стратегии. Аналогично для игрока В смешанная стратегия будет записана так:
zj
> 0,
j=1…n,
.
К поиску решения игры в смешанных стратегиях, так же как и при наличии седловой точки, могут быть применены критерии максимина-минимакса. В соответствии с ними игрок А будет выбирать свою смешанную стратегию таким образом, чтобы максимизировать наименьший средний выигрыш, а игрок В – минимизировать свой максимальный проигрыш. Если u* - оптимальная смешанная стратегия первого игрока, а z* - оптимальная смешанная стратегия второго игрока, то число
(26)
является ценой игры. С точки зрения математической статистики, это средневзвешенное (или, точнее, математическое ожидание) матрицы игры за все игровые циклы.
Т е о р е м а 1. Для любой матричной игры в смешанных стратегиях действительно соотношение:
,
т.е. цена игры не менее максимина, но и не более минимакса.
Определение оптимальных стратегий и цены игры и составляет сущность процесса нахождения решения игры.
З а д а ч а 16. Рассчитать цену игры, заданную матрицей
,
из предположения, что игроки имеют оптимальные смешанные стратегии u*=(0,3; 0,3; 0,4), z*=( 0,2; 0,5; 0,3).
Р е ш е н и е . Определим максимин и минимакс игры. Для этого выпишем вектор-строку минимальных выигрышей игрока А и максимальных проигрышей игрока В: α=(2; 3; 2), β=(5; 5; 4). Тогда максимин равен αmax =3, минимакс равен βmin=4. Следовательно, цена игры будет находиться между числами 3 и 4. Рассчитаем ее, воспользовавшись выражением ( 26 ).
.
Получили ответ – цена игры равна 3,63, что соответствует теоретическим представлениям.
Справедлива фундаментальная теорема Дж.Неймана, которую приведем без доказательства.
Т е о р е м а 2 (основная теорема матричных игр). Любая матричная игра имеет решение в смешанных стратегиях.
Значение и нетривиальность теоремы обусловлены тем, что в общем случае матричные игры в чистых стратегиях решения не имеют.
Т е о р е м а 3. Для того, чтобы число v было ценой игры, а u* и z* - оптимальными стратегиями, необходимо и достаточно выполнение неравенства:
;
(j=1…n);
;
(i=1…m).
Эта теорема определяет, что, соблюдая оптимальные смешанные стратегии, первый игрок может выиграть не менее цены игры, а второй игрок имеет шанс проиграть не более цены игры.
Т е о р е м а 4. Если один из игроков применяет оптимальную смешанную стратегию, то его выигрыш (или проигрыш второго) равен цене игры v независимо от того, с какими частотами будет применять второй игрок стратегии, вошедшие в оптимальную (в том числе и чистые стратегии).
Она важна тем, что позволяет выработать методику решения игры для игр 2×2, 2×n, m×2.
Рассмотрим возможность приложения приведенных выше теорем для решения парной игры типа 2×2 аналитическим методом.
З а д а ч а 17. Найти решение игры, заданной матрицей
.
Р
е ш е н и е. В данной задаче имеем две
стратегии первого игрока, т.е. m=2,
и две стратегии
второго игрока, т.е. n=2.
Прежде всего проверим, возможность
наличия седловой точки в данной игре.
Для этого выпишем минимальные выигрыши
первого игрока по двум чистым стратегиям
(по строкам) α=(2;
4) и максимальные
проигрыши второго игрока также по его
двум чистым стратегиям (по столбцам)
β=(6; 5).
Из этих векторов выпишем макcимин
для первого игрока αmax=4,
минимакс
для второго игрока βmin=5.
Так как они не равны, то решение следует
искать в смешанных стратегиях, а цена
игры должна быть в пределах 
.
Предположим, что для игрока А стратегия задается вектором u=(u1; u2), а для игрока В – вектором z=(z1; z2). Тогда, на основании теоремы 4, при применении игроком В чистой стратегии z1 или z2 игрок А получит средний выигрыш, равный цене игры v , т.е.
(при
стратегии z1),
(при
стратегии z2).
Помимо двух записанных уравнений относительно u1* и u2* добавим уравнение, связывающее их как частоты:
.
Решая полученную систему трех уравнений с тремя неизвестными, находим
;
; 
.
Найдем теперь оптимальную стратегию для игрока В. В отношении его можно составить следующую систему уравнений:
(при
стратегии u1),
(при
стратегии u2),
.
Здесь имеются три уравнения, а неизвестных два, т.е. одно из уравнений уже лишнее. Решая систему, получаем
;
.
Следовательно, решением задачи будут смешанные стратегии при цене игры:
;
;
.
Результаты полностью согласуются с теоретическими предпосылками.