14.2. Чистые и смешанные стратегии и их свойства.

Если первый игрок имеет т стратегий, а второй – n стратегий, то для любой пары стратегий первого и второго игроков чистые стратегии можно представить в виде единичных векторов. Например, для пары стратегий A1, В2 чистые стратегии первого и второго игроков запишутся в виде: p1=(1;0;...;0), q2=(0;1;0;...;0). Для пары стратегий Аi Вj чистые стратегии можно записать в виде:

рi=(0;...;0;;0;...;0),

qj=(0;…;0; ;0;...;0).

Теорема 1. В матричной игре нижняя чистая цена игры не превосходит верхней чистой цены игры, т.е. ???.

¦ По определению ?i=аij?аij. Аналогично ?j=аij?аij. Объединив эти соотношения, получим: ?i=аij?аij?аij=?j. Отсюда ?i?аij??j или ?i??j (i=l,…,m; j=1,…,п). Это неравенство справедливо для любых i и j, следовательно, ???.                                                      ?

Если для чистых стратегий Аi, Bj игроков А и В соответственно имеет место равенство ?=?, то пару чистых стратегий (Ai,Bj) называют седловой точкой матричной игры, элемент аij матрицы, стоящий на пересечении i-й строки и j-гo столбца, – седловым элементом платежной матрицы, а число v=?=? – чистой ценой игры.

Пример 4. Найдём нижнюю и верхнюю чистые цены, установим наличие седловых точек матричной игры .

¦ Определим нижние и верхние чистые цены игры (табл. 3):

?=?i=max(5,1,-4)=5, ?=?j=min(9,5,6,8)=5, v=?=?=5.

В данном случае имеем одну седловую точку (A1,B2), а седловой элемент равен 5. Этот элемент является наименьшим в 1-й строке и наибольшим во 2-м столбце. Отклонение игрока А от максиминной стратегии A1 ведет к уменьшению его выигрыша, а отклонение игрока В от минимаксной стратегии B2 ведет к увеличению его проигрыша. Иными словами, если в матричной игре имеется седловой элемент, то наилучшими для игроков являются их минимаксные стратегии. И эти чистые стратегии, образующие седловую точку и выделяющие в матрице игры седловой элемент а12=5, есть оптимальные чистые стратегии A1 и B2 игроков А и В.                                                                          ?

Если же матричная игра не имеет седловой точки, то решение игры затрудняется. В этих играх ?lt;?. Применение минимаксных стратегий в таких играх приводит к тому, что для каждого из игроков выигрыш не превышает ?, а проигрыш – не меньше ?. Для каждого игрока возникает вопрос увеличения выигрыша (уменьшения проигрыша). Решение находят, применяя смешанные стратегии. Смешанной стратегией первого (второго) игрока называется вектор р=(p1;... ;рт), где

рi?0 (i=1,…,т) и =1 (q=(q1; … ;qn), где qj?0 (j=l,…,n) и =1). Вектор р (q) означает вероятность применения i-й чистой стратегии первым игроком (j-й чистой стратегии вторым игроком).

Таблица 3 B1 B2 B3 B4 ?i А1 А2 А3 9 1 6 5 4 3 6 3 2 7 8 -4 5 1 -4 ?j 9 5 6 8

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

f(p,q)=.

Функция f(p,q) называется платежной функцией игры с матрицей (аij)m?n.

Стратегии р*=(;… ; ), q*=(;… ;) называются оптимальными, если для произвольных стратегий р=(p1;... ;рт), q=(q1; … ;qn) выполняется условие

f(p,q*)?f(p*,q*)?f(p*,q).                                  (3)

Использование в игре оптимальных смешанных стратегий обеспечивает первому игроку выигрыш не меньший, чем при использовании им любой другой стратегии р, второму игроку – проигрыш, не больший, чем при использовании им любой другой стратегии q.

Совокупность оптимальных стратегий и цены игры составляет решение игры.

Значение платежной функции при оптимальных стратегиях определяет цену игры v, т.е. f(p*,q*)=v.

Теорема 2 (теорема Неймана). В смешанных стратегиях любая конечная матричная игра имеет седловую точку.

Пусть имеем матричную игру (аij)m?n и некоторые смешанные оптимальные стратегии p*,q* игроков А и В, обеспечивающие сумму выигрыша v. Вопрос поставим так: как проверить, что набор (p*,q*,v) является решением игры? Для этого нужно проверить справедливость неравенства (3) для любых смешанных стратегий, среди которых и будут стратегии p*,q*. Однако различных смешанных стратегий, среди которых и оптимальные, имеем бесчисленное множество. И в таком случае проверить справедливость неравенства (3) невозможно. Поэтому рассмотрим следующую теорему, которая позволит ответить на поставленный выше вопрос.

Теорема 3. Для того чтобы смешанные стратегии р*=(;… ; ) и q*=(;… ;) были оптимальными для игроков А и В в игре с матрицей (аij)m?n выигрышем v, необходимо и достаточно выполнения неравенств:

?v (j=l,…,n),                                              (4)

?v (i=l,…,m).                                              (5)

¦ Пусть р*, q* – оптимальные смешанные стратегии.

?v?                                      (6)

В правую часть соотношения (6) подставим вектор

qj=(q1;...;qj-1;qj;qj+1,...;qп)=(0;... ;0;1;0;... ;0).

Получим

==?v,

т.е. оптимальная стратегия р* удовлетворяет неравенству (4).

