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

 

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

Рассмотрим платежную матрицу .

В матрице P i-я строка

не больше строки s этой матрицы

если одновременно выполняются следующие n неравенств:

, , …, . (7.19)

Строку s называют доминирующей, а строку i доминируемой. При этом говорят также, что s-я строка доминирует i-ю строку или что стратегия As игрока А доминирует стратегию Ai.

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

В матрице P j-й столбец

не меньше столбца r этой матрицы

если одновременно выполняются следующие m неравенств:

, , …, . (7.20)

Столбец r называют доминирующим, а столбец j доминируемым.

При этом говорят также, что столбец r доминирует столбец j или что стратегия Br игрока B доминирует стратегию Bj.

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

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

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

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