Метод вычисления оптимальных стратегий

Введение

Квазиматричные игры относятся к некоторому специальному классу позиционных антагонистических игр двух лиц со случайным ходом.

Игроками I и II, как и в матричных играх, являются противники, преследующие прямо противоположные цели и имеющие конечное число возможных вариантов действий. Случайный ход делает " природа ", которая, не преследуя какой-либо цели (в силу объективных факторов, независимых от воли игроков), выбирает из конечного множества одну альтернативу. Такой выбор представляет собой случайный ход . Наличие "природы" как третьего игрока приводит теоретико-игровую задачу к классу позиционных игр, так как в этом случае число последовательных ходов будет всегда более двух. При этом если оба игрока не знают, какой ход сделает "природа", то такая игра в нормальной форме является матричной игрой. Однако анализ конфликтных ситуаций, моделью которых является конечные игры, показывает, что в целом ряде случаев стороны имеют различную информацию о ходах "природы". Так, например, I может знать, а игрок II — не знать, какой ход сделает "природа". Такие игры и называются квазиматричными .

Описание квазиматричной игры

Правила квазиматричной игры формулируются следующим образом.

Пусть функция выигрыша игрока I задана множеством матриц

$$\left{ A_k=||a_{ij}^{(k)}|| \right}$$

для $$k=(1,2,...,r); i=(1,2,...,m)$$ и $$j=(1,2,...,n)$$, где $$k,i$$ и $$j$$ — альтернативы "природы", игрока I и игрока II соответственно.

Из множества альтернатив "природы" случайным образом выбирается число $$k$$, которое сообщается только игроку I. Последний, зная матрицу $$A_k=||a_{ij}^{(k)}||$$, выбирает число $$i$$. В отличие от него игрок II должен выбрать число $$j$$, зная только множество $$\{k\}$$ и распределение вероятности $$P_k$$, в соответствии с которым выбирается число $$k$$. В связи с этим игрок II не может применить свою оптимальную стратегию, которая вычисляется в зависимости от $$A_k=||a_{ij}^{(k)}||$$.

Игрок I, зная последнее обстоятельство, может использовать его в своих интересах и увеличить выигрыш. Игроку II тогда остается только не дать игроку I увеличить выигрыш более, чем это обусловлено разными объемами информации о функции выигрыша.

Для осуществления наилучшим образом своих интересов в квазиматричной игре игроки должны стремиться к ситуациям равновесия, то есть придерживаться своих оптимальных стратегий. Тогда значением квазиматричной игры $$\bar{\nu}$$ будет тот наибольший выигрыш, который игрок I может себе обеспечить (или, что то же самое, те наибольшие потери игрока II, которые он вынужден понести), если каждый из них придерживается своей оптимальной стратегии.

Решение квазиматричных игр

Пусть игрок II знает априорные вероятности $$P_1,P_2,...,P_k,...,P_{\gamma}$$ появления значений функций выигрыша:

$$a_{ij}^{(1)},a_{ij}^{2},...,a_{ij}^{k},...,a_{ij}^{\gamma}$$.

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

В квазиматричной игре на первом этапе делает ход "природа", которую обозначают числом 0. Следовательно, начальным узлом дерева будет кружок с числом 0 и информационным множеством $$\{q_0\}$$, состоящим из одного элемента $$q_0$$.

Из начального узла проводится s отрезков, каждый из которых соответствует матрице $$A_k$$ с вероятностью $$P_k(k=1,2,...,r)$$. На втором этапе делает ход игрок, имеющий полный объем информации. Следовательно, в каждой точке разветвления дерева на втором этапе имеется одно информационное множество $$\{q_k\}$$, состоящее из одного элемента $$q_k$$. Из каждого узла второго этапа проводится m отрезков, каждый из которых соответствует $$i$$ -ому ходу игрока, имеющего полный объем информации. Выбор этого игрока приводит к ситуации второго этапа, на котором делает ход игрок, имеющий неполный объем информации (он не знает, какой ход сделан на первом и втором этапах). Следовательно, этот игрок имеет только одно информационное множество, включающее все узлы третьего этапа. Выбор хода на третьем этапе приводит к одной из заключительных ситуаций, когда функция выигрыша принимает значение $$a_{ij}^{(k)}$$, если игра закончится в $$k$$ - вершине. Эту функцию выигрыша называют функцией выигрыша партии, так как она определяет выигрыш игрока I для конкретной партии.

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