Если вместо произвольного вектора р в левую часть соотношения (6) подставить вектор р(i)=(p1;... ,pi-1,pi, рi+1, …;рт)=(0;...;0;1;0;...;0), то можно показать, что и оптимальная стратегия q* удовлетворяет соотношению (5).

Итак, доказано условие необходимости, а именно: если стратегии р* и q* оптимальные, то они должны удовлетворять соотношениям (4) и (5).

Теперь докажем достаточность этого условия. Пусть выполняются неравенства (4), (5). Покажем, что p*,q* – оптимальные стратегии. Для этого нужно показать выполнимость соотношения (6). С учетом соотношения (4) преобразуем правую часть, а с учетом соотношения (5) – левую часть соотношения (6.

Пусть q=(q1;...;qп) – произвольный вектор, тогда

=?=v=v?1=v,

т.е. ?v.

Преобразуя левую часть соотношения (6) для произвольного вектора р=(p1; ... ;pт), получаем

=?=1 v=v,

т. е. ?v.

Итак, доказано, что если выполняются соотношения (4), (5), то выполняется и (6), т.е. смешанные стратегии р* и q* – оптимальные.?

Таким образом, для проверки того, что набор (р*,q*,v) является решением матричной игры, достаточно проверить, удовлетворяют ли р*,q* неравенствам (4) и (5) и уравнениям =1 и =1.

На основании теоремы 3 можно сделать вывод: если игрок А применяет оптимальную смешанную стратегию р*, а игрок В – любую чистую стратегию Bj, то выигрыш игрока А будет не меньше цены игры v. Аналогично: если игрок В использует оптимальную смешанную стратегию q*, а игрок А – любую чистую стратегию Аi, то проигрыш игрока В не превысит цены игры v.

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

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

¦ Пусть в матричной игре (аij)m?n имеем оптимальные стратегии игроков А и В соответственно р* и q*. Цена игры равна v. При этом игрок А имеет r активных стратегий, а игрок В – k активных стратегий. Расположив активные стратегии для игроков первыми, будем иметь: р*=(;… ;;0;….;0) и q*=(;…;;0;...;0), для которых =1 и =1.

Пусть игрок А придерживается своей оптимальной стратегии р*, а игрок В – чистой стратегии, тогда, согласно теореме 3,

?v (j=1,…,k).                                            (7)

Если игроки А и В используют свои оптимальные стратегии, то выигрыш игрока А равен цене игры v, т. е. v=.

Учитывая соотношение (7), получаем

v==?=v.                  (8)

Соотношение (8) выполнимо лишь в случае, когда неравенства (7) превращаются в равенства. Отсюда можно сделать вывод, что для любой смешанной стратегии q*=(;…;;0;...;0) выполняется равенство =v, что и доказывает теорему.                                        ?

На основании данной теоремы решение матричной игры можно упростить, выявив при этом доминирование одних стратегий над другими. Так, рассматривая стратегии игрока А, сравниваем элементы строк s и t, а именно: asj с элементами atj для j=l,…,n. Если asj?atj (j=1,…,п), то выигрыш игрока А при стратегии Аs будет больше, чем при стратегии Аt. В этом случае стратегия Аs доминирует над стратегией Аt. Стратегию Аs называют доминирующей, а стратегию Аt – доминируемой.

Поскольку игрок В заинтересован в минимизации проигрыша, доминирующим будет столбец с наименьшими элементами. Например, сравниваем элементы r-го и l-го столбцов. Если все элементы air?ail (i=1,…,m), то игроку В свой выбор выгодно сделать по l-му столбцу. В этом случае стратегия Вl игрока В доминирует над стратегией Вr. Стратегия Вl называется доминирующей, а стратегия Вr – доминируемой.

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

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

Теорема 5. Оптимальные смешанные стратегии р* и q* соответственно игроков А и В в матричной игре (aij)m?n с ценой v будут оптимальными и в матричной игре (baij+с)m?n с ценой v'=bv+с, где bgt;0.

¦ На основании теоремы 3 для оптимальной смешанной стратегии р* игрока А и для любой чистой стратегии Вj игрока В имеем

?v (j=l,…,n)                                              (9)

Умножим обе части неравенства (9) на некоторое положительное число bgt;0 и к обеим частям полученного неравенства прибавим произведение с. Получим

+c?bv+с (j=l,…,n).                  (10)

Так как =1, соотношение (10) примет вид

?bv+с (j=l,…,n)

или

?v' (j=l,…,n),

где v'=bv+c. Теорема доказана для оптимальной смешанной стратегии р* игрока А.

Аналогично доказывается теорема и для оптимальной смешанной стратегии игрока В.                                                                               ?

На основании теоремы 5 платежную матрицу, имеющую отрицательные числа, можно преобразовать в матрицу с положительными числами.

Пример 5. Выполним все возможные упрощения матричной игры

.

¦ Поскольку соответствующие элементы второй и четвертой строк матрицы игры равны, т.е. имеем две дублирующие строки, опустим, например, четвертую строку: . Сравним соответствующие элементы столбцов. Элементы первого столбца доминируют над элементами третьего и шестого столбцов, а элементы второго столбца доминируют над соответствующими элементами четвертого столбца. Игроку В невыгодно применять стратегии B3, B4 и B6. Опускаем третий, четвертый и шестой столбцы и получаем матрицу . Элементы второй строки меньше соответствующих элементов третьей строки. Следовательно, игроку А невыгодна стратегия А2. Опуская вторую строку, получаем упрощенную матрицу .

Если требуется получить матрицу с положительными элементами, то достаточно прибавить к ее элементам, например, число 2.        ?