Стратегическое равновесие в 2 x 2 играх

Случай единственного устойчивого решения, не реализуемого в чистых стратегиях

Первый и третий случаи, рассмотренные в заключительном пункте приведенного выше доказательства теоремы, необходимо включают в число устойчивых решений некоторую пару (x*,y*), образом которой является одна из вершин квадрата D. Это означает, что в таком решении каждая из сторон использует с единичной вероятностью одну из своих чистых стратегий. Для иллюстрации отметим, что паре $$(0,1) \in D$$, маркированной темной точкой на левом фрагменте рис. 2.10, соответствуют смешанная стратегия (x*,1-x*)=(0,1) первой стороны и смешанная стратегия (y*,1-y*)=(1,0) второй стороны. Устойчивые решения такого типа реализуемы и в чистых стратегиях.

Пример, рассмотренный в лекции 8 (соглашение об ограничении лова рыбы), иллюстрирует этот случай. Используя выражения (10.6) и (10.8), получаем (в соответствии со значениями элементов матриц, соответствующих примеру), что A=B=0 и a=b=1. Этим значениям соответствуют левые верхние фрагменты на рис. 2.8 и рис. 2.9. Следовательно, задача имеет единственное устойчивое решение$$(x^\ast, 1 - x^\ast) = (y^\ast, 1 - y^\ast) = (0,1),$$ соответствующее уже рассмотренному ранее решению в чистых стратегиях.

Ситуация, когда $$2\times 2$$ игра не имеет устойчивых решений в чистых стратегиях, но обретает такое решение в смешанных стратегиях, соответствует второму случаю из пункта, завершающего доказательство теоремы. Устойчивое решение в смешанных стратегиях окажется единственным, если решениями систем (10.10) и (10.11) являются лишь точки трехзвенных ломаных линий, соединяющих концы разных диагоналей квадрата. При этом единственная устойчивая пара стратегий$$(x^\ast, 1 - x^\ast) = (\beta, 1 - \beta),\quad (y^\ast, 1 - y^\ast) = (\alpha, 1 -\alpha),$$ порождается единственной точкой $$(x^\ast, y^\ast) = (\beta,\alpha)$$, в которой пересекаются указанные выше ломаные линии. В этом случае$$0 < \alpha < 1,\quad 0 < \beta < 1$$ и, кроме того, знаки величин A и B должны быть различны, т.е.$$AB < 0$$ (см. рис. 2.8 и рис. 2.9).

Неравенства (11.2) для величин $$\alpha$$ и $$\beta$$ из (10.19), (10.20), определяемых соответственно коэффициентами a, A из (10.6) и b, B из (10.8), имеют следствием отношения$$a_{11} \ne a_{21},\quad a_{22} \ne a_{12},\quad b_{11} \ne b_{12},\quad b_{22} \ne b_{21}.$$ Т.е. условие единственности решения в смешанных стратегиях предполагает, что коэффициенты, находящиеся в одном и том же столбце матрицы первого игрока, должны быть различны. Аналогично, должны быть различны и коэффициенты из одной и той же строки матрицы второго игрока.

Оптимальные смешанные стратегии в 2 x 2 матричной игре

Как уже отмечалось, антагонистическому случаю соответствуют условия (8.2), согласно которым для величин из (10.6) и (10.8) справедливы отношения$$a = a_{22} - a_{12},\quad b = -a_{22} + a_{21}.$$

