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

Лекция 3 (ММвТУиИО) ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ МАТРИЧНЫХ ИГР Рассмотрение методов поиска решения матричных игр начнем с игр, в которых число стратегий, хотя бы одного из игроков равно двум. Для построения решений 2 x n- и m x 2-игр существует эффективный метод, основанный на простых геометрических построениях - графический (точнее, графо - аналитический) метод. Начнем нахождение оптимальных смешанных стратегий на примере простейшей игры, описываемой платежной матрицей 2 х 2: 𝑎11 𝑎12 А = (𝑎 (1) 𝑎22 ) 21 Пусть смешанные стратегии игроков имеют вид: Р = {p1, p2} и Q = {q1, q2} Оптимальные стратегии первого игрока (𝑝10 и 𝑝20 = 1 − 𝑝10 ) и цена игры ν должны удовлетворять условиям: { 𝑎11 𝑝10 + 𝑎21 𝑝20 =𝜈 𝑎12 𝑝10 =𝜈 + 𝑎22 𝑝20 или 𝑎11 𝑝10 + 𝑎21 (1 − 𝑝10 ) = 𝑎12 𝑝10 + 𝑎22 (1 − 𝑝10 ) Откуда получаем (аналитически!) следующее решение матричной игры (1): 𝑝10 = 𝑎22 −𝑎21 𝑎11 +𝑎22 −(𝑎12 +𝑎21 ) 𝑎11 −𝑎12 = 1 − 𝑝10 = 𝑎11 +𝑎22 −(𝑎12 +𝑎21 ) 𝑎11 𝑎22 −𝑎12 𝑎21 𝑎11 𝑝10 1 + 𝑎21 𝑝20 = 𝑎11 +𝑎22 −(𝑎12 +𝑎21 ) 𝑝20 (2) 𝜈= { Вычислив оптимальное значение ν, можно вычислить и оптимальную смешанную стратегию второго игрока из условия или 𝑎11 𝑞1 + 𝑎12 𝑞2 = 𝜈 𝑎11 𝑞1 + 𝑎12 (1 − 𝑞1 ) = 𝜈 Что дает: 𝑞10 = 𝜈−𝑎12 𝑎11 −𝑎12 , 𝑞20 = 1 − 𝑞10 = 𝑎11 −𝜈 𝑎11 −𝑎12 (3) при 𝑎11 ≠ 𝑎12 Замечание. В случае равенства 0 знаменателей в формулах (2) и (3) у игры существует решение в чистых стратегиях (наглядно это видно на графиках). Эту задачу можно решить графически, учитывая, что решение системы (1) представляет собой геометрически точку пересечения двух прямых на плоскости (p1, ν) или (1- p1, ν). 1 Лекция 3 (ММвТУиИО) Отсюда следует и простой алгоритм геометрического способа решения игры 2 х 2: 1. На оси абсцисс откладываем отрезок единичной длины 𝑝1 = 𝑝 ∈ [0, 1]. 2. На оси ординат откладываем выигрыши игрока А при стратегии А2, а на прямой р=1 – выигрыши при стратегии А1. 3. Проводим прямые, проходящие через точки: а) (0, а21) и (1, а11); б) (0, а22) и (1, а12). 4. Находим точку пересечения этих прямых, которая и дает решение матричной игры (𝑝10 , 𝜈). Данный алгоритм проиллюстрирован на рис. 1. ν a21 a12 ν a11 a22 𝒑𝟎𝟏 1 p Рис. 1 Пример 3.1. Решить матричную игру 2 х 2, заданную платежной матрицей: 3 8 ) А=( 7 4 Решение. Определим сначала верхнюю и нижнюю цену игры: B1 B2 А1 3 8 3 А2 7 4 4 8 7 Нижняя цена игры α = 4 и ей соответствует стратегия А2. Верхняя цена игры β = 7 и ей соответствуют стратегии В1. Т.к. нижняя цена игры меньше верхней (α<β), то игра не имеет седловой точки, что приводит к необходимости рассмотрения смешанной стратегии. По формулам (2) находим: 2 Лекция 3 (ММвТУиИО) 𝑎22 − 𝑎21 4−7 = = 0,375 𝑎11 + 𝑎22 − (𝑎12 + 𝑎21 ) 3 + 4 − 7 − 8 𝑝20 = 1 − 𝑝10 = 1 − 0,375 = 0,625 𝜈 = 3 ∙ 0,375 + 7 ∙ 0,625 = 5,5 По формулам (3) определим смешанную стратегию второго игрока: 𝜈 − 𝑎12 5,5 − 8 𝑞10 = = = 0,5, 𝑞20 = 1 − 𝑞10 = 0,5 𝑎11 − 𝑎12 3−8 Ответ: Р ={0,375; 0,625}, Q ={0, 5; 0, 5}, 𝜈 = 5, 5 Графическое решение задачи показано на рис. 2. 𝑝10 = ν 7 8 5,5 4 3 0,375 1 p Рис. 2 Переходим к более сложным играм с двумя стратегиями у одного игрока. Игры 2 x n Пусть задана платежная матрица игры 2 x n: 𝑎11 𝑎12 … 𝑎1𝑛 (𝑎 𝑎22 … 𝑎2𝑛 ) 21 Согласно теореме 2 нахождение цены игры и оптимального значения p0 для игрока А равносильно решению уравнения: 𝜈 = min (𝑎1𝑗 𝑝0 + 𝑎2𝑗 (1 − 𝑝0 )) = max min (𝑎1𝑗 𝑝 + 𝑎2𝑗 (1 − 𝑝 )) , 𝑗 = ̅̅̅̅̅ 1, 𝑛 𝑗 0≤𝑝≤1 𝑗 Исходя из этого, опишем общую схему, приводящую к нахождению решения. Максимум функции: min (𝑎1𝑗 𝑝 + 𝑎2𝑗 (1 − 𝑝 )) 𝑗 (4) проще всего найти, построив ее график. Предположим, что игрок А выбрал смешанную стратегию P={p, 1-p}, а игрок В – j-ю чистую стратегию Bj, j=1, …, n. Тогда средний выигрыш игрока А в ситуации {P, Bj} будет равен: 3 Лекция 3 (ММвТУиИО) (j): 𝜈𝑗 = 𝑎1𝑗 𝑝 + 𝑎2𝑗 (1 − 𝑝) На плоскости (p,ν), где 𝑝 ∈ [0, 1], это уравнение (j) задает прямую. Т.о., каждой чистой стратегии Вj игрока В на этой плоскости соответствует своя прямая. Поэтому в качестве первого шага на плоскости (p, ν) проводятся все эти прямые (рис. 3): (j): 𝜈 = 𝑎1𝑗 𝑝 + 𝑎2𝑗 (1 − 𝑝), j=1, …, n ν 1 p Рис. 3 В качестве второго шага для каждого значения р, 0≤р≤1, путем визуального сравнения соответствующих ему значений ν на каждой из построенных прямых определяется и отмечается наименьшее значение (рис. 4). ν 1 p Рис. 4 4 Лекция 3 (ММвТУиИО) В результате описанной процедуры выделяется ломаная, которая и является графиком функции (4) (жирная линия на рис. 4). Эта ломаная огибает снизу все семейство построенных прямых, и ее принято называть нижней огибающей этого семейства. Верхняя точка построенной нижней огибающей и определяет цену игры – ν, и оптимальную стратегию P0 = {p0, 1-p0} игрока А (рис. 5). Описанная процедура может рассматриваться как некоторый аналог максиминного подхода при отсутствии седловой точки. ν ν p0 1 p Рис. 5 Пример 3.2. Рассмотрим игру, заданную матрицей 2х6: 6 4 3 1 −1 0 ( ) −2 −1 1 0 5 4 Решение. 1-ый шаг. Анализ игры на наличие седловой точки. Нижняя цена игры равна -1, верхняя – равна 1. Седловой точки нет. Решение игры нужно искать в смешанных стратегиях. 2-ой шаг. Вычисление средних выигрышей игрока А (проводится при условии, что игрок В выбирает только чистые стратегии). 𝑝 | 6 4 3 1 −1 0 Из таблицы 1 − 𝑝 | −2 −1 1 0 5 4 Получаем В1: 𝑤 = 6𝑝 − 2(1 − 𝑝) В2: 𝑤 = 4𝑝 − (1 − 𝑝) В3: 𝑤 = 3𝑝 + (1 − 𝑝) В4 : 𝑤 = 𝑝 В5: 𝑤 = −𝑝 + 5(1 − 𝑝) В6 : 𝑤 = 4 ( 1 − 𝑝 ) или после упрощения: В1: 𝑤 = 8𝑝 − 2 5 Лекция 3 (ММвТУиИО) В2: 𝑤 = 5𝑝 + 1 В3: 𝑤 = 2𝑝 + 1 В4 : 𝑤 = 𝑝 В5: 𝑤 = −6𝑝 + 5 В6: 𝑤 = −4𝑝 + 4 3-ий шаг. Построение нижней огибающей Строим на координатной плоскости (p, w) все шесть прямых, уравнения которых получены на 2-м шаге (рис. 6), и находим их нижнюю огибающую. ν 7 6 5 В1 4 В2 3 В3 2 В4 1 В5 ν -1 p0 В6 1 p -2 -3 Рис. 6 4-ый шаг. Отыскание цены игры и оптимальной смешанной стратегии игрока А При построении нижней огибающей видно, что в наивысшей точке пересекаются прямые В4 и В5, заданные уравнениями 𝜈 = 𝑝 и 𝜈 = −6𝑝 + 5 соответственно. Решая 𝜈=𝑝 {𝜈 = −6𝑝 + 5 систему уравнений получаем { 𝑝0 = 𝜈= 5 7 5 7 Тем самым, цена игры и оптимальная стратегия игрока А соответственно равны: 5 5 2 𝜈= , 𝑃0 = { , } 7 7 7 В принципе, на этом этапе решение игры для игрока А заканчивается, т.к. его интересует отыскание собственной оптимальной стратегии и ожидаемого наилучшего гарантированного результата. Следует отметить, что, решая матричную игру, исследователь обычно отождествляет себя с одним из игроков (как правило, это игрок А), считая другого своим противником. Это приводит к тому, что основное внимание уделяется 6 Лекция 3 (ММвТУиИО) поиску оптимальных стратегий только игрока А, а стратегии противника могут вообще не интересовать исследователя. Однако в ряде случаев оказывается важным знать оптимальные смешанные стратегии обоих игроков. Поэтому рассмотрим алгоритм поиска параметров оптимальной стратегии и для игрока В. В зависимости от формы нижней огибающей возможны несколько случаев. Случай А. Нижняя огибающая имеет ровно одну наивысшую точку (𝑝0 , 𝜈 0 ): 1) Если 𝑝0 = 0 (оптимальная стратегия игрока А – это чистая стратегия А2), то игроку В выгодно применить чистую стратегию Вj, соответствующую прямой, проходящей через точку (0, 𝜈 0 ) и имеющей наибольший отрицательный наклон в этой точке (рис. 7). νw ν0 Bj 1 p Рис. 7 2) Если 𝑝0 = 1 (оптимальная стратегия игрока А – чистая стратегия А1), то w ν0 Bj 1 p Рис. 8 7 Лекция 3 (ММвТУиИО) оптимальной для игрока В является чистая стратегия Вj, соответствующая прямой, проходящей через точку (1, 𝑣 0 ) и имеющей наибольший положительный наклон в этой точке (рис. 8). 3) Если 0 < 𝑝0 < 1, то в наивысшей точке нижней огибающей пересекаются, по меньшей мере, две прямые, одна из которых Вk (соответствующая стратегии Вk игрока В) имеет положительный наклон, а другая Вl – отрицательный (рис. 9). В этом случае оптимальная смешанная стратегия игрока В получается, если положить qk = q, ql = 1-q, qj = 0, j ≠ k,l, где q – решение уравнения a1kq + a1l(1-q) = a2kq + a2l(1-q) ν Bk ν0 Bl 1 p Рис. 9 Случай Б. Нижняя огибающая содержит горизонтальный участок, соответствующий чистой стратегии Вk игрока В, которая и является оптимальной для него (рис. 10). ν ν0 Bj 1 p Рис. 10 8 Лекция 3 (ММвТУиИО) Пример 3.2 (продолжение). Покажем, как найти полное решение игры, т.е. еще и оптимальную смешанную стратегию игрока В: 𝑄0 = {𝑞10 , 𝑞20 , 𝑞30 , 𝑞40 , 𝑞50 , 𝑞60 } 1) выделяя из шести чистых стратегий игрока В стратегии В4 и В5, которым соответствуют прямые, определяющие наивысшую точку нижней огибающей, положим 𝑞10 = 0, 𝑞20 = 0, 𝑞30 = 0, 𝒒𝟎𝟒 = 𝒒, 𝒒𝟎𝟓 = 𝟏 − 𝒒, 𝑞60 = 0, 2) приравняем к найденной цене игры любой из двух средних выигрышей игрока В (в случае, когда игрок А выбирает одну из своих чистых стратегий), отвечающих предложенной смешанной стратегии 0 0 𝑞 1−𝑞 0 __ __ __ __ __ __ 6 4 3 1 −1 −2 −1 1 0 5 4 5 5 или 5(1 − 𝑞) = 7 7 3) решая любое из этих уравнений, получаем один и тот же результат 6 6 𝑞0 = , 𝑞0 = 7 7 Т.о. полное решение игры имеет следующий вид 5 2 6 1 5 𝑃 0 = { , }, 𝑄0 = {0,0,0, , , 0} , 𝜈= 7 7 7 7 7 𝑞 − (1 − 𝑞 ) = Замечание. Ситуацию с наличием лишь двух конкурирующих стратегий игрока А нельзя считать надуманной, поскольку на практике она возникает сравнительно часто. Например, в случае, если нужно сравнить два образца некоторого изделия (скажем, старого и модернизированного) с целью выяснения возможности замены, это удобно сделать, используя формализацию с помощью платежной матрицы 2хn. 9