Смешанные стратегии и проблема устойчивости решений

Защитная роль смешанных стратегий

Как следует из последней рассмотренной теоремы (см. лекцию 9), наличие у сторон полной информации о развитии игры гарантирует существование стратегических решений, обладающих свойством устойчивости по Нэшу. Вместе с тем, когда такая информация отсутствует, устойчивые решения могут не существовать. Рассмотренная выше игра "погоня за конкурентом" (см. лекцию 8) является примером именно такого рода, если допустить, что сторона P2, принимает свои решения, не имея информации о первом выборе стороны P1. Рассмотрим еще один подобный пример.

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

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

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

Заметим, что коэффициенты этой матрицы совпадают с элементами матрицы из табл. 2.1, соответствующей игре в орлянку, которая рассмотрена 2 лекции 8. Матрица игры не содержит седловых значений. Сторона P1 может гарантировать себе лишь нижнюю цену игры (т.е. полезность, равную -1 ). Аналогично, сторона P2 может гарантировать, что ее проигрыш не превысит верхней цены игры (т.е. величины, равной +1 ). Напомним, что в антагонистической игре критерии эффективности сторон связаны отношением M1+M2=0 (см. определение в лекции 1).

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

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

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

Пусть сторона P1 выбирает стратегии П1 и П2 соответственно с вероятностями x и 1-x, где $$x \in [0{,}1]$$. Когда $$x = \frac{1}{2}$$, указанный случайный выбор можно реализовать, например, путем бросания симметричной монеты. При этом выбор пункта П1 можно связать с выпадением "Орла", а выбор пункта П2 - с выпадением "Решки". Случай $$x = \frac{3}{4}$$ может быть реализован бросанием симметричной монеты дважды. При этом двум последовательным реализациям "Решки" сопоставляется выбор пункта П2, а во всех остальных случаях выбирается пункт П1. Для произвольных значений x, $$0\le x \le 1$$, можно использовать компьютерные датчики псевдослучайных чисел, равномерно распределенных в отрезке [0,1]. При этом реализация значения $$\xi \in [0,x)$$ связывается с выбором варианта П1. В остальных случаях (т.е. при $$\xi \in [x,1])$$ выбирается вариант П2. Все такие случайные механизмы, используемые в задачах выбора вариантов решения, часто называют рулеткамиТермином рулетка первоначально называлось устройство для азартной игры. В этой игре участники делают ставки на номер лунки, в которую попадет шарик после остановки вращающегося круга. . Применительно к целям нашего рассмотрения, конкретное устройство рулетки является несущественным. Важно лишь то распределение вероятностей исходов, которое реализуется выбранным случайным механизмом.

Поскольку в рамках нового подхода выбор стороны P1 является случайным, сторона P2 не может предсказать его исход. Эта неопределенность является результатом искусственного введения в задачу некоторого неуправляемого параметра. При этом стороны могут ориентироваться лишь на математическое ожидание полезности$$M(x,j) = xa_{1j} + (1 - x)a_{2j},\quad 0 \le x \le 1,\ j = 1,2.$$ исхода игры для игрока P1, значение которого соответствует рулетке, использованной этим игроком, и стратегии с номером j, выбранной игроком P2.

Введя случайный механизм выбора, мы фактически расширили исходную модель. В этом расширении игрок P2 по-прежнему выбирает стратегию с некоторым номером j (j=1,2). Но выбор стратегии i (i=1,2) первого игрока осуществляется случайным механизмом. Игрок P1, задавая число x $$(0\le x \le 1$$ ), выбирает лишь распределение вероятностей для этого случайного механизма, но не конкретную стратегию i. Это распределение называют смешанной стратегией первого игрока, поскольку ее реализация во многих партиях игры порождает некоторую "смесь" стратегий i=1 и i=2.

Поскольку при x=1 случайный механизм рождает (с единичной вероятностью) выбор i=1, а при x=0 - выбор i=2, то прежние стратегии реализуются и при игре в смешанных стратегиях. Для различения смешанных стратегий игрока P1 и стратегий i=1 и i=2, которые он использовал в исходной игре, последние обычно называют чистыми стратегиями.

