Ситуация равновесия в матричных играх

Лекция 2 (ММвТУиИО) СИТУАЦИЯ РАВНОВЕСИЯ В МАТРИЧНЫХ ИГРАХ Рассмотрев на Лекции №1 некоторые принципы формализации конфликтных ситуаций с помощью модели антагонистической игры двух лиц с нулевой суммой, посмотрим, что предлагает теория игр для исследования таких моделей. ЧИСТЫЕ СТРАТЕГИИ Рассмотрим следующий пример матричной игры. Пример 2.1. Два игрока А и В, не глядя друг на друга, кладут на стол по картонному кружку красного (r), зеленого (g) или синего (b) цвета, сравнивают цвет кружков и расплачиваются друг с другом баллами так, как показано в матрице игры, описывающей выигрыш игрока А (в этой матрице строки сверху-вниз соответствуют стратегиям Ar, Ag, Ab, а столбцы слева-направо – стратегиям Вr, Вg, Вb): −2 2 −1 А=( 2 1 1 ). 3 −3 1 Считая, что эта игра (3х3) повторяется многократно, попробуем определить оптимальные стратегии каждого из игроков. Выигрыш соответствует положительному элементу платежной матрицы, а отрицательный указывает на проигрыш игрока А. Соответственно, матрица выигрышей игрока В получается из этой матрицы заменой каждого ее элемента на противоположный. Начнем с последовательного анализа стратегий игрока А, не забывая о том, что, выбирая стратегию игрока А, нужно принимать в расчет ответную стратегию игрока В, которую он должен выбрать так, чтобы свести выигрыш игрока А к минимуму. Так на стратегию Аr он может ответить стратегией Br (минимальный выигрыш равен -2, что на самом деле означает проигрыш игрока А, равный 2), на стратегию Аg– стратегией Bg или Bb (минимальный выигрыш игрока А равен 1), а на стратегию Аb – стратегией Bg (минимальный выигрыш игрока А равен -3). Запишем эти минимальные выигрыши в дополнительном столбце таблицы справа: Br Bg Bb Аr -2 2 -1 -2 Аg 2 1 1 1 Аb 3 -3 1 -3 Принцип выбора стратегии игроками А и В: 1 Лекция 2 (ММвТУиИО) Максимин (maxmin). Игрок А останавливает свой выбор на стратегии Аg, при которой его минимальный выигрыш, указанный в доп.столбце, максимален: max {-2, 1, -3} =1, т.е. maxmin = 1. Если игрок А будет придерживаться этой стратегии, то ему гарантирован выигрыш, не меньший 1, при любом поведении противника в игре. Аналогичные рассуждения можно провести и для игрока В. Т.к. игрок В заинтересован в том, чтобы свести выигрыш игрока А к минимуму, то ему нужно сначала проанализировать каждую свою стратегию с точки зрения максимального выигрыша игрока А. Выбирая свою стратегию, игрок В должен учитывать, что ответной стратегией его противника будет та, при которой его (игрока А) выигрыш будет максимальным. Так на стратегию Br он может ответить стратегией Аb (максимальный выигрыш игрока А равен 3), на стратегию Bg – стратегией Аr (максимальный выигрыш игрока А равен 2), а на стратегию Bb – стратегией Аg или Аb (максимальный выигрыш игрока А равен 1). Эти максимальные выигрыши запишем в дополнительной нижней строке таблицы: Br Bg Bb Аr -2 2 -1 -2 Аg 2 1 1 1 Аb 3 -3 1 -3 3 2 1 Минимакс (minmax). Игрок В останавливает свой выбор на стратегии Bb, при которой максимальный выигрыш игрока А, указанный в доп.строке, минимален: min {3, 2, 1} =1, т.е. minmax = 1. Если игрок В будет придерживаться этой стратегии, то при любом поведении противника он проиграет не больше 1. Итак, в рассматриваемой игре числа maxmin и minmax совпали: maxmin = minmax = 1. Выделим соответствующие стратегии в таблице: Br Bg Bb Аr -2 2 -1 Аg 2 1 1 Аb 3 -3 1 Выделенные стратегии Аg и Bb являются оптимальными для игроков А и В, 2 Лекция 2 (ММвТУиИО) Аg = Aopt , Bb = Bopt в следующем смысле: при многократном повторении игры отказ от выбранной стратегии любым из игроков уменьшает его шансы на выигрыш (увеличивает шансы на проигрыш). В самом деле, если игрок А будет придерживаться не стратегии Аg, а выберет иную, например, Аr, то вряд ли стоит рассчитывать на то, что игрок В этого не заметит. Ясно, что в этом случае он отдаст предпочтение стратегии Br. А на выбор Аb игрок В ответит, например, стратегией Bg. В результате отказа от оптимальной для него стратегии выигрыш игрока А уменьшится. Если же от стратегии Bopt отказывается игрок В, выбирая, например, стратегию Br, то игрок А может ответить на это стратегией Аb и, тем самым, увеличить свой выигрыш. В случае стратегии Bg ответ игрока А – Аr. Тем самым, ситуация { Аg, Bb } оказывается равновесной. Рассмотрим теперь произвольную матричную игру: 𝑎11 𝑎12 … 𝑎1𝑛 𝑎21 𝑎22 … 𝑎2𝑛 А=( … … … … ) 𝑎𝑚1 𝑎𝑚2 … 𝑎𝑚𝑛 и опишем общий алгоритм, посредством которого можно определить, есть ли в этой игре ситуация равновесия или ее нет. Предположение: оба игрока действуют разумно, т.е. стремятся к получению максимального для себя выигрыша, считая, что соперник также действует наилучшим (для себя) образом. Действия игрока А 1-ый шаг. В каждой строке матрицы А находится минимальный элемент: 𝛼𝑖 = min 𝑎𝑖𝑗 𝑗 𝑖 = 1, … , 𝑚 Полученные числа α1, α2, …, αm приписываются к исходной таблице в виде правого допольнительного столбца: 𝑎11 𝑎12 … 𝑎1𝑛 | 𝛼1 𝑎21 𝑎22 … 𝑎2𝑛 | 𝛼2 . … … … … | … 𝑎𝑚1 𝑎𝑚2 … 𝑎𝑚𝑛 | 𝛼𝑚 Т.е., выбирая стратегию Ai, игрок А вправе рассчитывать на то, что в результате любых действий противника (игрока B) в рамках правил игры, он выиграет не меньше, чем αi. 2-ой шаг. Среди чисел α1, α2, …, αm выбирается максимальное число: 3 Лекция 2 (ММвТУиИО) 𝛼 = max 𝛼𝑖 , 𝑖 Т.е., действуя наиболее осторожно и рассчитывая на наиболее разумное поведение противника, игрок А должен остановиться на той стратегии Аi, для которой число αi является максимальным. Или, учитывая оба шага: 𝛼 = max min 𝑎𝑖𝑗 . 𝑗 𝑖 Отметим, что выбранное число α является одним из элементов заданной матрицы А. Если игрок А будет придерживаться стратегии, выбранной описанным выше способом, то, при любом поведении игрока В, игроку А гарантирован выигрыш не меньший α. Число α называется нижней ценой игры. Таким образом, нижняя цена игры – это гарантированный выигрыш, который может обеспечить себе первый игрок. Принцип построения стратегии игрока А, основанный на максимизации минимальных выигрышей, называется принципом максимина, а выбираемая в соответствии с этим принципом стратегия Аi0 – максиминной стратегией игрока А. Действия игрока В 1-ый шаг. В каждом столбце матрицы А ищется максимальный элемент: 𝛽𝑗 = max 𝑎𝑖𝑗 , 𝑗 = 1, … , 𝑛. 𝑖 Полученные числа β1, β2, …, βn приписываются к исходной таблице в качестве нижней (добавочной) строки: 𝑎11 𝑎12 … 𝑎1𝑛 | 𝛼1 𝑎21 𝑎22 … 𝑎2𝑛 | 𝛼2 … … … … | … . 𝑎𝑚1 𝑎𝑚2 … 𝑎𝑚𝑛 | 𝛼𝑚 −−−−−−−−−−−− 𝛽1 𝛽2 … 𝛽𝑛 | Т.е., выбирая стратегию Bj, игрок B рассчитывает на то, что, в результате любых действий противника (игрока А) в рамках правил игры, он проиграет не больше, чем βj. 2-ой шаг. Среди чисел β1, β2, …, βn выбирается минимальное число: 𝛽 = 𝑚𝑖𝑛 𝛽𝑖𝑗 , 𝑗 Т.е., действуя наиболее осторожно и рассчитывая на разумное поведение противника, игрок В останавливается на той стратегии Вk, для которой число βk является минимальным. Учитывая оба шага: 𝛽 = min max 𝑎𝑖𝑗 . 𝑗 𝑖 4 Лекция 2 (ММвТУиИО) По построению, выбранное число β также является одним из элементов заданной матрицы А. Если игрок В будет придерживаться стратегии, выбранной описанным выше способом, то при любом поведении игрока А ему (игроку В) гарантирован проигрыш не больший β. Число β называется верхней ценой игры. Таким образом, верхняя цена игры – это минимальные потери, который может обеспечить себе игрок В. Принцип построения стратегии игрока В, основанный на минимизации максимальных потерь, называется принципом минимакса, а выбираемая в соответствии с этим принципом стратегия Вj0 – минимаксной стратегией игрока В. Нижняя цена игры α и ее верхняя цена β всегда связаны неравенством α ≤ β. Если α = β, т.е. max min 𝑎𝑖𝑗 = 𝑎𝑖0𝑗0 = min max 𝑎𝑖𝑗 , 𝑖 𝑗 𝑗 𝑖 то ситуация {Ai0, Bj0} оказывается равновесной, и ни один из игроков не заинтересован в том, чтобы ее нарушить. В этом случае (когда нижняя цена игры равна верхней цене игры) общее значение называется просто ценой игры и обозначается через ν. Цена игры совпадает с элементом 𝑎𝑖0𝑗0 матрицы игры А, расположенным на пересечении i0-й строки (стратегия Ai0 игрока А) и j0-го столбца (стратегия Bj0 игрока В), - минимальным в своей строке и максимальным в своем столбце. Этот элемент называют седловой точкой матрицы А (или точкой равновесия), а про игру говорят, что она имеет седловую точку. Стратегии Ai0 и Bj0 соответствующие седловой точке, называются оптимальными чистыми стратегиями, а совокупность пары оптимальных стратегий и цены игры – решением матричной игры с седловой точкой. Про саму игру в этом случае говорят, что она решается в чистых стратегиях. Седловых точек (пар оптимальных стратегий) в матричной игре может быть несколько, но все они имеют одно и то же значение. Пример 2.2. В таблице приведена платежная матрица некоторой игры: А1 А2 А3 B1 2 7 5 B2 4 6 3 B3 7 8 4 B4 5 7 1 5 Лекция 2 (ММвТУиИО) В соответствии с приведенным выше алгоритмом, определим для указанной матрицы нижнюю и верхнюю цены игры: B1 B2 B3 B4 А1 2 4 7 5 2 А2 7 8 7 6 6 А3 5 3 4 1 1 7 8 7 6 Нижняя цена игры (гарантированный выигрыш) α равна 6 и соответствует стратегии А2 игрока А. В этих условиях игроку В ничего не остается как придерживаться стратегии В2, которая ведет к наименьшему проигрышу. Верхняя цена игры (минимальный проигрыш) β также равен 6 и соответствует стратегии В2 игрока В. Игрок А, максимизируя в этих условиях свой выигрыш, выберет стратегию А2. Таким образом, пара стратегий {А2, В2} является решением игры, цена игры ν равна 6. Элемент а22=6 – седловая точка. Игра имеет решение в чистых стратегиях. Пример 2.3. Для игры, заданной следующей платежной матрицей, проверить наличие оптимальной чистой стратегии: 1 −4 9 16 ( А = 16 9 4 1) 10 10 10 15 Решение. Построим таблицу и воспользуемся алгоритмом: B1 B2 B3 B4 А1 1 -4 9 16 -4 А2 16 9 4 1 1 А3 10 10 10 15 10 16 16 10 10 Нижняя цена игры α = 10 и ей соответствует стратегия А3. Верхняя цена игры β = 10 и ей соответствуют стратегии В2 и В3. Цена игры ν = 10. Элементы а32 = а33 = 10 – седловая точка. Игра имеет решения в чистых стратегиях: {А3, В2} и {А3, В3}. 6 Лекция 2 (ММвТУиИО) СМЕШАННЫЕ СТРАТЕГИИ Матричные игры с седловой точкой привлекают своей простотой, однако, более типичным является случай, когда применение описанного алгоритма приводит к «чистому» неравенству: α < β. Как показывает следующий пример, в этом случае предложенный выбор стратегий к равновесной ситуации уже не приводит, и при многократном повторении игры у игроков возникают мотивы к нарушению рекомендаций, основанных на описанном алгоритме действий игроков А и В. Пример 2.4. Рассмотрим игру 3х3, заданную матрицей: 4 −1 −3 А = (−2 1 3) 2 −3 Применив предложенный алгоритм, получим: B1 B2 B3 А1 4 -1 -3 -3 А2 -2 1 3 -2 А3 2 -3 -3 4 3 2 Нижняя цена игры α = -2 и ей соответствует стратегия А2, и верхняя цена игры β = 2 и соответствующая ей стратегия - В2. Игрок А, пытаясь максимизировать свой выигрыш, выберет стратегию А2. В этих условиях игрок В ответит стратегией В1 и сведет выигрыш А к проигрышу (-2). В свою очередь, на стратегию В1 у игрока А имеется ответная стратегия А1, дающая ему выигрыш 4. Тем самым, ситуация {А2, В2} равновесной не является и в данной игре не существует решения в чистых стратегиях. Рассмотрим общий случай антагонистической игры двух лиц с нулевой суммой. Пусть найдены нижняя цена игры, равная α, и верхняя цена игры, равная β. Случай, когда нижняя цена игры α и верхняя цена игры β не совпадают (α < β), означает, что игрок А может обеспечить себе выигрыш не меньший α, а игрок В имеет возможность не проиграть больше, чем β. Возникает вопрос, можно ли и как разделить между игроками («нераспределенную» из-за отсутствия чистых стратегий) разность β – α. Предыдущие построения на этот вопрос ответа не дают – они ограничивают рамки действий игроков чистыми стратегиями. Поэтому механизм, обеспечивающий получение каждым из игроков как можно большей доли этой разности, следует искать в расширении стратегических возможностей, имеющихся у игроков. 7 Лекция 2 (ММвТУиИО) Рассмотренный выше пример 2.4 иллюстрирует общее правило для игр без седловой точки: игрок, играющий по определенной (детерминированной) стратегии, оказывается в худшем положении по сравнению с игроком, который меняет стратегию случайным образом. Оказывается, что компромиссного распределения разности (β – α) между игроками и уверенного получения каждым игроком своей доли при многократном повторении игры можно достичь путем случайного чередования ими своих чистых стратегий. При таких действиях,  во-первых, обеспечивается наибольшая скрытность выбора стратегии (результат выбора не может стать известным противнику, поскольку он неизвестен и самому игроку);  во-вторых, при разумном построении механизма случайного выбора стратегий, набор последних оказывается оптимальным. Случайная величина, значениями которой являются стратегии игрока, называется его смешанной стратегией. Задание смешанной стратегии игрока состоит в указании тех вероятностей, с которыми выбираются его исходные чистые стратегии. Рассмотрим произвольную m x n-игру, заданную m x n-матрицей: А=(aij). Т.к. игрок А имеет m чистых стратегий, то его смешанная стратегия может быть описана набором m неотрицательных чисел (вероятностей, с которыми используется та или иная чистая стратегия Аi): p1 ≥ 0, p2 ≥ 0, …, pm ≥ 0, при этом ∑𝑚 𝑖=1 𝑝𝑖 = 1. Смешанная стратегия игрока В, имеющего n чистых стратегий, описывается набором n неотрицательных чисел (вероятностей с которыми используется та или иная чистая стратегия Вj): q1 ≥ 0, q2 ≥ 0, …, qn ≥ 0, при этом ∑𝑛𝑗=1 𝑞𝑗 = 1. Т.о. каждая чистая стратегия является частным случаем смешанной стратегии: чистая стратегия Аi является смешанной стратегией, описываемой набором чисел p1 , p2 , …, pm , где pi=1, pk =0 (k ≠ i). Для соблюдения секретности каждый из игроков применяет свои стратегии, не обращая внимания на выбор другого игрока. Таким образом, задав два набора P = {p1 , p2 , …, pm } и Q = {q1 , q2 , …, qn }, мы оказываемся в ситуации смешанных стратегий. В этих условиях каждая обычная ситуация (в чистых стратегиях) {Аi, Вj} по определению является случайным событием и, ввиду независимости выборов P и Q, реализуется с вероятностью pi * qj. Поскольку в этой ситуации игрок А получает 8 Лекция 2 (ММвТУиИО) выигрыш aij, то его итоговый выигрыш равен математическому ожиданию выигрыша в ситуации смешанных стратегий (P, Q): 𝑚 𝑛 𝑀𝐴 (𝑃, 𝑄) = ∑ ∑ 𝑎𝑖𝑗 ∗ 𝑝𝑖 ∗ 𝑞𝑗 𝑖=1 𝑗=1 Это число и принимается за средний выигрыш игрока А при смешанных стратегиях (P,Q). 0} Стратегии 𝑃0 = {𝑝10 , 𝑝20 , … , 𝑝𝑚 и 𝑄0 = {𝑞10 , 𝑞20 , … , 𝑞𝑛0 } называются оптимальными смешанными стратегиями соответственно, если выполнено следующее соотношение: игроков А и В 𝑀𝐴 (𝑃, 𝑄0 ) ≤ 𝑴𝑨 (𝑷𝟎 , 𝑸𝟎 ) ≤ 𝑀𝐴 (𝑃0 , 𝑄) Выписанные неравенства означают следующее:  левое неравенство – отклонение игрока А от оптимальной стратегии Р0 при условии, что игрок В придерживается стратегии Q0, приводит к тому, что выигрыш отклонившегося игрока А может только уменьшиться;  правое неравенство – отклонение игрока В от оптимальной стратегии Q0 при условии, что игрок А придерживается стратегии Р0, приводит к тому, что выигрыш игрока А может только возрасти, и, значит, выигрыш игрока В – только уменьшиться. Условие оптимальности равносильно тому, что: max min 𝑀𝐴 (𝑃, 𝑄) = 𝑀𝐴 (𝑃0 , 𝑄0 ) = min max 𝑀𝐴 (𝑃, 𝑄) 𝑃 𝑄 𝑄 𝑃 Величина 𝜈 = 𝑀𝐴 (𝑃0 , 𝑄0 ), определяемая последней формулой, называется ценой игры. Набор (Р0, Q0, ν), состоящий из оптимальных смешанных стратегий игроков А и В и цены игры, называется решением матричной игры. Основная теорема теории матричных игр Теорема 1 (Дж. фон Нейман). (1.1) Для матричной игры с любой матрицей А величины max min 𝑀𝐴 (𝑃, 𝑄) , min max 𝑀𝐴 (𝑃, 𝑄) 𝑄 𝑃 𝑄 𝑃 существуют и равны между собой: max min 𝑀𝐴 (𝑃, 𝑄) = min max 𝑀𝐴 (𝑃, 𝑄) 𝑃 𝑄 𝑄 𝑃 (1.2) Более того, существует по крайней мере одна ситуация в смешанных стратегиях 𝑃0 , 𝑄0 , для которой выполняется соотношение: 𝑀𝐴 (𝑃 0 , 𝑄0 ) = max min 𝑀𝐴 (𝑃, 𝑄) = min max 𝑀𝐴 (𝑃, 𝑄) P 𝑄 𝑄 𝑃 Иными словами, любая матричная игра имеет решение в смешанных стратегиях. 9 Лекция 2 (ММвТУиИО) Поиск этого решения опирается на факты, следующие из теоремы 2: Основные свойства оптимальных смешанных стратегий Теорема 2. Пусть 0} 𝑃0 = {𝑝10 , 𝑝20 , … , 𝑝𝑚 и 𝑄0 = {𝑞10 , 𝑞20 , … , 𝑞𝑛0 } - оптимальные смешанные стратегии и ν – цена игры. (2.1) Оптимальная смешанная стратегия 𝑃0 игрока А смешивается только из тех чистых стратегий Аi, i =1, …, m (т.е. отличными от нуля могут быть вероятности pi только с теми номерами i =1, …, m), для которых выполнены равенства: 𝑚 ∑ 𝑎𝑖𝑗 𝑝𝑖0 = 𝜈 𝑖=1 Это означает, что смешиваются не все чистые стратегии, а только те, которые в совокупности дают 𝜈. (2.2) Аналогично, в оптимальной смешанной стратегии 𝑄0 игрока В отличными от нуля могут быть вероятности qj, для номеров j=1, …, n которых выполнены равенства: 𝑛 ∑ 𝑎𝑖𝑗 𝑞𝑗0 = 𝜈 𝑗=1 (2.3) Кроме того, имеют место соотношения: 𝑚 𝜈= min ∑ 𝑎𝑖𝑗 𝑝𝑖0 𝑗 𝑖=1 𝑚 𝑛 𝑛 = max min ∑ 𝑎𝑖𝑗 𝑝𝑖 = minmax ∑ 𝑎𝑖𝑗 𝑞𝑗 = max ∑ 𝑎𝑖𝑗 𝑞𝑗0 𝑃 𝑗 𝑖=1 𝑄 𝑖 𝑗=1 𝑖 𝑗=1 Последние равенства представляют собой основу для разработки различных методов (алгоритмов) решения матричных игр. Отметим следующие условия применения смешанных стратегий: 1) Игра не имеет седловой точки. 2) Игроки используют случайную смесь чистых стратегий с фиксированными вероятностями. 3) Игра повторяется многократно в сходных условиях. 4) При любом ходе ни один из игроков не информирован о стратегии другого игрока. 5) Происходит усреднение результатов игр. 10