Свойства чистых и смешанных стратегий

 

Значение платежной функции при оптимальных стратегиях определяет цену игры v, т. е. .

Теорема: В смешанных стратегиях любая конечная матричная игра имеет седловую точку.

Пусть имеем матричную игру и некоторые смешанные оптимальные стратегии , игроков А и В, обеспечивающие сумму выигрыша v. Вопрос поставим так: как проверить, что набор является решением игры? Для этого нужно проверить справедливость неравенства для любых смешанных стратегий, среди которых и будут стратегии , . Однако, различных смешанных стратегий, среди которых и оптимальные, имеем бесчисленное множество. И в таком случае проверить справедливость этого неравенства невозможно. Поэтому рассмотрим следующую теорему, которая позволит ответить на поставленный выше вопрос.

Теорема: Для того чтобы смешанные стратегии и были оптимальными для игроков А и В в игре с матрицей и выигрышем v, необходимо и достаточно выполнения неравенств:

(3.5)

(3.4)

,

.

На основании данной теоремы можно сделать вывод: если игрок А применяет оптимальную смешанную страте­гию , а игрок В – любую чистую стратегию В_j, то выигрыш игрока А будет не меньше цены игры v. Аналогично: если игрок В использует оптимальную смешанную стратегию , а игрок А – любую чистую стратегию A_i, то проигрыш игрока В не превысит цены игры v.

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

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

На основании данной теоремы решение матричной игры можно упростить, выявив при этом доминирование одних стратегий над другими. Так, рассматривая стратегии игрока А, сравниваем элементы строк s и t, а именно: с элементами а_tj для . Если , то выигрыш игрока А при стратегии А_s будет больше, чем при стратегии A_t. В этом случае стратегия А_s доминирует над стратегией A_t. Стратегию А_s называют доминирующей, а стратегию A_t — доминируемой.

Поскольку игрок В заинтересован в минимизации проигрыша, доминирующим будет столбец с наименьшими элементами. Например, сравниваем элементы r-гo и l-го столбцов. Если все элементы , то игроку В свой выбор выгодно сделать по l-му столбцу. В этом случае стратегия В_l игрока В доминирует над стратегией В_r. Стратегия В_l называется доминирующей, а стратегия В_r — доминируемой.

Если в матричной игре имеем строки (столбцы) с одними и теми же элементами, то строки (столбцы), а соответственно и стратегии игроков А и В, называются дублирующими.

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

Теорема: Оптимальные смешанные стратегии и соответственно игроков А и В в матричной игре с ценой v будут оптимальными и в матричной игре с ценой , где .

На основании данной теоремы платежную матрицу, имеющую отрицательные числа, можно преобразовать в матрицу с положительными числами.

Пример: Выполнить всевозможные упрощения матричной игры

Решение.

Поскольку соответствующие элементы второй и четвертой строк матрицы игры равны, т. е. имеем две дублирующие строки, опустим, например, четвертую строку.

Сравним соответствующие элементы столбцов. Элементы первого столбца доминируют над элементами третьего и шестого столбцов, а элементы второго столбца доминируют над соответствующими элементами четвертого столбца. Игроку В невыгодно применять стратегии В₃, B₄ и В₆. Опускаем третий, четвертый и шестой столбцы и получаем матрицу вида

Элементы второй строки меньше соответствующих элементов третьей строки. Следовательно, игроку А невыгодна стратегия А₂. Опуская вторую строку, получаем упрощенную матрицу

Если требуется получить матрицу с положительными элементами, то достаточно прибавить к ее элементам, например, число 2.

На примере покажем один из методов нахождения решения игры, заданной матрицей.

Пример: Найти решение игры, заданной матрицей

Решение.

Проверим наличие седловых точек. Найдем минимальные элементы в каждой из строк (2; 4) и максимальные в каждом из столбцов (6; 5). Значит, нижняя цена игры α=max(2; 4)=4 и β=min(6;5)=5. Так как α≠β, то решением игры являются смешанные оптимальные стратегии, а цена игры заключается в пределах от 4 до 5.

Предположим, что для игрока А стратегия задается вектором . Тогда средний выигрыш при первой и второй стратегии будет равен:

,

.

Вероятность выбора той или иной стратегии равна 1, т.е.

.

Получим систему из трех уравнений с тремя неизвестными. Решив ее получим , и .

Построим геометрическую иллюстрацию данного метода решения.

Откладываем на оси 0u единичный отрезок. Строим линию параллельно оси 0z. Строим прямые через точки (2; 6) и (5; 4). Линии пересекаются в точке М.

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

Ответ: , и .

Обобщая изложенные выше результаты нахождения решения игры , можно указать основные этапы нахождения решения игры или .

1. Строим прямые, соответствующие стратегиям одного игрока.

2. Определяем нижнюю (верхнюю) границу выигрыша.

3. Находят две стратегии этого игрока, которым соответствуют две прямые, пересекающиеся в точке с максимальной (минимальной) координатой.

4. Определяем цену игры и оптимальные стратегии.