Проведем анализ ядра (10.1), соответствующего расширению исходной игры путем введения смешанных стратегий первого игрока. Выбирая конкретное значение $$x\in [0,1]$$, игрок P1 гарантирует себе следующее значение математического ожидания полезности исхода:$$\begin{gathered} \min\{M(x,j)\colon j = 1,2\} = \min \{x(a_{1j} - a_{2j}) + a_{2j}\colon j = 1,2\} = \\ = \min \{2x - 1,1-2x\}. \end{gathered}$$

Графики на рис. 2.7 представляют отрезки прямых линий 2x-1 и 1-2x, причем нижняя огибающая этого семейства, соответствующая правой части равенства (10.2), выделена жирными линиями. Как следует из этого рисунка, при любом значении x, не совпадающем с нулем или единицей, справедливо неравенство:$$\min \{2x - 1, 1 -2x\} > -1,\ 0 < x < 1.$$

Т.е. любая смесь стратегий гарантирует стороне P1 математическое ожидание полезности, превосходящее нижнюю цену игры. При этом выбор значения $$x^\ast = \frac{1}{2}$$ позволяет повысить этот гарантированный уровень до нулевого значения:$$\max_{0 \le x \le 1} \min_{1 \le j \le 2} M(x,j) = \max_{0 \le x \le 1} \{2x - 1, 1 -2x\} = 0.$$

Пусть теперь второй игрок также выбирает свою чистую стратегию с помощью рулетки, задаваемой распределением вероятностей (y,1-y), где $$0 \le y \le 1$$. Математическое ожидание выигрыша первого игрока (т.е. ядро игры) в этом (полном) смешанном расширении исходной игры определяется выражением:$$M(x,y) = (2x-1)y + (1-2x)(1-y) = (2x-1)(2y-1),$$ при вычислении которого учтена независимость случайных выборов, осуществляемых сторонами. Очевидна справедливость неравенств$$(\forall x,y \in [0,1]) M(x, \frac{1}{2}) \le M(\frac{1}{2}, \frac{1}{2}) \le M(\frac{1}{2}, y),$$ из которых следует, что ядро смешанного расширения исходной игры имеет седловую точку$$(x^\ast, y^\ast) = (\frac{1}{2}, \frac{1}{2})$$ (см. определение седловой точки в лекции 6), которой соответствует нулевая цена игры. Заметим, что указанная цена игры есть математическое ожидание полезности исхода. Конкретное значение выигрыша игрока P1 в любой партии игры может быть равно либо +1, либо -1.

Таким образом, смешанное расширение рассмотренной игры, не имевшей устойчивых решений в чистых стратегиях, имеет устойчивое (и эффективное) решение в смешанных стратегиях. Как будет показано в следующем параграфе, этот вывод носит общий характер (т.е. он не связан с конкретными значениями элементов матрицы из рассмотренного примера). Указанный вывод в сочетании с доказанной выше теоремой (см. лекцию 9) можно интерпретировать следующим образом. Достаточным условием существования устойчивых (по Нэшу) решений матричной игры является равная информационная обеспеченность игроков. Либо обе стороны располагают информацией обо всех сделанных выборах (что соответствует игре с полной информацией), либо обе стороны не могут достоверно прогнозировать решения друг друга (что обеспечивается использованием смешанных стратегий). Как мы увидим ниже, этот вывод справедлив и для биматричных игр.

Замечание 2.4. Поскольку, согласно (10.3)$$(\forall x, y \in [0,1]) M(x^\ast, y) = M(x, y^\ast) = v = 0,$$ то для достижения сторонами математического ожидания полезности, равного цене игры v в смешанных стратегиях, достаточно, чтобы лишь одна из сторон использовала свою оптимальную смешанную стратегию, являющуюся компонентой седловой точки. При этом нужно, чтобы другая сторона имела гарантию, что использование этой оптимальной стратегии действительно имеет место. Именно так и происходит традиционная игра в орлянку. Один из игроков осуществляет бросание симметричной монеты, а другой загадывает, каким будет исход бросания (т.е. использует чистую стратегию). Факт бросания симметричной монеты одним из игроков наблюдаем другим игроком.

