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

↑

▷ Содержание

⇐ ПредыдущаяСтр 11 из 15Следующая ⇒

Различают стратегии чистые и смешанные.

А. Чистая стратегия А_i(i = ) игрока А (чистая стратегия B_j (j = ) игрока В) – это возможный ход игрока А (в), выбранный им с вероятностью, равной 1.

Если игрок А имеет m-стратегий, а игрок В – n-стратегий, то для лю­бой пары стратегий игроков А и В чистые стратегии можно представить в виде единичных векторов, например: для пары стратегий А₁, В₂ чистые стратегии первого и второго игроков запишутся в виде:

для стратегии A₁;  = (1; 0;..; 0);

для стратегии В₂; g₂ = (0; 1; 0; …; 0).

Для пары стратегий А_i, В_j чистые стратегии можно записать в виде:

для стратегии А_i; p_i = (0;...; 0; 1; 0; …; 0)

                                              |® i-место;

для стратегии ; g_j = (0,..., 0; 1; 0; …; 0)

                                              |® j-место.

Теорема. В матричной игре нижняя чистая цена меньше или равна верхней чистой цене игры, т. е., α £ b.

Доказательство. Возьмем i – строку и j – столбец. По определению a _i = min a _ij, £ a_ij, а b _j = max a _ij ³ a _ij Þ a _i £ a _ij, £ b_j Þ a _i £ b _i,        

          j                               i

(i = , j = ).

Итак как это справедливо для любого i и j, то, следовательно   a £ b.

Если для чистых стратегий А_i, В_j игроков А и В имеет место равен­ство a = b, то пару чистых стратегий (А_i, В_j) называют седловой точкой матричной игры, элемент a _ij – седловым элементом платежной матрицы, а число u = a = b – чистой ценой игры.

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

Решение.

Определим нижние и верхние чистые цены игры, для этого составим платежную матрицу,

а седловой элемент равен а₁₂ = 5, этот элемент является наименьшим в первой строке и наибольшим во втором столбце.

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

Отклонение игрока А от maxmin стратегии А₁ ведет к уменьшению его выигрыша, а отклонение игрока В от минимаксной стратегии ведет к увеличению его проигрыша.

Б. Смешанные стратегии.

Если же матричная игра не имеет седловой точки, то решение игры затрудняется. В этих играх a < b. Применение минимаксных стратегий в таких играх приводит к тому, что для каждого из игроков выигрыш £ a, а проигрыш ³ b. Для каждого игрока возникает вопрос увеличения своего выиг­рыша. Решение находят, применяя смешанные стратегии.

Смешанной стратегией игрока А (В) называется вектор

, где  и

 где ,

Вектор  означает вероятность применения i -ой чистой страте­гии игроком А (j -ой чистой стратегии игроком В). Так как игроки выбирают свои стратегии случайно и независимо друг от друга, то величина выигрыша (проигрыша) есть случайная величина. Ее средняя величина – математическое ожидание – является функцией от смешанных стратегий и :

Функция  – называется платежной функцией игры.

Стратегии = ('р₁*,..., р_m*,), = (g₁^*, …, g_n*) называются оптималь­ными, если для произвольных стратегий = (р₁, р₂,..., р_m) и = (g₁, g₂, …, g_m) выполняется условие £  £ .

Использование в игре оптимальных смешанных стратегий обеспечивает игроку А выигрыш не меньший, чем при использовании им любой другой стратегии р, а 2-му игроку – проигрыш не больший, чем при использовании им любой другой стратегии. Совокупность оптимальных стратегий и цены игры составляет решение игры. Цена игры  Чистые стратегии игрока, входящие в его оптимальную смешан­ную стратегию с вероятностями неравными 0, называются активными стратегиями игрока.

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

1. Для того чтобы смешанные стратегии p*=(p₁^*, p₂^*, …, p_m^*) и g^* = (g₁^*, g₂^*, …, g_n^*) были оптимальными, для игроков А и B с ценой игры u должны выполняться неравенства:

2. Решение матричной игры можно упростить, выяснив при этом до­минирование одних стратегий над дру­гими. Рассмотрим стратегии игрока А, для этого сравним элементы строк s и t:

а) если все , то выигрыш игрока стратегии А_s будет больше, чем при стратегии А_t, тогда стратегия А_s называется доминирующей, а стратегия А_t – доминируемой;

б) игрок В заинтересован в минимизации проигрыша поэтому доминирующим будет столбец с меньшими элементами;

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

3. Платежную матрицу можно преобразовать в матрицу с положи­тельными числами, умножив все элементы матрицы на какое-либо число b или прибавив к ним какое-либо число с, то есть получив матрицу (b · a_ij + c) _{m × n}.

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

Решение:

а) поскольку соответствующие элементы второй и четвертой строк матрицы равны, то есть имеем две дублирующие строки, то опустим, например, четвертую строку. Получим

б) сравним соответствующие элементы строк и столбцов: элементы первого столбца доминируют (<) над элементами третьего и шестого столбцов, то есть игроку В невыгодно применять стратегии В₃ и В₆. Вычеркнем их. Элементы второго столбца доминируют (<) над элементами четвертого столбца. Опустим его. Получим:

в) элементы 2 строки меньше соответствующих элементов 3-й строки, т. е. 3-я строка доминирует над 2-й строкой (поэтому 2-ю строку опускаем) Þ .

г) если требуется получить матрицу с положительными членами, то доста­точно прибавить к ее элементам, например число с = 3. Получаем:

.

Познавательные статьи:



Техника прыжка в длину с разбега

Организация работы процедурного кабинета

Области применения синхронных машин

Оптимизация по Винеру и Калману