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

Обозначим через G (Х, Y,А) игру двух лиц с нулевой суммой, в которой игрок А выбирает стратегию Х Î Х, игрок В – Y Î U, после чего игрок А получает выигрыш А = А (Х, y) за счёт игрока В.

Определение. Стратегия х1 игрока А доминирует (строго доминирует) над стратегией Х2, если

А(х1, y) ³ А(х2, y) (А(х1, y) > А(х2, y)), y Î U.

Стратегия Y1 игрока В доминирует (строго доминирует) над стратегией Y2, если

А(х, y1) £ А(х, y2) (А(х, y1) < А(х, y2)), х Î Х.

При этом стратегии х2 и y2 называются доминируемыми (строго доминируемыми).

Спектром смешанной стратегии игрока в конечной антагонистической игре называется множество всех его чистых стратегий, вероятность которых согласно этой стратегии положительна.

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

Свойство 2. Ни одна строго доминируемая чистая стратегия игрока не содержится в спектре его оптимальной стратегии.

Игра G¢ = (Х¢,Y¢,А¢) называется подыгрой игры G (Х, Y,А), если Х¢Ì Х, U¢Ì U, а матрица А¢ является подматрицей матрицы А. Матрица А¢ при этом строится следующим образом. В матрице А остаются строки и столбцы, соответствующие стратегиям Х¢ и U¢, а остальные “вычеркиваются”. Всё то что “останется” после этого в матрице А и будет матрицей А¢.

Свойство 3. Пусть G = (Х, Y,А) – конечная антагонистическая игра, G¢ = (Х \ х¢,Y, А) – подыгра игры G, а Х¢ – чистая стратегия игрока 1 в игре G, доминируемая некоторой стратегией , спектр которой не содержит Х¢. Тогда всякое решение (Хо, yо, U) игры G¢ является решением игры G.

Свойство 4. Пусть G = (Х, Y,А) – конечная антагонистическая игра, G¢ = (Х, Y \ y¢,А) – подыгра игры G, а Y¢ – чистая стратегия игрока 2 в игре G, доминируемая некоторой стратегией , спектр которой не содержит Y¢.Тогда всякое решение игры G¢ Является решением G.

Свойство 5. Если для чистой стратегии Х¢ игрока 1 выполнены условия свойства 3, а для чистой стратегии Y¢ игрока 2 выполнены условия свойства 4, то всякое решение игры G¢ = (Х \ Х¢,Y \ y¢,А) является решением игры G = (Х, Y,А).

Свойство 6. Тройка (Хо, yо, U) является решением игры G = (Х, Y,А) тогда и только тогда, когда (Хо, yо, кU +а) является решением игры G(Х, Y,кА+а), где А – любое вещественное число, К > 0.

Свойство 7. Для того, чтобы Хо = () была оптимальной смешанной стратегией игрока А в матричной игре с матрицей А и ценой игры U, необходимо и достаточно выполнение следующих неравенств

(j = )

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

(I = )

Из последнего свойства вытекает: чтобы установить, является ли предполагаемые (Х, y) и U решением матричной игры, достаточно проверить, удовлетворяют ли они неравенствам (*) и (**). С другой стороны, найдя неотрицательные решения неравенств (*) и (**) совместно со следующими уравнениями

Получим решение матричной игры.

Таким образом, решение матричной игры сводится к нахождению неотрицательных параметров решений линейных неравенств (*) (**) и линейных уравнений (***). Однако это требует большого объёма вычислений, которое растёт с увеличением числа чистых стратегий игроков. (Например, для матрицы 33 имеем систему из 6 неравенств и 2 уравнений). Поэтому в первую очередь следует, по возможности используя свойства 2 и 3, уменьшить число чистых стратегий игроков. Затем следует во всех случаях проверить выполнение неравенства

= .

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

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

Пример 3. Пусть G = (Х, Y,А), где Х = {1, 2, 3, 4}; Y = {1, 2, 3, 4}, а функция выигрыша А задана следующим образом :

Где С > 0.

Решение. Прежде всего заметим, что по свойству 6 достаточно решить игру G1 = (Х, Y,А), где А1 =А . В матричной форме игра G1 определяется матрицей выигрышей

Элементы четвёртой строки этой матрицы “ £ ” соответствующих элементов третьей строки и поэтому третья стратегия игрока А доминирует над четвёртой. Кроме того, элементы первого столбца матрицы А1 “ ³ ” соответствующих элементов второго столбца, Следовательно, вторая стратегия игрока В доминирует над его первой стратегией.

Далее, из свойства 5 следует, что всякое решение игры G2 = (Х \ {4}, Y \ {1}, А1) является решением игры G1. В матричной форме игру G2 можно представить матрицей

Очевидно, что элементы второй строки “ ³” полусуммы соответствующих элементов первой и третьей строк. Кроме того, элементы третьего столбца матрицы А2 “ ³“ соответствующих элементов второго столбца. Применяя свойство 5 получим, что всякое решение игры G3 = (Х \ {4,2}, Y \ {1,4}, А2) является решением игры G2, а следовательно и игры G1. Игра G3 определяется матрицей

Матрица А3 Не имеет седловой точки, т. к. не выполнено равенство

= ,

А игра G3 не имеет решения в чистых стратегиях, т. е. оптимальные стратегии игроков являются смешанными. Эти стратегии (в данном случае) легко найти из анализа структуры матрицы А3. Поскольку матрица А3 Симметрична, можно предположить, что игроки в оптимальной стратегии используют свои чистые стратегии с равными вероятностями.

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

Либо

Аналогично, если игрок В использует свои чистые стратегии 2 и 3 с равными вероятностями, то математическое ожидание его проигрыша будет равно . Следовательно, указанные стратегии являются оптимальными в игре G3, а величины – значением игры G3. Из предыдущего следует, что эти стратегии оптимальны и в G1.

Таким образом, стратегия Х = (, 0,, 0) является оптимальной стратегией игрока А, стратегия Y = (0,,, 0) – оптимальной стратегией игрока В в игре G1, а значение игры G1 равно . В силу свойства 4 решением игры G будет тройка (Х, Y,).

< Предыдущая		Следующая >