Существование устойчивых решений в смешанных расширениях 2 x 2 игр

Обобщим результаты рассмотрения конкретного примера на случай смешанного расширения произвольной $$2\times 2$$ биматричной игры. Обозначим элементы матриц первой и второй сторон соответственно через aij} и bij $$(1\le i,\, j \le 2)$$. Примем, что сторона P1 использует смешанную стратегию (x,1-x), $$0\le x \le 1$$, а сторона P2 - смешанную стратегию (y,1-y), $$0 \le y \le 1$$. Смешанные стратегии (x,1-x), (y,1-y), выбранные сторонами P1, P2, однозначно описываются парой вещественных чисел (x,y), принадлежащей единичному квадрату$$D = \{(x,y)\colon 0 \le x, y \le 1\}.$$

Математическое ожидание M1(x,y) выигрыша стороны P1, соответствующее паре (x,y) (с учетом независимости выборов, порождаемых рулетками сторон), определяется выражением$$\begin{gathered} M_1 (x,y) = [a_{11} x + a_{21}(1 - x)]y + [a_{12}x + a_{22}(1 - x)](1- y)=\\ = xy (a_{11} - a_{12} - a_{21} + a_{22}) - x(a_{22} - a_{12}) - y(a_{22} - a_{21}) + a_{22}, \end{gathered}$$ или$$M_1(x,y) = Axy - ax + f(y),$$ где$$\begin{gathered} A = a_{11} - a_{12} - a_{21} + a_{22},\quad a = a_{22} - a_{12},\\ f(y) = a_{22} - y(a_{22} - a_{21}). \end{gathered}$$

Аналогичные вычисления дают выражение для математического ожидания M2(x,y) выигрыша стороны P2:$$M_2(x,y) = Bxy - by + g(x),$$ $$B = b_{11} - b_{12} - b_{21} + b_{22},\quad b = b_{22} - b_{21},$$ $$g(x) = b_{22} - x(b_{22} - b_{12}).$$

Теперь вопрос о существовании пары (x*,y*), определяющей устойчивое (по Нэшу) решение (x*,1-x*), (y*,1-y* ) в смешанном расширении$$M_i(x,y),\quad i = 1,2,\quad 0 \le x,\ y \le 1,$$ исходной $$2\times 2$$ биматричной игры, сводится к вопросу о существовании решения $$(x^\ast, y^\ast) \in D$$ системы неравенств:$$(\forall x \in [0,1])\, M_1 (x^\ast, y^\ast) \ge M_1(x, y^\ast),$$ $$(\forall y \in [0,1])\, M_2 (x^\ast, y^\ast) \ge M_2(x^\ast, y).$$ Условия (10.10), (10.11) могут быть существенно упрощены.

Лемма 2.1. Для выполнения соответствующего паре (x*,y*) континуума неравенств (10.10) необходима и достаточна справедливость двух неравенств:$$M_1 (x^\ast, y^\ast) \ge M_1(0, y^\ast),\quad M_1 (x^\ast, y^\ast) \ge M_1(1, y^\ast).$$ Аналогично, для выполнения условий (10.11) необходима и достаточна справедливость неравенств:$$M_2 (x^\ast, y^\ast) \ge M_2(x^\ast, 0),\quad M_2 (x^\ast, y^\ast) \ge M_2(x^\ast, 1).$$

Доказательство Покажем эквивалентность условий (10.10) и (10.12). Эквивалентность условий (10.11) и (10.13) доказывается аналогично. Подстановка значений x=0 и x=1 в условия (10.10) дает неравенства (10.12). Т.е. необходимость отношений (10.12) действительно имеет место.