Игрок I имеет полную информацию о ходах "природы". Поэтому его стратегия должна определять, какой отрезок дерева игры выбирается в $$k$$ -м узле. Например, одной из стратегий игрока I является выбор в каждом узле отрезка 1. Другая стратегия игрока – выбор отрезка с наибольшим номером, то есть отрезка $$m$$, и так далее. Поскольку у игрока I имеется r различных информационных множеств, которые имеют номера $$1,2,...,k,...,r$$, то любую стратегию игрока I можно изобразить набором $$r$$ различных информационных множеств, которые имеют номера $$1,2,...,k,...,r$$, то любую стратегию игрока I можно изобразить набором $$r$$ чисел, где $$k$$ -е число изображает отрезок, выбранный, когда партия достигает $$k$$ -го информационного множества. Таким образом, наборы из $$r$$ целых чисел

$$(i_1,i_2,...,i_k,...,i_r)$$

изображают стратегию игрока I. Например, стратегия, при которой всегда выбирается отрезок 1, изображается как

$$(1,1,1,...,1,...1)$$.

Обозначим множество стратегий игрока I через $$S(i_1,i_2,...,i_r)$$. Можно установить, что $$S(i_1,i_2,...,i_r)$$ — функция, указывающая игроку I выбор числа $$i$$ в зависимости от выбранного числа $$k$$ на первом этапе. Так, например, стратегия $$S(1,1,1,… 1,…1)$$ состоит в том, чтобы выбрать ход 1 независимо от того, какой ход сделан на первом этапе. Другая возможность стратегия $$S(1,1,2,… 1,…1)$$ определяет выбор хода 2, если на первом этапе сделан ход 3, и хода 1 во всех остальных случаях.

Игрок II, делающий ход на третьем этапе, не имеет информации о сделанных ходах на первом и втором этапах, поэтому его стратегия определяет только выбор числа $$j$$. Следовательно, множество стратегий этого игрока запись следующим образом:

$$S_j=(0,0,0,0,0,1,0,0,0)\text{ для j }=(1,2,...,n)$$.

На основании изложенного видно, что стратегией игрока является функция, которая определена для каждого информационного множества, соответствующего игроку. Значение стратегии для каждого такого информационного множества представляет один из возможных ходов, имеющихся у игрока. Следовательно, число стратегий игрока будет определяться числом его информационных множеств и возможных ходов. Для игрока, имеющего полный объем информации, оно будет равно $$m^r$$ (поскольку $$i_k$$ пробегает m значений и имеется $$r$$ значений числа $$i_k$$ ), а для игрока, не имеющего информации о сделанных ходах на предыдущих этапах, будет равно $$n$$.

Каждая пара стратегий $$(S_{(i_1,...,i_{\gamma})},S_j)$$ определяет математическое ожидание функции выигрыша $$a_{(i_1,...,i_{\gamma})j}$$ позиционной игры с неполной информацией:

$$a_{(i_1,i_2,...,i_{\gamma})j}=\sum\limits_{k=1}^{\gamma}a^{(k)}_{i_kj}P_k$$.

Вычисление $$a_{(i_1,...,i_{\gamma})j} $$ дает возможность составить нормализованную форму позиционной квазиматричной игры $$(m^{\gamma}\times n)$$ матрицу

$$A_k^{\prime}=||a_{(i_1,...,i_{\gamma})j}||$$.

Решение игры, матрица которой равна $$A_k^{\prime}$$ определяет оптимальные смешанные (в общем случае) стратегии $$x$$ и $$y$$ игроков I и II соответственно, а также значение игры $$\bar{\nu}$$.

Очевидно, что вектор оптимальной смешанной стратегии игрока I можно записать следующим образом:

$$x=\{x(S_{(i_1,...,i_{\gamma})})\}$$,

где $$x(S_{(i_1,...,i_{\gamma})})$$ — вероятность применения $$S_{(i_1,...,i_{\gamma})}$$ чистой стратегии. Тогда вектор оптимальной смешанной стратегии игрока II будет

$$y=\{y(S_j)\}$$,

где $$y(S_j)$$ — вероятность применения $$S_j$$ чистой стратегии. Соответственно значение игры $$\bar{\nu}$$ будет равно

$$\sum\sum a_{(i_1,...,i_{\gamma})j}x(S_{(i_1,...,i_{\gamma})}y(S_j))$$.

Однако найденное решение $$x,y$$, по крайней мере для игрока I, еще не является решением квазиматричной игры. Действительно, смешанная стратегия $$x$$ определяет лишь распределение вероятностей чистых стратегий игрока I в позиционной игре, и не более. В связи с этим воспользуемся понятием стратегия поведения.

Под стратегией поведения игрока понимается распределение вероятностей по альтернативам, определенное для каждого его информационного множества.

Можно представить себе каждую чистую стратегию как книжку инструкций, в которой каждая страница относится лишь к одному информационному множеству и точно устанавливает, что нужно делать в этом информационном множестве. Множество стратегий соответствует библиотеке таких книг. Смешанная стратегия выбирает одну книгу из библиотеки посредством случайного механизма с распределением вероятностей, совпадающим с распределением вероятностей смешанной стратегии. Стратегия поведения представляет книгу другого рода, хотя каждая страница также относится к одному информационному множеству, она устанавливает распределение вероятностей по альтернативам этого множества, а не конкретный выбор (Н.Н. Воробьев. Бесконечные антагонистические игры//М., Изд-во физико-математической литературы, 1967. С.300).

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

Как показал Г. Кун (Позиционные игры//Сб. под ред. Н.Н. Воробьева, М. "Наука" , 1987. ), для игр с полной памятью, а квазиматричные игры являются таковыми, всякая смешанная стратегия эквивалентна некоторой стратегии поведения. Следовательно, в квазиматричных играх всегда существует оптимальная стратегия поведения.

Метод вычисления оптимальных стратегий в квазиматричных играх реализованы в .NET на языке программирования C# (Институт вычислительной математики и математической геофизики СО РАН).

Применение метода : экономика;
                    военное дело.

Вычисление оптимальных стратегий в биматричных играх

Описание биматричной игры. Все игры которые были рассмотрены, относились к классу игр с нулевой суммой. Однако ряд конфликтных ситуаций, складывающихся в ходе действий, характерны тем, что выигрыш одной стороны не равен в точности проигрышу другой. Теоретико-игровыми моделями подобных ситуаций являются некооперативные игры с ненулевой суммой. Такие игры называются биматричными, потому что задание каждой такой игры сводится к заданию двух матриц $$A$$ и $$B$$ одинаковой формы: $$A=||a_{ij}||; B=||b_{ij}|| при i=1,...m; j=1,...,n$$.

Процесс биматричной игры состоит в независимом выборе игроком I числа $$i$$ а игроком II — числа $$j$$, после чего игрок I получает выигрыш $$a_{ij}$$, а игрок II — выигрыш $$b_{ij}$$.

Номера строк матриц $$A$$ и $$B$$ назовем чистыми стратегиями игрока I, а номера столбцов этих матриц – чистыми стратегиями игрока II. Тогда пары вида $$(i,j)$$ будут являться ситуациями в чистых стратегиях биматричной игры, а числа $$a_{ij}$$ и $$b_{ij}$$ — выигрышами I и II игроков в ситуации $$(i,j)$$. Соответственно, распределение вероятностей применения чистых стратегий игрока I — $$x=(x_1,...,x_m)$$ и игрока II — $$y=(y_1,...,y_n)$$ будем называть смешанными стратегиями. Тогда пары вида $$(x,y)$$ представляют ситуации биматричной игры в смешанных стратегиях, а числа $$\sum\limits_{i=1}^{m}\sum\limits_{j=1}^{n}a_{ij}x_iy_j$$ и $$\sum\limits_{i=1}^{m}\sum\limits_{j=1}^{n}b_{ij}x_iy_j$$ являются математическими ожиданиями выигрыша I и II игроков.

Ситуацией равновесия биматричной игры в смешанных стратегиях будем называть такую пару $$(x^*,y^*)$$, при которой:

$$\nu_I=\sum\limits_{i=1}^{m}\sum\limits_{j=1}^{n}a_{ij}x^*_iy^*_j \ge \sum\limits_{i=1}^{m}\sum\limits_{j=1}^{n}a_{ij}x_iy^*_j;\\ \nu_{II}=\sum\limits_{i=1}^{m}\sum\limits_{j=1}^{n}b_{ij}x^*_iy^*_j \ge \sum\limits_{i=1}^{m}\sum\limits_{j=1}^{n}b_{ij}x_iy^*_j$$,

где $$\nu_I$$ — математическое ожидание выигрыша игрока I;

$$\nu_{II}$$ — математическое ожидание выигрыша игрока II;

$$x^*$$ — оптимальная смешанная стратегия игрока I;

$$y^*$$ — оптимальная смешанная стратегия игрока II.

Задача

Построение и решение биматричной игры. Предположим, что противолодочная подводная лодка страны $$L$$ осуществляет поиск ракетной подводной лодки государства $$R$$, которая маневрирует в строго определенной части района боевого патрулирования. В остальной части этого района действует противолодочная подводная лодка $$R$$, которая осуществляет поиск противолодочной подводной лодки $$L$$. Пусть каждая противолодочная лодка для обнаружения противника может использовать свою гидроакустическую станцию или в активном режиме, включая ее периодически, или только в пассивном режиме, выполняя непрерывный поиск.

Как противолодочная подводная лодка $$L$$, так и ракетная подводная лодка $$R$$ с обнаружением сигналов гидролокатора может уклониться от противника. Однако периодичность включения гидролокатора делает обнаружение возможным, но недостоверным.

В подобной конфликтной ситуации одним из игроков является противолодочная подводная лодка $$L$$, а другим — противолодочная подводная лодка $$R$$.Очевидно, ракетная подводная лодка не может быть игроком, так как она имеет только один способ действий, заключающийся в скрытом маневрировании и выполнении уклонения с обнаружением сигналов гидролокаторов.

Характерным здесь является то, что каждый из игроков преследует разные, но не противоположные цели. Действительно, целью противолодочной подводной лодки $$L$$ является обнаружение ракетной подводной лодки, а целью противолодочной подводной лодки $$R$$ — обнаружение противолодочной подводной лодки $$L$$. Поэтому для оценки достижения цели каждым из игроков в зависимости от выбранных способов действий (стратегий) необходимо иметь два критерия эффективности и соответственно две функции выигрыша. Тогда моделью подобной конфликтной ситуации будет конечная игра с ненулевой суммой, описываемая двумя матрицами одинаковой формы $$A=||a_{ij}||$$ и $$B=||b_{ij}||$$, называемая биматричной.

Примем за критерий эффективности противолодочной подводной лодки $$L$$ (игрок I ) вероятность обнаружения ракетной подводной лодки $$(a_{ij})$$, а за критерий эффективности противолодочной подводной лодки $$R$$ (игрок II ) – вероятность обнаружения противолодочной подводной лодки $$L(b_{ij})$$. Тогда биматричная игра будет задана матрицей $$A$$ (рисунок 9.a) и матрицей $$B$$ (рисунок 9.b).

Где $$i=j=1$$ — использование активного режима;

$$i=j=2$$ — использование пассивного режима.

Для решения полученной биматричной игры $$(2 \times 2)$$ достаточно задать значения вероятностей $$a_{ij}$$ и $$b_{ij}$$.

Пусть для конкретных значений вероятностей $$a_{ij}$$ и $$b_{ij}$$ биматричная игра задана матрицами $$A$$ (рис. 8.c) и $$B$$ (рис. 8.d).

Из анализа матриц $$A$$ и $$B$$ устанавливаем, что $$i_0=1$$ и $$j_0=1$$, то есть игроки осуществляют ситуацию равновесия в чистых стратегиях, так как максимальные элементы матриц $$A$$ и $$B$$ принадлежат паре $$(1,1)$$.

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