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

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

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

; .

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

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

,

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

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

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

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

– цена игры.

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

Определение 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). Найденному соответствуют две чистые стратегии участника , которые будут для него активными. Таким образом, игру сводим к игре .

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

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

.

Строим зависимость от :

6 g3   g1   g4 g2   0 1 1 P1a

выбираем стратегии и по

 

нове й инженерно-физический институт (государственный книверситет), 2007. принципу .

Переходим к матрице - и рассчитываем оптимальные и :

. Решением игры для участника В является:

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

Участник имеет чистых стратегий, а – 2 чистые стратегии, платежная матрица имеет вид:

.

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

.

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

2.3.4. Решение матричных игр n´m

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