При этом$$A = -B,$$ что обеспечивает выполнение неравенства (11.3). В силу справедливости условий (8.2), справедливость неравенств (11.4) является необходимым следствием отсутствия седлового значения $$2\times 2$$ матрицы игры (см. определение в лекции 8), поскольку совпадение значений коэффициентов в любой строке (или в столбце) $$2\times 2$$ матрицы гарантирует существование такого значения. Таким образом, в $$2\times 2$$ антагонистической игре отсутствие устойчивых решений в чистых стратегиях гарантирует существование единственного устойчивого решения в смешанных стратегиях, порождаемого парой $$(\beta, \alpha)$$, где$$\alpha = (a_{22} - a_{12})/A,\qquad \beta= (a_{22} - a_{21})/A.$$ При этом$$x^\ast = (a_{22} - a_{21})/A,\qquad 1 - x^\ast = (a_{11} - a_{12})/A,$$ $$y^\ast = (a_{22} - a_{12})/A,\qquad 1 - y^\ast = (a_{11} - a_{21})/A,$$ и для ядра M(x,y)=M1(x,y) смешанного расширения исходной игры справедлива оценка$$ (\forall y \in [0,1])\, M(x^\ast, y) = \{[a_{11} (a_{22} - a_{21}) + a_{21}(a_{11} - a_{12})] \cdot y +\\ + [a_{12} (a_{22} - a_{21}) + a_{22}(a_{11} - a_{12})](1 -y)\}/A =\\ = (a_{11}a_{22} - a_{12}a_{21})/A = M(x^\ast, y^\ast). $$ Таким образом, цена игры в смешанных стратегиях (т.е. математическое ожидание выигрыша первой стороны при реализации устойчивой пары смешанных стратегий из (11.7), (11.8)) есть$$v = (a_{11}a_{22} - a_{12}a_{21})/A.$$

Отметим одно важное обстоятельство. Из (11.9), (11.10) следует, что$$(\forall y \in [0,1])\, M(x^\ast, y) = v.$$