Пусть выполняются условия (10.12). Из линейности по x выражения (10.5) для величины M1(x,y) следует, что при любом значении $$x \in [0, 1]$$$$M_1(x, y^\ast) = M_1[1 \cdot x + 0 \cdot (1 - x), y^\ast] = x M_1 (1, y^\ast) + (1 - x)M_1(0, y^\ast).$$ Отсюда, учитывая сделанное предположение о справедливости неравенств (10.12), выводим истинность отношения$$M_1(x, y^\ast) \le M_1 (x^\ast, y^\ast),$$ что и доказывает выполнение условий (10.10). Таким образом, достаточность также установлена.

Теорема 2.2 (о существовании устойчивых решений в смешанном расширении $$2\times 2$$ биматричной игры. Каждая $$2\times 2$$ биматричная игра имеет устойчивое (по Нэшу) решение в смешанных стратегиях.

Доказательство 1. Определим множество всех пар $$(x, y) \in D$$, удовлетворяющих неравенствам (10.12), которые, согласно доказанной лемме, эквивалентны условиям (10.10).

При x=0 из выражения (10.5) и из первого неравенства в (10.12) следует справедливость отношения$$x^\ast (Ay^\ast - a) \ge 0.$$

Аналогично, из второго неравенства в (10.12) (для случая x=1 ) вытекает оценка$$(1 - x^\ast)(Ay^\ast - a) \le 0.$$

Найдем множество всех решений системы (10.14), (10.15), лежащих в единичном квадрате D из (10.4).

При x*=0 условие (10.14) необходимо выполняется и, следовательно, все пары вида$$(0, y^\ast),\quad Ay^\ast \le a ,\quad 0 \le y^\ast\le 1,$$ являются решениями системы (10.14), (10.15).

Аналогично, при x*=1 необходимо выполняется условие (10.15) и все пары вида$$(1, y^\ast),\quad Ay^\ast \ge a,\quad 0 \le y^\ast \le 1,$$ являются решениями рассматриваемой системы (10.14), (10.15).

Наконец, при 0<x*<1 множество решений системы (10.14), (10.15) состоит из пар вида$$(x^\ast, y^\ast),\quad Ay^\ast = a,\quad 0 < x^\ast < 1,\quad 0 \le y^\ast \le 1.$$

Теперь рассмотрим выполнимость полученных условий (10.16)-(10.18) в зависимости от значений величин a и A из (10.06). При a=A=0 любая пара $$(x^\ast, y^\ast) \in D$$ удовлетворяет условиям (10.16)-(10.18) и, следовательно, является решением (10.10).

При A=0 и $$a\ne 0$$ возможны два случая, которым соответствуют два верхних фрагмента на рис. 2.8. При a>0 все точки, лежащие на левой стороне (выделена жирной линией на левом верхнем фрагменте) квадрата D, являются решениями системы (10.10). При a<0 этим свойством обладают все точки, лежащие на правой стороне квадрата D (см. правый верхний фрагмент на рис. 2.8).

Пусть $$A \ne 0$$. Тогда, согласно (10.16), все решения вида $$(0, y^\ast) \in D$$ возможны лишь при условии, что $$y^\ast \le \alpha$$ (если A>0 ) или $$y^\ast \ge \alpha$$ (если A<0 ), где$$\alpha = a/A.$$

Аналогично, из (10.17) выводим, что все решения вида $$(1, y^\ast) \in D$$ возможны лишь при выполнении условия $$y^\ast \ge \alpha$$ (если A>0 ) или при выполнении условия $$y^\ast \le \alpha$$ (если A<0 ). Наконец, согласно (10.18), решения вида $$(x^\ast, \alpha) \in D$$, 0<x*<1, возможны лишь в случаях, когда $$0 \le \alpha \le 1$$. Случаю A>0 соответствует левый фрагмент второго (сверху) ряда на рис. 2.8. При этом все точки из D, удовлетворяющие условиям (10.10), лежат на жирной ломаной линии, составленной из трех отрезков. Два вертикальных отрезка представляют точки вида (0,y*) и (1,y*). Горизонтальный отрезок является образом точек вида $$(x^\ast, \alpha)$$, 0<x*<1. Правый фрагмент из этого же ряда соответствует случаю A<0, $$0 < \alpha < 1$$.