Матричные игры без седловой точки

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

Введем понятие смешанной стратегии. Смешанная стратегия – комбинация чистых стратегий с вероятностями выбора :

; .

Оптимальная смешанная стратегия: .

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

будет в интервале (для участника это проигрыш ).

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

для – из условия ,

– цена игры.

Доказательство теоремы будет рассмотрено далее.

Определение 2 (активные стратегии). Активные стратегии для участника – это те стратегии из множества чистых , для которых .

Утверждение 1. Если участник придерживается оптимальной смешанной стратегии, то его выигрыш не зависит от стратегии участника в пределах активных стратегий участника .

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

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

. (2.1)

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

Запишем (2.1) с учетом этого неравенства:

С учетом, что получаем нестрогое неравенство . Но так как участник B осуществляет выбор на множестве активных стратегий, а – оптимальная стратегия для A, то не может быть больше . Следовательно .

2.3.1. Решение матричных игр 2´2

Каждый из участников имеет по две чистые стратегии. Матрица выигрышей для A имеет вид:

Элементы матрицы таковы, что , т.е. седловой точки нет.

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

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

Учитывая, что :

Откуда получим

, (2.2)

. (2.3)

Для определения также составим уравнение:

;

; (2.4)

. (2.5)

Цена игры (выигрыш для участника) будет равна:

Для того чтобы решения (2.2), (2.3), (2.4), (2.5) были положительными числами (вероятностями), необходимо, чтобы для элементов матрицы выполнялись следующие неравенства:

или .

Пример задачи. Правила игры. Каждый из участников имеет две чистые стратегии:

– выбрать число 1,

– выбрать число 2.

Если сумма у двух участников окажется четным числом, то выигрыш составит эту сумму. Если же сумма окажется нечетной, то выигрывает участник .

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

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

Для участника решением будет:

Цена игры равна:

Поскольку , выигрывает участник В; из этого можно сделать вывод, что правила игры несправедливы.

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

Графическая интерпретация решения игры 2´2. Построим зависимость выигрыша участника от (рис. 2.1),

где – выигрыш участника А, если участник придерживается чистой стратегии , – если участник придерживается чистой стратегии .

Приравняв g ₁ и g ₂, получим оптимальное значение , которое соответствует , т.е. максимизировал свой выигрыш.

Теперь рассмотрим решение игры с позиции участника . Построим зависимость его проигрыша от (рис. 2.2),

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

Оптимальное значение получается из условия , т.е. он минимизирует проигрыш.

2.3.2. Решение матричных игр 2´m графоаналитическим методом

Если участник имеет 2 чистые стратегии, а – чистых стратегий, то матрица выигрышей для имеет вид:

Построим зависимость выигрыша участника от при чистых стратегиях участника:

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

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

Пример. Дана платежная матрица, необходимо найти оптимальные смешанные стратегии: