Графический метод решения матричных игр

Лекция 4 (ММвТУиИО) ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ МАТРИЧНЫХ ИГР (ЧАСТЬ 2) Игры m x 2 Пусть теперь в матричной игре две чистые стратегии имеет игрок В, а число чистых стратегий у игрока А произвольно (равно m). Это означает, что платежная матрица такой игры имеет следующий вид: 𝑎11 𝑎12 𝑎21 𝑎22 ( … … ) 𝑎𝑚1 𝑎𝑚2 Анализ этой игры во многом напоминает рассуждения, проведенные в Лекции №3 для игры 2 х n. Этап 1. Пусть Q = {q, 1-q} – произвольная смешанная стратегия игрока В. Этап 2. Если игрок А выбирает i-ю чистую стратегию, i=1, 2, …, m, то средний проигрыш игрока В в ситуации {i, Q} будет равен: (i) : w = ai1 * q + ai 2 * (1-q), i=1, 2, …, m Этап 3. Зависимость этого проигрыша (w) от q описывается прямой на плоскости (q, w). Этап 4. Графиком функции max (𝑎𝑖1 𝑞 + 𝑎𝑖2 (1 − 𝑞)) 1≤𝑖≤𝑚 является верхняя огибающая семейства прямых (i), соответствующих чистым стратегиям игрока А (рис. 1) w w0 q0 1 q Рис. 1 1 Лекция 4 (ММвТУиИО) Этап 5. Абсцисса q0 нижней точки полученной огибающей (ломаной) определяет оптимальную смешанную стратегию игрока В, а ордината w0 – цену игры. Этап 6. Нахождение оптимальной смешанной стратегии игрока А проводится по той же схеме (возможны несколько случаев, показанных на рис. и примерах ниже), которая использовалась для определения оптимальной смешанной стратегии игрока В в игре 2 х n, с поправкой на то, что в данном случае:  уже найдена смешанная стратегия для игрока В (см. выше);  необходимо выделить те стратегии А, которые обеспечивают достижение оптимальной цены игры, найденной при поиске решения для В. Случай А. Верхняя огибающая имеет ровно одну низшую точку (𝑝0 , 𝑤 0 ): 1) Если 𝑞0 = 0 (оптимальная стратегия игрока В – это чистая стратегия В2), то игроку A выгодно применить чистую стратегию Aj, соответствующую прямой, проходящей через точку (0, 𝑤 0 ) и имеющей наибольший положительный наклон: w Aj w0 1 q 2) Если 𝑞0 = 1 (оптимальная стратегия игрока B – чистая стратегия B1), то оптимальной для игрока A является чистая стратегия Aj, соответствующая прямой, проходящей через точку (1, 𝑤 0 ) и имеющей наибольший отрицательный наклон: 2 Лекция 4 (ММвТУиИО) w Aj w0 1 q 3) Если 0 < 𝑞0 < 1, то в низшей точке верхней огибающей пересекаются, по меньшей мере, две прямые, одна из которых Ak (соответствующая стратегии Ak игрока A) имеет положительный наклон, а другая Al – отрицательный. В этом случае оптимальная смешанная стратегия игрока A получается, если положить pk = p, pl = 1-p, pj = 0, j ≠ k,l, где p – решение уравнения ak1 * p + a1l * (1-p) = ak2 * p + al2 * (1-p) w Ak Al w0 q0 1 q Случай Б. Верхняя огибающая содержит горизонтальный участок, соответствующий чистой стратегии Аj игрока А, которая и является оптимальной для него: 3 Лекция 4 (ММвТУиИО) w Aj w0 1 q Описанная процедура может рассматриваться как некоторый аналог минимаксного подхода при отсутствии седловой точки. Пример 4.1. Пусть игра 3х2 задана следующей матрицей и требуется найти ее решение: 3 −1 (−1 3 ) 1 Решение. 1-ый шаг. Анализ игры на наличие седловой точки. Нижняя цена игры равна 0, верхняя – равна 3: седловой точки нет. Решение игры нужно искать в смешанных стратегиях. 2-ой шаг. Вычисление средних проигрышей игрока В (проводится при условии, что игрок А выбирает только чистые стратегии). Из таблицы игры 𝑞 1−𝑞 ___ ___ 3 −1 −1 3 1 получаем три уравнения: A1: 𝑤 = 3𝑞 − (1 − 𝑞 ) A2: 𝑤 = −𝑞 + 3(1 − 𝑞 ) A3 : 𝑤 = 𝑞 или после упрощения: 4 Лекция 4 (ММвТУиИО) A1: 𝑤 = 4𝑞 − 1 A2: 𝑤 = −4𝑞 + 3 A3 : 𝑤 = 𝑞 3-ий шаг. Построение верхней огибающей Строим на координатной плоскости (q, w) все прямые, уравнения которых получены на 2-м шаге (рис. 2), и находим их верхнюю огибающую. А1 w А3 1 p А2 Рис. 2 4-ый шаг. Нахождение цены игры и оптимальной смешанной стратегии игрока B. Нижняя точка верхней огибающей является точкой пересечения прямых А1 и А2. Решая систему уравнений 𝑤 = 4𝑞 − 1 { 𝑤 = −4𝑞 + 3 получаем 1 𝑞 = { 2 𝑤0 = 1 5-ый шаг. Нахождение оптимальной смешанной стратегии игрока А Полагая 𝑝10 = 𝑝, 𝑝20 = 1 − 𝑝, 𝑝30 = 0 , приравниваем два средних выигрыша игрока А (когда игрок В выбирает только свои чистые стратегии) к цене игры: 3𝑝 − (1 − 𝑝) = 1 − 𝑝 + 3(1 − 𝑝 ) = 1 и находим 5 Лекция 4 (ММвТУиИО) 1 2 Таким образом, цена игры и оптимальные смешанные стратегии игроков А и В равны: 𝑝0 = 1 1 𝑃0 = { , , 0}, 2 2 1 1 𝑄0 = { , } , 𝜈 = 1 2 2 6 Лекция 4 (ММвТУиИО) ДОМИНИРОВАНИЕ СТРАТЕГИЙ В АНТАГОНИСТИЧЕСКОЙ ИГРЕ В принципе решение любой матричной игры, как будет показано в Лекции №5, сводится к решению стандартной задачи линейного программирования и т.о. может быть найдено методами линейного программирования (этому будет посвящена Лекция №5). При этом требуемый объем вычислений напрямую зависит от числа чистых стратегий игроков (растет с его увеличением и, значит, с увеличением размеров матрицы игры). Поэтому любые приемы предварительного анализа игры, позволяющие уменьшать размеры ее платежной матрицы или еще как-то упростить эту матрицу, не нанося ущерба решению, играют на практике важную роль. В ряде случаев анализ платежной матрицы показывает, что некоторые чистые стратегии не могут внести никакого вклада в искомые оптимальные смешанные стратегии. Отбрасывание таких стратегий позволяет заменить первоначальную матрицу матрицей выигрышей меньших размеров. Рассмотрим антагонистическую матричную игру двух лиц с нулевой суммой, заданную платежной матрицей: 𝑎11 𝑎12 … 𝑎1𝑛 𝑎21 𝑎22 … 𝑎2𝑛 А=( … … … … ) 𝑎𝑚1 𝑎𝑚2 … 𝑎𝑚𝑛 1. Будем говорить, что i-я строка матрицы А 𝑎𝑖1 𝑎𝑖2 … не больше j-й строки этой матрицы 𝑎𝑗1 𝑎𝑗2 … 𝑎𝑖𝑛 𝑎𝑗𝑛 , если одновременно выполнены следующие n неравенств: 𝑎𝑖1 ≤ 𝑎𝑗1 , 𝑎𝑖2 ≤ 𝑎𝑗2 , … , 𝑎𝑖𝑛 ≤ 𝑎𝑗𝑛 При этом также говорят, что j-я строка доминирует i-ю строку или, что стратегия Aj игрока А доминирует стратегию Ai. Игрок А поступит разумно, если будет избегать стратегий, которым в матрице игры отвечают доминируемые строки. 2. Стратегия Aj игрока А дублирует стратегию Ai, если все выигрыши в j-ой строке равны соответствующим выигрышам в i-ой строке. Если в матрице А одна из строк (например, j-ая) доминирует или дублирует другую строку (например, i-ую), то число строк в матрице А можно уменьшить путем отбрасывания доминируемой / дублируемой (i-ой) строки. 3. Будем говорить, что k-ый столбец матрицы А 7 Лекция 4 (ММвТУиИО) 𝑎1𝑘 𝑎2𝑘 … 𝑎𝑚𝑘 не меньше l-го столбца этой матрицы 𝑎1𝑙 𝑎2𝑙 … 𝑎𝑚𝑙 если одновременно выполнены следующие m неравенств: 𝑎1𝑘 ≥ 𝑎1𝑙 , 𝑎2𝑘 ≥ 𝑎2𝑙 , … , 𝑎𝑚𝑘 ≥ 𝑎𝑚𝑙 При этом говорят, что l-ый столбец доминирует k-ый столбец или что стратегия Bl игрока B доминирует стратегию Bk. Игрок B поступит разумно, если будет избегать стратегий, которым в матрице игры отвечают доминируемые столбцы. 4. Стратегия Вl игрока В дублирует стратегию Bk, если все проигрыши В в l-ом столбце равны соответствующим проигрышам в k-ом столбце. Если в матрице А один из столбцов (например, l-ый) доминирует или дублирует другой столбец (например, k-ый), то число столбцов в матрице В можно уменьшить путем отбрасывания доминируемого /дублируемого (k-го) столбца. Оптимальные смешанные стратегии в игре с матрицей, полученной усечением исходной за счет доминируемых строк и столбцов, дадут оптимальное решение в исходной игре т.к.:  доминируемые чистые стратегии игроков в смешении не участвуют;  соответствующие доминируемым стратегиям вероятности следует принять равными нулю. Нужно отметить, что при отбрасывании доминируемых строк и столбцов некоторые из оптимальных стратегий могут быть потеряны. Однако цена игры при этом не изменится и по усеченной матрице может быть найдена хотя бы одна пара оптимальных смешанных стратегий. Пример 4.2. Рассмотрим игру с матрицей 4 7 2 3 4 3 5 6 8 9 4 4 2 2 8 3 6 1 2 4 (3 5 6 8 9) Стратегия А5 дублирует стратегию А2, поэтому любую из них можно отбросить. Сравнивая, далее, А1 и А4 видим, что А1 доминирует над стратегией А4 и А4 можно отбросить. Отбросив стратегии А5 и А4 получаем игру 3х5: 8 Лекция 4 (ММвТУиИО) 4 7 2 3 4 ( 3 5 6 8 9) 4 4 2 2 8 Рассматривая полученную матрицу видим, что стратегия В1 доминирует над стратегией В2. Кроме того, стратегия В3 доминирует над стратегиями В4 и В5. Отбрасывая доминируемые стратегии, получаем игру 3х2: 4 2 (3 6 ) 4 2 Теперь видно, что стратегии А1 и А3 дублируют друг друга. Отбросив стратегию А3 окончательно получаем игру 2х2. 4 2 ( ) 3 6 Тем самым исходная игра 5х5 сводится к игре 2х2, решение которой легко находится графическим методом. Пример 4.3. Рассмотрим игру, описываемую следующей, матрицей: −1 0 2 1 −2 0 1 ( ) 2 1 −1 −2 −1 0 2 1 Сравнивая строки матрицы видим, что 1-я строка совпадает с 4-ой строкой, т.е. стратегия А4 дублирует стратегию А1 - одну из этих строк можно вычеркнуть, не нанося ущерба решению (убираем 4-ую строку): −1 0 2 1 (−2 0 1 0) 2 1 −1 −2 Сравнивая поэлементно 1-ю и 2-ю строки, замечаем, что 1-я строка доминирует 2-ю строку, т.е. стратегия А1 доминирует стратегию А2. Это также позволяет уменьшить число строк матрицы (убираем 2-ую строку): −1 0 2 1 ( ) 2 1 −1 −2 Замечая, что 4-й столбец доминирует 3-й столбец, убирая 3-ий, получаем игру с матрицей 2х3: −1 0 1 ( ) 2 1 −2 Решая эту игру графоаналитическим методом, находим ее решение – цену игры и оптимальные смешанные стратегии игроков А и В: 2 1 1 1 { , }, { , 0, } 𝜈 = 0, 3 3 2 2 Возвращаясь к исходной игре 4х4 и учитывая исключенные стратегии, получаем решение исходной игры: 9 Лекция 4 (ММвТУиИО) 𝜈 = 0, 2 1 𝑃0 = { , 0, , 0} , 3 3 1 1 𝑄0 = { , 0,0, } 2 2 10