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

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

Определение 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. Таким образом, получаем цену исходной игры: .

3.3.7. Решение игр 2´ n и m´ 2

Как уже отмечалось в теореме об активных стратегиях, любая конечная игра m ´ n имеет решение, в котором число активных стратегий каждого игрока не превосходит , где . Следовательно, у игры 2´ n или m ´ 2 всегда имеется оптимальное решение содержащее не более двух
активных стратегий у каждого из игроков
= . Если эти активные стратегии игроков будут найдены, то игры 2´ n и m ´ 2 превращаются в игры 2´ 2, методы решения которых рассмотрены выше.

Практически решение игры 2´ n осуществляется следующим образом:

1) строится графическое изображение игры для игрока А;

2) выделяется нижняя граница выигрыша и находится наибольшая ордината нижней границы (максимин), которая равна цене игры n;

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

Таким образом, игра 2´ n сведена к игре 2´ 2, которую более точно можно решить алгебраическим методом.

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

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

Пример. Найти решение игры, платёжная матрица которой имеет вид:

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

Рис. 3.11. Графическое изображение игры для игрока А

Точка N (максимин) является точкой оптимума. В этой точке пересекаются линии, соответствующие активным стратегиям B ₁ и B ₂ игрока B.

Таким образом, исключая стратегию B ₃, получаем матричную игру 2x2 с платёжной матрицей вида

Используя алгебраический метод решения этой игры, получаем точное решение

; ;

; ;

.

Ответ: ; ; .

Пример. Найти решение игры, платёжная матрица которой имеет вид

Платёжная матрица не имеет седловой точки. Для сведения данной игры к игре 2´ 2 строим её графическое изображение для игрока В (рис. 3.12).

Рис.3.12. Графическое изображение игры для игрока В

Точка М (минимакс) является точкой оптимума. В этой точке пересекаются отрезки, соответствующие активным стратегиям А ₂, А ₆ и А ₃ игрока А. Таким образом, исключая стратегии А ₁, А ₄ и А ₅ и выбирая из трех активных стратегий две (например, А ₂ и А ₃ или А ₂ и А ₆), приходим к матричной игре 2´ 2. Выбор стратегий А ₃ и А ₆ исключен, так как в этом случае точка М перестанет быть точкой минимакса.

Пусть выбираются стратегии А ₂ и А ₃. Тогда игра 2´ 2 приобретает вид

Оптимальные смешанные стратегии данной игры, а, следовательно, и исходной игры определяются следующими вероятностями:

; ;

; ;

.

Ответ: ; ; .

Другой вариант игры 2´ 2 получается, если использовать стратегии А ₂ и А ₆. В этом случае платёжная матрица имеет вид

Тогда

; ;

; ;

.

Ответ: ; ; .

Естественно, что цена игры для обоих вариантов способов решения задачи одинакова.

В заключение наметим общую схему решения матричных игр 2´ n и m ´ 2:

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

2. Производится упрощение матричной игры путем исключения дублирующих и доминируемых стратегий. Если упрощенная игра имеет размерность не 2´ 2, то переходим к этапу 3.

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

4. Решается матричная игра 2´ 2.

3.3.8. Решение игр m´ n. Эквивалентные задачи линейного программирования

Пусть имеется матричная игра m ´ n без седловой точки с матрицей выигрышей . Допустим, что все выигрыши a_ij положительны (этого всегда можно добиться, прибавляя ко всем элементам матрицы достаточно большое число С; от этого, как уже отмечалось, цена игры увеличится на C, а оптимальные решения S_A и S_B не изменятся).

Если все aij положительны, то и цена игры при оптимальной стратегии тоже положительна, т.к. .

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

Найдем вначале S_A. Для этого предположим, что игрок В отказался от своей оптимальной смешанной стратегии S_B и применяет только чистые стратегии. В каждом из этих случаев выигрыш игрока А будет не меньше, чем :

. (3.25)

Разделив левую и правую часть каждого из неравенств (3.25) на положительную величину n и введя обозначения:

, (3.26)

запишем неравенства (3.25) в следующем виде:

, (3.27)

где x ₁, x ₂,... x_m – неотрицательные переменные.

В силу того, что

,

переменные x ₁, x ₂,... x _mудовлетворяют условию

. (3.28)

Учитывая, что игрок А стремится максимизировать n, получаем следующую задачу линейного программирования: найти неотрицательные значения переменных x ₁, x ₂,... x _mтакие, чтобы они удовлетворяли линейным ограничениям – неравенствам (3.27) и обращали в минимум линейную функцию этих переменных:

. (3.29)

Из решения задачи линейного программирования находим цену игры n и оптимальную стратегию S _Aпо формулам:

, (3.30)

, . (3.31)

Аналогично находим оптимальную стратегию S _Bигрока В. Предположим, что игрок А отказался от своей оптимальной стратегии S _Aи применяет только чистые стратегии. Тогда проигрыш игрока В в каждом из этих случаев будет не больше, чем :

. (3.32)

Разделив левую и правую части каждого их неравенств (3.32) на положительную величину n и введя обозначения:

, (3.33)

запишем неравенство (2.32) в следующем виде:

, (3.34)

где y ₁, y ₂,..., y_n – неотрицательные переменные.

В силу того, что , переменные y ₁, y ₂,..., y _nудовлетворяют условию

. (3.35)

Учитывая, что игрок В стремится минимизировать положительную цену n (свой проигрыш), получаем задачу линейного программирования: найти неотрицательные значения переменных y ₁, y ₂,..., y_n такие, чтобы они удовлетворяли линейным ограничениям (3.34) и обращали в максимум линейную функцию этих переменных:

. (3.36)

Эта задача является двойственной по отношению к задаче, представленной условиями (3.27) и (3.29).

Оптимальная стратегия игрока В определяется из решения двойственной задачи линейного программирования по формулам:

, . (3.37)

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

Таким образом, оптимальные стратегии и матричной игры m ´ n с платёжной матрицей могут быть найдены путем решения пары двойственных задач линейного программирования:

Прямая (исходная) задача	Двойственная задача
, , ; , .	, , ; , .

При этом

, (3.38)

Пример. Найти решение и цену матричной игры, платёжная матрица которой имеет вид