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

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

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

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

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

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

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

Bj Ai	B1	B2	B3	B4	B5
A1	5	9	3	4	5
A2	4	7	7	9	10
A3	4	6	3	3	9
A4	4	8	3	4	5
A5	4	7	7	9	10

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

Bj Ai	B1	B2	B3	B4	B5
A1	5	9	3	4	5
A2	4	7	7	9	10
A3	4	6	3	3	9

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

Bj Ai	B1	B3
A1	5	3
A2	4	7
A3	4	3

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

Bj Ai	B1	B3
A1	5	3
A2	4	7

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

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

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

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

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

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

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

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

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

Bj Ai	B1	B2
A1	0.5	-0.2
A2	0.1	0.3

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

Bj Ai	B1	B2
A1	7	0
A2	3	5

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

; ;

; ;

.

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

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