Аналогично можно получить симметричное утверждение$$(\forall x \in [0,1])\, M(x, y^\ast) = v.$$ Отсюда следует вывод о том, что замечание, сделанное в лекции 10, не зависит от конкретных значений элементов $$2\times 2$$ матрицы игры. Пусть одна из сторон (заведомо) использует рулетку, реализующую оптимальную смесь чистых стратегий. Тогда, независимо от того, какую стратегию выбирает другая сторона, ее ожидаемый выигрыш совпадает с ценой игры. Т.е. любая ее стратегия обеспечивает максимальный гарантированный уровень математического ожидания выигрыша (величину v для стороны P1 и величину ( -v для стороны P2 ).

Согласно выражениям (11.7), (11.8) и (11.10), рассмотренный ранее пример рекламной борьбы (см. лекцию 10), не имеющий устойчивых решений в чистых стратегиях, имеет единственное устойчивое решение в смешанных стратегиях:$$(x^\ast, 1 - x^\ast) = (y^\ast, 1 - y^\ast) = (\frac{1}{2},\frac{1}{2}),\quad v =0.$$ Это же решение было получено ранее (некоторым частным способом); см. (10.3). Заметим, что игры, которым соответствует нулевая цена, часто называют безобидными.

Теперь вернемся к примеру погони за конкурентом, в котором при отсутствии полной информации (см. дерево игры на рис. 2.5) нет устойчивых решений в чистых стратегиях (см. также замечание 2.2 в лекции 9). Обратимся к соответствующей этому случаю матрице $$4\times 2$$ матрице игры, приведенной в лекции 9. Заметим, что первая и вторая стратегии стороны P1 дают одни и те же выигрыши против одной и той же стратегии стороны P2. При этом третья стратегия стороны P1 даже превосходит ее четвертую стратегию. Фактически, мы имеем ситуацию, когда каждый элемент матрицы, находящийся в строке с номером i, превышает соответствующий (т.е. находящийся в том же столбце) элемент из строки с номером k (или хотя бы не меньше, чем этот элемент):$$a_{ij} \ge a_{kj},\quad 1 \le j \le 2.$$ В этом случае говорят, что строка i доминирует строку k. Ясно, что любое значение выигрыша, обеспечиваемое использованием доминируемой стратегии с номером k, может быть достигнуто использованием доминирующей стратегии с номером i. Поэтому в рассматриваемом примере сторона P1 может ограничиться использованием второй и третьей стратегий. В результате получаем (редуцированную) игру с $$2\times 2$$ матрицей:

Согласно (11.7), (11.8) и (11.10), этой игре соответствует устойчивое (и эффективное) решение в смешанных стратегиях вида:$$\left(x^\ast, 1 - x^\ast\right) = (\frac{2}{3}, \frac{1}{3}),\quad \left(y^\ast, 1 - y^\ast\right) = (\frac{1}{6}, \frac{5}{6}),$$ и цена игры $$v = 3\frac{2}{3}$$. Примем, что первая и четвертая (чистые) стратегии в исходной $$4\times 2$$ игре используются первым игроком с нулевыми вероятностями. Тогда случайный механизм, характеризуемый вектором вероятностей $$(0, \frac{2}{3}, \frac{1}{3}, 0)$$, обеспечивает игроку P1 математическое ожидание выигрыша, равное указанной выше цене $$v = 3\frac{2}{3}$$. Фактически, обсуждая этот пример, мы обобщили смешанные стратегии на случай, когда число чистых стратегий превышает 2. Более последовательное рассмотрение такого обобщения будет проведено ниже.

Замечание 2.5 (о природе устойчивости решений в антагонистической игре) Если изменить знаки всех элементов матрицы игры на противоположные, то, согласно (11.10), знак цены игры также изменится. Например, если значение цены игры было положительным (в этом случае говорят, что игра поставлена в пользу первого игрока), то оно изменится на отрицательное значение (т.е. игра будет поставлена уже в пользу второго игрока). Однако пара устойчивых смешанных стратегий, определяемых выражениями (10.7) и (10.8), останется неизменной.

Стратегическое равновесие при неантагонистических интересах сторон

Пусть интересы сторон, описываемые матрицами $$2\times 2$$ биматричной игры, являются неантагонистическими. С этим предположением продолжим обсуждение поведения игроков, которое характеризуется стратегическими парами (x*,y*), обладающими свойствами равновесия по Нэшу (т.е. отвечающими условиям (10.10), (10.11)).

Начнем со случая, когда $$2\times 2$$ биматричная игра имеет единственное устойчивое решение и оно достигается в смешанных стратегиях из (11.1). При этом:$$\alpha= (a_{22} - a_{12})/(a_{11} - a_{12} - a_{21} + a_{22}),$$ $$\beta= (b_{22} - b_{21})/(b_{11} - b_{12} - b_{21} + b_{22}).$$

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

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

Второй фермер оценивает полезность исхода, связанного с одновременной торговлей обеих сторон в одном и том же населенном пункте, как нулевую. Матрицы, соответствующие этой $$2\times 2$$ неантагонистической игре, представлены в табл. 2.7. Стратегии сторон соответствуют выбору конкретного пункта (П1 или П2) для торговли в текущий день.

Очевидно, что первый фермер заинтересован торговать в том же месте, что и второй. Интересы второго фермера диктуют противоположный выбор (тем не менее, как уже было отмечено, рассматриваемая игра не является антагонистической).

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

Согласно (10.6) и (10.8)$$A = 2,\ a = 1,\quad B = -4,\ b = -2.$$ Здесь выполняются условия (11.3), (11.4) и, следовательно, существует единственная устойчивая (по Нэшу) пара смешанных стратегий вида$$(x^\ast, 1 - x^\ast) = (y^\ast, 1 - y^\ast) = (\frac{1}{2}, \frac{1}{2});$$ cм. (11.1) и (11.11), (11.12). Т.е. каждый фермер может выбирать пункт для торговли в текущий день, например, путем бросания симметричной монеты. Определяемые выражениями (10.5)-(10.8) математические ожидания полезностей сторон, соответствующие устойчивой паре стратегий (11.13), равны величинам$$M_1 (x^\ast, y^\ast) = 2 \frac{1}{2}, \qquad M_2(x^\ast, y^\ast) = 1.$$

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

Согласно (11.1) и (11.11), стратегия (y*,1-y*) игрока P2 в $$2\times 2$$ биматричной игре совпадает со смешанной минимаксной стратегией (11.8) второго игрока в антагонистической игре с левой матрицей из табл. 2.6. Т.е. действия P2, соответствующие устойчивой паре, направлены на уменьшение выигрыша первого игрока, а не на увеличение собственного выигрыша.

Аналогична направленность действий стороны P1. Инвертируя знаки всех элементов в правой таблице из табл. 2.6, получим матрицу$$\begin{vmatrix} -b_{11} \quad -b_{12}\\ -b_{21} \quad -b_{22} \end{vmatrix}\!,$$ коэффициенты которой соответствуют проигрышам стороны P2.

Максиминная стратегия первого игрока в антагонистической игре с такой матрицей имеет вид:$$(x^\ast, 1 - x^\ast) = \left((b_{22} - b_{21})/B,\ (b_{11} - b_{12}/B)\right)\!;$$ ср. с (11.7). Согласно (11.1) и (11.12), распределение (11.14) есть также смешанная стратегия игрока P1, входящая в единственное устойчивое решение для смешанного расширения биматричной игры. Т.е. поведение P1 в равновесном (по Нэшу) решении направлено на уменьшение выигрыша второго игрока, а не на максимизацию собственного выигрыша. Этот феномен обычно называют антагонизмом поведения без антагонизма интересов.

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

Пример 2.6 (выбор пункта для строительства с долевым участием). Две фирмы P1 и P2 планируют строительство (с долевым участием) гостиничного комплекса в одном из двух районов города (Р1 и Р2). Фирма P1 заинтересована строить комплекс в районе Р1, где у нее есть ряд предприятий обслуживания, которые могли бы принести (в этом случае) дополнительный доход. Фирма P1 не имеет таких предприятий в районе Р2. Но именно в этом втором районе расположены точки обслуживания, созданные фирмой P2, которая (по этой причине) заинтересована в том, чтобы комплекс строился в районе P2.

Ни одна из фирм не имеет достаточных свободных средств, чтобы построить комплекс в одиночку. Поэтому, если фирмы не смогут прийти к согласию относительно района строительства, то стройка окажется невозможной. Полезность такого исхода является нулевой для каждой фирмы. Матрицы описанной игрыПриведенный пример имеет и другие известные в литературе интерпретации: "семейный спор" (Льюс Р.Д., Райфа Х. Игры и решения. - М.: ИЛ, 1961), "вежливые водители" (Мулен Э. Теория игр с примерами из математической экономики. - М.: Мир, 1985) и др. представлены в табл. 2.8.

Из данных табл. 2.8 и выражений (10.6), (10.8), (10.9), (10.20) получаем, что$$A = 3,\ a=1,\ \alpha = \frac{1}{3},\qquad B = 3,\ b = 2,\ \beta= \frac{2}{3}.$$ При этом из рис. 2.8 и рис. 2.9 следует (см. средний фрагмент на рис. 2.10), что существует три пары (x*, y*), удовлетворяющие условиям устойчивости (10.10), (10.11). Этот случай иллюстрируется рис. 2.11.

Смешанные стратегии, соответствующие этим парам, и отвечающие им математические ожидания M1(x*,y*), M2(x*, y*) выигрыша сторон представлены в табл. 2.9.

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

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

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

Кроме того, реализация любой из устойчивых пар стратегий требует согласования действий сторон. Действительно, например, если игрок P1 выберет чистую стратегию i*=2, являющуюся компонентой первой устойчивой пары из табл. 2.9, а игрок P2 выберет чистую стратегию {j*=1}, а иявляющуюся компонентой второй устойчивой пары, то такой совместный выбор не обладает свойствами поведения в равновесии. Таким образом, в конфликтах с неантагонистическими интересами сторон анализ устойчивости решений может оказаться недостаточным для выработки удовлетворительных схем поведения этих сторон. Мы вернемся к обсуждению этого вопроса в следующей лекции.

Смешанные расширения m x n биматричных игр

Рассмотренная выше схема выбора поведения, основанная на (искусственном) внесении неопределенности путем использования случайных механизмов, может быть обобщена на случай, когда число чистых стратегий каждой из сторон превышает две. При таком подходе первая сторона P1 использует рулетку, которая имеет m исходов, характеризуемых вероятностями наступления xi, $$1\le i\le m$$, а вторая сторона - рулетку с n исходами, характеризуемыми вероятностями наступления yj, $$1\le j\le n$$. При этом m и n есть числа чистых стратегий, имеющихся соответственно у первой и второй сторон. Теперь введем следующее определение.

Определение 2.5. Смешанными стратегиями игроков P1 и P2 в $$m\times n$$ биматричной игре соответственно называются векторы$$\begin{gathered} x = (x_1 \dots x_j \dots x_m) \in S_m \subset R^m,\\ y = (y_1 \dots y_j\dots y_n) \in S_n \subset R^n, \end{gathered}$$ где Sm и Sn есть множества векторов с неотрицательными координатами, сумма которых равна единице, т.е.$$\begin{gathered} S_m = \{x \in R^m \colon x_i \ge 0,\ 1 \le i \le m,\quad x_1 + \ldots + x_m = 1\},\\ S_n = \{y \in R^n \colon y_j \ge 0,\ 1 \le j \le n,\quad y_1 + \ldots + y_m = 1\}. \end{gathered}$$ Числа xi и yj есть вероятности, с которыми (независимые) рулетки игроков P1 и P2 порождают исходы соответственно с номерами i и j. Тем самым определяется использование игроками P1 и P2 соответственно чистой стратегии с номером i и чистой стратегии с номером j в текущей партии игры. пар

Поскольку в классе Sm смешанных стратегийМногомерные фигуры, обладающие свойствами (11.15), называются симплексами .} стороны P1 для любого номера i, $$1\le i\le m$$, существует стратегия x(i), удовлетворяющая условиям$$x_k(i) = 0,\quad k = 1\dots i-1, i+1\dots m,\quad x_i(i) = 1,$$ и, следовательно, обеспечивающая применение чистой стратегии i с единичной вероятностью, то игра в чистых стратегиях может интерпретироваться как частный случай игры в смешанных стратегиях. Аналогичное утверждение справедливо для игрока $$P_2$$.

