Правило доминирования

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

– я строка платежной матрицы

доминирует – ю строку

(стратегия игрока доминирует стратегию ), если одновременно выполняются следующие неравенств:

.

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

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

–й столбец

доминирует –й столбец

,

(стратегия игрока доминирует стратегию ), если одновременно выполняются следующие неравенств:

.

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

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

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

Пример 5. Определить цену игры и оптимальные смешанные стратегии. платежную матрицу уменьшить, используя правило доминирования:

.

Решение. Сравнивая строки матрицы, видим, что 1-я строка совпадает с 4-й строкой (стратегия дублирует стратегию ). Поэтому одну из этих строк (например, 4-ю) можно вычеркнуть, не нанося ущерба решению:

Сравнивая поэлементно 1-ю и 2-ю строки, замечаем, что 1-я строка доминирует 2-ю строку (стратегия доминирует стратегию ).

Стратегию отбрасываем:

	Сравниваем столбцы. Стратегия доминирует стратегию . Стратегию можно отбросить:
В результате получаем игру ):

Решая эту игру методом нижней огибающей, находим ее решение – цену игры и оптимальные смешанные стратегии игроков и :

= , , .

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

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

Графический метод решения игр ( ).

Решение игры ( ) допускает наглядную геометрическую интерпретацию. Пусть игра задана платежной матрицей . По оси абсцисс (рис.9) отложим единичный отрезок . Точка ( ) изображает стратегию , а все промежуточные точки этого отрезка – смешанные стратегии первого игрока, причем расстояние от до правого конца отрезка – это вероятность стратегии , расстояние до левого конца – вероятность стратегии .По оси откладываем выигрыш при стратегии ,по вертикали в точке – выигрыш при стратегии .

Если 2-й игрок примет стратегию , то она дает выигрыши и , соответствующие стратегиям и . Обозначим эти точки через . Средний выигрыш , соответствующий смешанной стратегии , определяется по формуле математического ожидания и равен ординате точки , которая лежит на отрезке и имеет абсциссу (рис.9).

Аналогично строим отрезок , соответствующий применению вторым игроком стратегии (рис.10). При этом средний выигрыш – ордината точки .

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

Пример 6. Дана матрица игры:

.

Найти цену игры и оптимальные смешанные стратегии игроков и графическим способом.

Решение. Анализ игры на наличие седловой точки:

			0,3
			0,4
	0,7	0,8

Седловой точки нет. Решение игры нужно искать в смешанных стратегиях.