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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Эти два свойства матричных игр применяются в следующих случаях:

1) если матрица игры наряду с положительными имеет и отрицательные элементы, то ко всем её элементам прибавляют такое число, чтобы исключить отрицательные числа в матрице;

2) если матрица игры имеет дробные числа, то для удобства вычислений элементы этой матрицы следует умножить на такое число, чтобы все выигрыши были целыми числами.

Пример. Решить матричную игру 22 с платёжной матрицей вида:

Умножая все элементы платёжной матрицы на 10, а затем прибавляя к ним число 2, получаем игру с платёжной матрицей

Решая эту игру алгебраическим методом, получаем

; ;

; ;

.

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