Выбор игроками P1 и P2 смешанных стратегий $$x \in S_m$$ и $$y \in S_n$$ еще не определяет конкретного исхода игры. В связи с этим, в качестве оценок эффективности M1(x, y) и M2(x,y), которую обеспечивает игрокам выбор пары (x,y), принимаются математические ожидания$$\begin{gathered} M_1(x,y) = \sum_{i=1}^m \sum_{j=1}^n a_{ij} x_i y_j,\\ M_2(x,y) = \sum_{i=1}^m \sum_{j=1}^n b_{ij} x_i y_j, \end{gathered}$$ при определении которых учтена (вероятностная) независимость случайных механизмов, используемых сторонами.

Если принять, что x и y есть векторы-столбцы, и обозначить матрицы, представляющие выигрыши первого и второго игроков (при игре в чистых стратегиях), соответственно через A и B, то, согласно (11.16), смешанное расширение $$m\times n$$ биматричной игры можно представить следующей моделью (в нормальной форме):$$M_1(x,y) = x^{T} Ay,\quad M_2 (x,y) = x^{T} By,\quad x \in S_m,\ y \in S_n$$ (верхний индекс T соответствует операции транспонирования, сопоставляющей вектору-столбцу вектор-строку).

Для произвольной $$m\times n$$ биматричной игры справедливо утверждение, что в ее смешанном расширении существует хотя бы одна ситуация равновесия (по Нэшу). Т.е. в смешанном расширении каждой биматричной игры существует пара смешанных стратегий ( x*,y*), удовлетворяющая неравенствам (3.3), где X=Sm и Y=Sn. В случае, когда интересы сторон являются противоположными (антагонистическими), это утверждение подразумевает существование седловой точки (x*,y*) ядра$$M(x,y) = M_1(x,y) = x^T Ay,$$ удовлетворяющей условиям:$$(\forall x \in S_m) (\forall y \in S_n)\quad x^T Ay^\ast \le x^{\ast T} Ay^\ast \le x^{\ast T}Ay;$$ см. (6.2) и (6.3).

Существование пар стратегий, удовлетворяющих условиям (11.9) и, следовательно, являющихся равновесными решениями для смешанных расширений $$m\times n$$ антагонистических игр, которые имеют ядра вида (11.18) (с любыми матрицами A ), будет показано в следующем параграфе. Доказательство упомянутого выше факта разрешимости условий (6.3) для смешанного расширения (11.17) любой $$m \times n$$ биматричной игры может быть найдено в других источникахСм., например: Оуэн Г. Теория игр. - М.: Мир, 1971.. Мы опускаем это доказательство в нашей небольшой (соответствующей программе вводного курса) книге, поскольку для общего $$m\times n$$ случая (в отличие от уже рассмотренных $$2\times 2$$ задач) оно не дает способа вычисления пары стратегий, порождающих ситуацию равновесия (т.е. оно не является конструктивным ). Кроме того, как уже было отмечено, анализ устойчивости в таких задачах может оказаться недостаточным для выработки удовлетворительных схем поведения сторон.