Смешанные стратегии. Чистые стратегии игрока. Оптимальные смешанные стратегии. Метод вычисления оптимальных стратегий
Смешанной стратегией SA игрока А называется применение чистых стратегий A1, A2, ..., Am с вероятностями p1, p2, ..., pi, ..., pm причем сумма вероятностей равна 1: Смешанные стратегии игрока А записываются в виде матрицы или в виде строки SA = (p1, p2, ..., pi, ..., pm) Аналогично смешанные стратегии игрока В обозначаются: , или, SB = (q1, q2, ..., qi, ..., qn), где сумма вероятностей появления стратегий равна 1: Чистые стратегии можно считать частным случаем смешанных и задавать строкой, в которой 1 соответствует чистой стратегии. На основании принципа минимакса определяется оптимальное решение (или решение) игры: это пара оптимальных стратегий S*A , S*B в общем случае смешанных, обладающих следующим свойством: если один из игроков придерживается своей оптимальной стратегии, то другому не может быть выгодно отступать от своей. Выигрыш, соответствующий оптимальному решению, называется ценой игры v. Цена игры удовлетворяет неравенству: ? ? v ? ? (3.5) где? и? - нижняя и верхняя цены игры. Справедлива следующая основная теорема теории игр - теорема Неймана. Каждая конечная игра имеет по крайней мере одно оптимальное решение, возможно, среди смешанных стратегий. Пусть S*A = (p*1, p*2, ..., p*i, ..., p*m) и S*B = (q*1, q*2, ..., q*i, ..., q*n) - пара оптимальных стратегий. Если чистая стратегия входит в оптимальную смешанную стратегию с отличной от нуля вероятностью, то она называется активной. Справедлива теорема об активных стратегиях: если один из игроков придерживается своей оптимальной смешанной стратегии, то выигрыш остается неизменным и равным цене игры v, если второй игрок не выходит за пределы своих активных стратегий. Эта теорема имеет большое практическое значение - она дает конкретные модели нахождения оптимальных стратегий при отсутствии седловой точки. Рассмотрим игру размера 2×2, которая является простейшим случаем конечной игры. Если такая игра имеет седловую точку, то оптимальное решение - это пара чистых стратегий, соответствующих этой точке. Игра, в которой отсутствует седловая точка, в соответствии с основной теоремой теории игр оптимальное решение существует и определяется парой смешанных стратегий S*A = (p*1, p*2) и S*B = (q*1, q*2). Для того чтобы их найти, воспользуемся теоремой об активных стратегиях. Если игрок А придерживается своей оптимальной стратегии S"A, то его средний выигрыш будет равен цене игры v, какой бы активной стратегией ни пользовался игрок В. Для игры 2×2 любая чистая стратегия противника является активной, если отсутствует седловая точка. Выигрыш игрока А (проигрыш игрока В) - случайная величина, математическое ожидание (среднее значение) которой является ценой игры. Поэтому средний выигрыш игрока А (оптимальная стратегия) будет равен v и для 1-й, и для 2-й стратегии противника. Пусть игра задана платежной матрицей Средний выигрыш игрока А, если он использует оптимальную смешанную стратегию, а игрок В - чистую стратегию B1 (это соответствует 1-му столбцу платежной матрицы Р), равен цене игры v: a11 p*1+ a21 p*2= v. Тот же средний выигрыш получает игрок А, если 2-й игрок применяет стратегию B2, т.е. a12 p*1+ a22 p*2= v. Учитывая, что p*1+ p*2= 1, получаем систему уравнений для определения оптимальной стратегии S"A и цены игры v: (3.6) Решая эту систему, получим оптимальную стратегию (3.7) и цену игры (3.8) Применяя теорему об активных стратегиях при отыскании SВ*- оптимальной стратегии игрока В, получаем, что при любой чистой стратегии игрока А (А1 или А2) средний проигрыш игрока В равен цене игры v, т.е. (3.9) Тогда оптимальная стратегия определяется формулами: (3.10)
теория игра стратегия смешанная
Смешанные стратегии
Если в матричной игре отсутствует седловая точка в чистых стратегиях, то находят верхнюю и нижнюю цены игры. Они показывают, что игрок 1 не получит выигрыша, превосходящего верхнюю цену игры, и что игроку 1 гарантирован выигрыш, не меньший нижней цены игры.
Смешанная стратегия игрока - это полный набор его чистых стратегий при многократном повторении игры в одних и тех же условиях с заданными вероятностями. Подведем итоги сказанного и перечислим условия применения смешанных стратегий:
- * игра без седловой точки;
- * игроки используют случайную смесь чистых стратегий с заданными вероятностями;
- * игра многократно повторяется в сходных условиях;
- * при каждом из ходов ни один игрок не информирован о выборе стратегии другим игроком;
- * допускается осреднение результатов игр.
Применяются следующие обозначения смешанных стратегий.
Для игрока 1 смешанная стратегия, заключающаяся в применении чистых стратегий А 1 , А 2 , ..., А т с соответствующими вероятностями р 1 , р 2, ..., р т.
Для игрока 2
q j -- вероятность применения чистой стратегии B j .
В случае когда р i = 1, для игрока 1 имеем чистую стратегию
Чистые стратегии игрока являются единственно возможными несовместными событиями. В матричной игре, зная матрицу А (она относится и к игроку 1, и к игроку 2), можно определить при заданных векторах и средний выигрыш (математическое ожидание эффекта) игрока 1:
где и - векторы;
p i и q i - компоненты векторов.
Путем применения своих смешанных стратегий игрок 1 стремится максимально увеличить свой средний выигрыш, а игрок 2 - довести этот эффект до минимально возможного значения. Игрок 1 стремится достигнуть
Игрок 2 добивается того, чтобы выполнялось условие
Обозначим и векторы, соответствующие оптимальным смешанным стратегиям игроков 1 и 2, т.е. такие векторы и, при которых будет выполнено равенство
Цена игры - средний выигрыш игрока 1 при использовании обоими игроками смешанных стратегий. Следовательно, решением матричной игры является:
- - оптимальная смешанная стратегия игрока 1;
- - оптимальная смешанная стратегия игрока 2;
Цена игры.
Смешанные стратегии будут оптимальными (и), если образуют седловую точку для функции т.е.
Существует основная теорема математических игр.
Для матричной игры с любой матрицей А величины
существуют и равны между собой: = = .
Следует отметить, что при выборе оптимальных стратегий игроку 1 всегда будет гарантирован средний выигрыш, не меньший чем цена игры, при любой фиксированной стратегии игрока 2 (и, наоборот, для игрока 2). Активными стратегиями игроков 1 и 2 называют стратегии, входящие в состав оптимальных смешанных стратегий соответствующих игроков с вероятностями, отличными от нуля. Значит, в состав оптимальных смешанных стратегий игроков могут входить не все априори заданные их стратегии.
Решить игру - означает найти цену игры и оптимальные стратегии. Рассмотрение методов нахождения оптимальных смешанных стратегий для матричных игр начнем с простейшей игры, описываемой матрицей 22. Игры с седловой точкой специально рассматриваться не будут. Если получена седловая точка, то это означает, что имеются невыгодные стратегии, от которых следует отказываться. При отсутствии седловой точки можно получить две оптимальные смешанные стратегии. Как уже отмечалось, эти смешанные стратегии записываются так:
Значит, имеется платежная матрица
a 11 p 1 + a 21 p 2 = ; (1.16)
a 12 p 1 + a 22 p 2 = ; (1.17)
p 1 + p 2 = 1. (1.18)
a 11 p 1 + a 21 (1 - p 1) = a 12 p 1 + a 22 (1 - p 1); (1.19)
a 11 p 1 + a 21 - a 21 p 1 = a 12 p 1 + a 22 - a 22 p 1 , (1.20)
откуда получаем оптимальные значенияи:
Зная и, находим:
Вычислив, находим и:
a 11 q 1 + a 12 q 2 = ; q 1 + q 2 = 1; (1.24)
a 11 q 1 + a 12 (1 - q 1) = . (1.25)
при a 11 a 12 . (1.26)
Задача решена, так как найдены векторы и цена игры. Имея матрицу платежей А, можно решить задачу графически. При этом методе алгоритм решения весьма прост (рис. 2.1).
- 1. По оси абсцисс откладывается отрезок единичной длины.
- 2. По оси ординат откладываются выигрыши при стратегии А 1 .
- 3. На линии, параллельной оси ординат, в точке 1 откладываются выигрыши при стратегии a 2 .
- 4. Концы отрезков обозначаются для a 11 -b 11 , a 12 -b 21 , a 22 -b 22 , a 21 -b 12 и проводятся две прямые линии b 11 b 12 и b 21 b 22 .
- 5. Определяется ордината точки пересечения с. Она равна. Абсцисса точки с равна р 2 (р 1 = 1 - р 2).
Рис. 1.1.
Данный метод имеет достаточно широкую область приложения. Это основано на общем свойстве игр тп, состоящем в том, что в любой игре тп каждый игрок имеет оптимальную смешанную стратегию, в которой число чистых стратегий не больше, чем min(m, n). Из этого свойства можно получить известное следствие: в любой игре 2п и т2 каждая оптимальная стратегия и содержит не более двух активных стратегий. Значит, любая игра 2п и т2 может быть сведена к игре 22. Следовательно, игры 2п и т2 можно решить графически. Если матрица конечной игры имеет размерность тп, где т > 2 и п > 2, то для определения оптимальных смешанных стратегий используется линейное программирование.
В общем случае V * ≠ V * - седловой точки не существует. Оптимальное решение в чистых стратегиях также не существует. Однако, если расширить понятие чистой стратегии введением понятия смешанной стратегии, то удаётся реализовать алгоритм нахождения оптимального решения не вполне определённой игровой задачи. В такой ситуации предлагается использование статистического (вероятностного) подхода к нахождению оптимального решения антагонистической игры. Для каждого игрока, наряду с данным набором возможных для него стратегий, вводится неизвестный вектор вероятностей (относительных частот), с которыми следует применять ту или иную стратегию.
Обозначим вектор вероятностей (относительных частот) выбора заданных стратегий игрока A следующим образом:
P = (p 1 , p 2 ,…, p m),
где p i ≥ 0, p 1 + p 2 +…+ p m = 1. Величина p i называется вероятностью (относительной частотой) применения стратегии A i .
Аналогично для игрока B вводится неизвестный вектор вероятностей (относительных частот) имеет вид:
Q = (q 1 , q 2 ,…, q n),
где q j ≥ 0, q 1 + q 2 +…+ q n = 1. Величина q j называется вероятностью (относительной частотой) применения стратегии B j . Совокупность (комбинация) чистых стратегий A 1 , A 2 , …A m и B 1, B 2, …B n в сочетании с векторами вероятностей выбора каждой из них называются смешанными стратегиями.
Основной теоремой в теории конечных антагонистических игр является Теорема фон Неймана
: каждая конечная матричная игра имеет, по крайней мере, одно оптимальное решение, возможно, среди смешанных стратегий
.
Из этой теоремы следует, что не вполне определённая игра имеет хотя бы одно оптимальное решение в смешанных стратегиях. В таких играх решением будет пара оптимальных смешанных стратегий P * и Q * , таких, что если один из игроков придерживается своей оптимальной стратегии, то и другому игроку не выгодно отклоняться от своей оптимальной стратегии.
Средний выигрыш игрока A определяется математическим ожиданием:
Если вероятность (относительная частота) применения стратегии отлична от нуля, то такая стратегия называется активной .
Стратегии P * , Q * называются оптимальными смешанными
стратегиями, если M A (P, Q *) ≤ M A (P * , Q *) ≤ M A (P * , Q) (1)
В этом случае M A (P * , Q *) называется ценой
игры и обозначается через V (V * ≤ V ≤ V *). Первое из неравенств (1)означает, что отклонение игрока A от своей оптимальной смешанной стратегии
при условии, что игрок B придерживается своей оптимальной смешанной стратегии, приводит к уменьшению среднего выигрыша
игрока A. Второе из неравенств означает, что отклонение игрока B от своей оптимальной смешанной стратегии
при условии, что игрок A придерживается своей оптимальной смешанной стратегии, приводит к увеличению среднего проигрыша игрока B
.
В общем случае подобные задачи успешно решаются этим калькулятором .
Пример .
| 4 | 7 | 2 |
| 7 | 3 | 2 |
| 2 | 1 | 8 |
1. Проверяем, имеет ли платежная матрица седловую точку . Если да, то выписываем решение игры в чистых стратегиях.
Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I.
| Игроки | B 1 | B 2 | B 3 | a = min(A i) |
| A 1 | 4 | 7 | 2 | 2 |
| A 2 | 7 | 3 | 2 | 2 |
| A 3 | 2 | 1 | 8 | 1 |
| b = max(B i) | 7 | 7 | 8 |
Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(a i) = 2, которая указывает на максимальную чистую стратегию A 1 .
Верхняя цена игры b = min(b j) = 7. Что свидетельствует об отсутствии седловой точки, так как a ≠ b, тогда цена игры находится в пределах 2 ≤ y ≤ 7. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии).
2. Проверяем платежную матрицу на доминирующие строки и доминирующие столбцы
.
В платежной матрице отсутствуют доминирующие строки и доминирующие столбцы.
3. Находим решение игры в смешанных стратегиях
.
Запишем систему уравнений.
Для игрока I
4p 1 +7p 2 +2p 3 = y
7p 1 +3p 2 +p 3 = y
2p 1 +2p 2 +8p 3 = y
p 1 +p 2 +p 3 = 1
Для игрока II
4q 1 +7q 2 +2q 3 = y
7q 1 +3q 2 +2q 3 = y
2q 1 +q 2 +8q 3 = y
q 1 +q 2 +q 3 = 1
Решая эти системы методом Гаусса , находим:
y = 4 1 / 34
p 1 = 29 / 68 (вероятность применения 1-ой стратегии).
p 2 = 4 / 17 (вероятность применения 2-ой стратегии).
p 3 = 23 / 68 (вероятность применения 3-ой стратегии).
Оптимальная смешанная стратегия игрока I: P = (29 / 68 ; 4 / 17 ; 23 / 68)
q 1 = 6 / 17 (вероятность применения 1-ой стратегии).
q 2 = 9 / 34 (вероятность применения 2-ой стратегии).
q 3 = 13 / 34 (вероятность применения 3-ой стратегии).
Оптимальная смешанная стратегия игрока II: Q = (6 / 17 ; 9 / 34 ; 13 / 34)
Цена игры: y = 4 1 / 34
Описание биматричной игры . Все игры которые были рассмотрены, относились к классу игр с нулевой суммой . Однако ряд конфликтных ситуаций, складывающихся в ходе действий, характерны тем, что выигрыш одной стороны не равен в точности проигрышу другой. Теоретико-игровыми моделями подобных ситуаций являются некооперативные игры с ненулевой суммой. Такие игры называются биматричными , потому что задание каждой такой игры сводится к заданию двух матриц и одинаковой формы: .
Процесс биматричной игры состоит в независимом выборе игроком I числа а игроком II - числа , после чего игрок I получает выигрыш , а игрок II - выигрыш .
Номера строк матриц и назовем чистыми стратегиями игрока
I, а номера столбцов этих матриц – чистыми стратегиями игрока
II. Тогда пары вида будут являться ситуациями в чистых стратегиях биматричной игры
, а числа и - выигрышами I и II игроков в ситуации . Соответственно, распределение вероятностей применения чистых стратегий игрока I - 
и игрока II - 
будем называть смешанными стратегиями
. Тогда пары вида представляют ситуации биматричной игры
в смешанных стратегиях
, а числа 
и 
являются математическими ожиданиями выигрыша I и II игроков.
Ситуацией равновесия биматричной игры в смешанных стратегиях будем называть такую пару , при которой:
 |
