Упрощение матричных игр

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

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

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

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

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

Bj   Ai	B1	B2	B3	B4	B5
A1
A2
A3
A4
A5

Из платежной матрицы видно, что стратегия А₂ дублирует стратегию А₅, потому любую из них можно отбросить (отбросим стратегию А₅). Сравнивая почленно стратегии А₁ и А₄, видим, что каждый элемент строки А₄ не больше соответствующего элемента строки А₁. Поэтому применение игроком А доминирующей над А₄ стратегии А₁ всегда обеспечивает выигрыш, не меньший того, который был бы получен при применении стратегии А₄. Следовательно, стратегию А₄ можно отбросить. Таким образом, имеем упрощенную матричную игру с платежной матрицей вида:

Bj   Ai	B1	B2	B3	B4	B5
A1
A2
A3

Из этой матрицы видно, что в ней некоторые стратегии игрока В доминируют над другими: В₃ над В₂, В₄ и В₅. Отбрасывая доминируемые стратегии В₂, В₄ и В₅, получаем игру 3x2, имеющей платежную матрицу вида:

Bj   Ai	B1	B3
A1
A2
A3

В этой матрице стратегия А₃ доминируется как стратегией А₁, так и стратегией А₂. Отбрасывая стратегию А₃, окончательно получаем игру 2x2 с платежной матрицей

Bj   Ai	B1	B3
A1
A2

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

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

Дата добавления: 2014-01-07