Материал: УП - Методы оптимальных решений

5.2. Максиминные и минимаксные стратегии игроков

Каждый игрок выбирает для себя наиболее выгодную стратегию, при этом игрок А стремится получить mах выигрыш, а игрок В выбирает стра­тегию, которая дает ему min проигрыш. В этой связи вводят понятия нижней и верхней чистой цены игры.

Нижней чистой ценой игры (максимином) игрока А называют число:

 = maх (min а_ij) (7)

i j

Верхней чистой ценой игры (минимаксом) игрока В называют число:

= min (max а_ij) (8)

j i

Стратегии игроков, соответствующие максимину (минимаксу), на­зываются максиминными (минимаксными).

Пример 20. Найти максиминную и минимаксную стратегии игроков в матричной игре: .

Решение:

Запишем платежную матрицу (табл. 27).

Таблица 27

В соответствии с формулой (7) по каждой строке определим наименьшее число, которое и записываем в столбец _i. Это означает, что какой бы выбор по столбцам ни сделал игрок В, выигрыш игрока А, который выбирает свои стратегии по строкам, в худшем случае составит (– 3; 3; 1; 2) и поэтому игрок А выбирает из них max, т. е.  = maх (min а_ij) = max α_i = max(– 3; 3; 1; 2) = 3, сле-

i j

довательно, максиминной стратегией игрока А является стратегия А₂.

Аналогично, пользуясь формулой (8), находим = min (max а_ij)

j i

= min_j = min(5; 7; 8; 9) = 5 – минимаксной стратегией игрока В является стратегия B₁.

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

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

А. Чистая стратегия А_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-место.

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

Доказательство. Возьмем i – строку и j – столбец. По определению _i = min _ij,  _ij, а _j = max _ij  _ij  _i  _ij,  _j  _i  _i,

j i

(i = , j = ).

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

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

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

Решение.

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

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

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

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

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

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

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

, где и

где ,

Вектор означает вероятность применения 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 с ценой игры  должны выполняться неравенства:

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

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

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

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

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

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

Решение:

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

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

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

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

_.

5.4. Приведение матричной игры к задаче линейного программирования

Пусть имеем игру размерности m* n с матрицей:

_.

Обозначим через р^*=(р₁, …, р_m) g^*=(g₁, …, g_n) – оптимальные смешанные стратегии игроков А и В. Стратегия р^* игрока А гарантирует ему вы­игрыш ≥ υ независимо от выбора стратегии игроком В. Это можно запи­сать так:

(9)

где р₁ + р₂ + … + р_m = 1, .

Аналогично стратегия g^* игрока В гарантирует ему проигрыш ≤ υ, не­зависимо от выбора стратегии игроком А, т. е.

(10)

где g₁ + g₂ + … + g_n = 1, g_j ≥ 0 (j = ).

Поскольку элементы платежной матрицы можно сделать положи­тельными, то и цена игры υ ≥ 0.

Разделим системы (9) и (10) на υ ≥ 0, получим (11) и (12).

(11)

где

(12)

где

Обозначим , тогда имеем:

(13)

_{где х1 + х2 + … + хm=}

(14)

где у₁ + у₂ + … + у_n =