(8.2) |
где - математическое ожидание выигрыша игрока I;
Математическое ожидание выигрыша игрока II;
Оптимальная смешанная стратегия игрока I;
Оптимальная смешанная стратегия игрока II.
Задача
Построение и решение биматричной игры . Предположим, что противолодочная подводная лодка страны осуществляет поиск ракетной подводной лодки государства , которая маневрирует в строго определенной части района боевого патрулирования. В остальной части этого района действует противолодочная подводная лодка , которая осуществляет поиск противолодочной подводной лодки . Пусть каждая противолодочная лодка для обнаружения противника может использовать свою гидроакустическую станцию или в активном режиме, включая ее периодически, или только в пассивном режиме, выполняя непрерывный поиск .
Как противолодочная подводная лодка , так и ракетная подводная лодка с обнаружением сигналов гидролокатора может уклониться от противника. Однако периодичность включения гидролокатора делает обнаружение возможным, но недостоверным.
В подобной конфликтной ситуации одним из игроков является противолодочная подводная лодка , а другим - противолодочная подводная лодка .Очевидно, ракетная подводная лодка не может быть игроком, так как она имеет только один способ действий, заключающийся в скрытом маневрировании и выполнении уклонения с обнаружением сигналов гидролокаторов.
Характерным здесь является то, что каждый из игроков преследует разные, но не противоположные цели. Действительно, целью противолодочной подводной лодки является обнаружение ракетной подводной лодки, а целью противолодочной подводной лодки - обнаружение противолодочной подводной лодки . Поэтому для оценки достижения цели каждым из игроков в зависимости от выбранных способов действий (стратегий) необходимо иметь два критерия эффективности и соответственно две функции выигрыша. Тогда моделью подобной конфликтной ситуации будет конечная игра
с ненулевой суммой, описываемая двумя матрицами одинаковой формы 
и 
, называемая биматричной.
Примем за критерий эффективности противолодочной подводной лодки (игрок I) вероятность обнаружения ракетной подводной лодки , а за критерий эффективности противолодочной подводной лодки (игрок II) – вероятность обнаружения противолодочной подводной лодки . Тогда биматричная игра будет задана матрицей (рисунок 9.a) и матрицей (рисунок 9.b).
Рис. 9.a.
Рис. 9.b.
Где - использование активного режима;
Использование пассивного режима.
Различают
стратегии чистые и смешанные. Чистая
стратегия
первого игрока (чистая стратегия
второго игрока) – это возможный ход
первого (второго) игрока, выбранный им
с вероятностью, равной 1.
Если
первый игрок имеет m
стратегий, а второй – n
стратегий, то для любой пары стратегий
первого и второго игроков чистые
стратегии можно представить в виде
единичных векторов. Например, для пары
стратегий
,
чистые стратегии первого и второго
игроков запишутся в виде:
,
.
Для пары стратегий
,
чистые стратегии можно записать в виде:
,
.
Теорема
:
В матричной игре нижняя чистая цена
игры не превосходит верхней чистой цены
игры, т. е.
.
Определение:
Если для
чистых стратегий
,
игроковA
и В соответственно имеет место равенство
,
то пару чистых стратегий (
,
)
называют седловой точкой матричной
игры, элемент
матрицы, стоящий на пересеченииi-й
строки и j-го
столбца – седловым элементом платежной
матрицы, а число
- чистой ценой игры.
Пример: Найти нижнюю и верхнюю чистые цены, установить наличие седловых точек матричной игры
.
Определим
нижние и верхние чистые цены игры:
,
,
.
|
|
|||||
|
|
В
данном случае имеем одну седловую точку
(А 1 ;
В 2),
а седловой элемент равен 5. Этот элемент
является наименьшим в 1-й строке и
наибольшим во 2-м столбце. Отклонение
игрока А от максиминной стратегии А 1
ведет к уменьшению его выигрыша, а
отклонение игрока В от минимаксной
стратегии В 2
ведет к увеличению его проигрыша. Иными
словами, если в матричной игре имеется
седловой элемент, то наилучшими для
игроков являются их минимаксные
стратегии. И эти чистые стратегии,
образующие седловую точку и выделяющие
в матрице игры седловой элемент a 12 =5,
есть оптимальные чистые стратегии
и
соответственно игроков А и В.
Если
же матричная игра не имеет седловой
точки, то решение игры затрудняется. В
этих играх
.
Применение минимаксных стратегий в
таких играх приводит к тому, что для
каждого из игроков выигрыш не превышает
,
а проигрыш - не меньше
.
Для каждого игрока возникает вопрос
увеличения выигрыша (уменьшение
проигрыша). Решение находят, применяя
смешанные стратегии.
Определение:
Смешанной
стратегией первого (второго) игрока
называется вектор
,
где
и
(
,
где
и
).
Вектор p(q) означает вероятность применения i-й чистой стратегии первым игроком (j-й чистой стратегии вторым игроком).
Поскольку игроки выбирают свои чистые стратегии случайно и независимо друг от друга, игра имеет случайный характер и случайной становится величина выигрыша (проигрыша). В таком случае средняя величина выигрыша (проигрыша) – математическое ожидание – является функцией от смешанных стратегий р, q:
.
Определение:
Функция f(р,
q)
называется платежной функцией игры с
матрицей
.
Определение:
Стратегии
,
называются оптимальными, если для
произвольных стратегий
,
выполняется условие
Использование в игре оптимальных смешанных стратегий обеспечивает первому игроку выигрыш, не меньший, чем при использовании им любой другой стратегии р; второму игроку – проигрыш, не больший, чем при использовании им любой другой стратегии q.
Совокупность оптимальных стратегий и цены игры составляет решение игры.