Решение игр в чистых стратегиях. Теория игр и статистических решений
теория игра стратегия смешанная
Смешанные стратегии
Если в матричной игре отсутствует седловая точка в чистых стратегиях, то находят верхнюю и нижнюю цены игры. Они показывают, что игрок 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, то для определения оптимальных смешанных стратегий используется линейное программирование.
Если в игре каждый из противников применяет одну и ту же стратегию, то про эту игру говорят, что она происходит в чистых стратегиях, а стратегии игроков А и В будут называться чистыми стратегиями .В антагонистической игре пара стратегий называется равновесной (устойчивой), если ни одному из игроков невыгодно отступать от своих стратегий.Применять чистые стратегии имеет смысл, если игроки знают о действиях противника. Если этого нет, то идея равновесия нарушается и игра может вестись как получится.Стратегии А1 В1 – устойчивы по отношению к информации о поведении противника.Признаком устойчивости пары стратегий это равенство верхней и нижней цены игры. И случай А1 В1 будет
ν = α = β. ν > 0, то игрок А будет в выигрыше, если ν < 0, то в выигрыше игрок В. Если ν = 0, в этом случае игра справедлива для обоих игроков. Не все матричные игры имеют седловые точки.
Теорема: каждая игра с полной информацией имеет седловую точку и следовательно решает в чистых стратегиях, т.е. имеется пара устойчивых стратегий, дающих устойчивый выигрыш равный ν.Если матрица не имеет седловую точку, то цена игры лежит α<ν<β. Это означает, что первый игрок, используя максиминный принцип, обеспечит себе выигрыш не менее, чем α. А второй игрок придерживаясь минимаксного подхода обеспечит себе проигрыш не больше верхней цены игры. Игра будет оптимальна, если оба игрока будут применять смешанные стратегии.Случайная величина, значениями которой являются чистые стратегии, называется смешанной стратегией для этого игрока.
Задать смешанную стратегию это значит задать те вероятности, с которыми используются чистые стратегии.
S A = || p 1 , p 2 …. p m || ,S B = || q1, q2 …. q m || , A: ∑ pi = 1 ,B: ∑ qi = 1
Игра может повторяться несколько раз, но в каждой партии игрок придерживается смешанной стратегии, где чистые стратегии придерживаются вероятности p i и q j .
Модель смешанные стратегий отличается от модели чистых стратегий. В случае смешанных стратегий тактика поведения игроков будет более гибкой, т.к. игроки знают заранее какую чистую стратегию они применят.
Предположим что и игрок А и игрок В придерживаются смешанной стратегии. Необходимо определить А: ∑∑ a ij p i q j
Для игрока В ожидаемый проигрыш равен ожидаемому выигрышу игрока А. Выигрыш первого игрока и средний проигрыш второго игрока равны друг другу.
18.Методы решения конечной игры двух лиц порядка m*n.
Предположим, что все элементы платёжной матрицы 0≤aij. Тогда α≤ν≤β. Согласно основной теореме матричных игр, любая матричная игра имеет 2 оптимальные смешанные стратегии.
S A = (p 1 , p 2 , … , p n)
S B = (p 1 , p 2 , … , p n)
Решаем игру для игрока А, при этом предполагая что игрок В использует только чистые стратегии. Тогда
a 11 p 1 + a 21 p 2 + … + a m1 p m ≥ ν: B 1
a 12 p 1 + a 22 p 2 + … + a m2 p m ≥ ν: B 2 (1)
a 1n p 1 + a 2n p 2 + … + a mn p m ≥ ν: B n
X 1 = P 1 /ν , X 2 = P 2 /ν … X m = P m /ν
a 11 X 1 … + a m1 p m ≥ 1
a 1n X 1 … + a m1 p m ≥ 1 (2)
p 1 +p 2 +…+p m =1
X 1 +X 2 +…+X m = 1/ν (3)
L(x) = X 1 +X 2 +…+X m -> min (4)
Определим задачу линейного программирования.
ν = 1/(X 1 0 +X 2 0 …X m 0) (5)
P1 = X 1 0 *ν опт
p2 = X 2 0 *ν опт (6)
min L(x) = ∑x i
∑a ij: 1≤x i (7) (прямая задача)
0≤x i (i=1,2..)
a 11 q 1 + a 21 q 2 + … + a m1 q m < ν: A 1
a 21 q 1 + a 22 q 2 + … + a m2 q m < ν: A 2 (8)
a m1 q 1 + a m2 q 2 + … + a mn q m < ν: A m
Y 1 = q 1 /ν , Y 2 = q 2 /ν … Y m = q m /ν
q 1 +q 2 +…+q n =1
y 1 +y 2 +…+y n =1/ν
L(y)=∑y j -> max
∑a ij , y i ≤1 (i=1,2…) (9) (двойственная задача)
y 1 0 +y 2 0 …y m 0 = 1/ν опт
ν опт = 1/∑y m 0
Q1 = y 1 0 *ν опт
q2 = y 2 0 *ν опт
ν=1/∑x i = 1/∑y i = 1/min L(x) = 1/ max L(y) (11)
| B 1 | B 2 | B 3 | α i | |
| A 1 | ||||
| A 2 | ||||
| A 3 | ||||
| β j |
1) α = 1, β = 3
2) Нет упрощений.
L(x)=x 1 +x 2 +x 3 => min
x 1 +3x 2 +x 3 >= 1
2x 1 +x 2 +x 3 >=1
3x 1 +x 2 +x 3 >=1
x 1 =2/9, x 2 =2/9, x 3 =1/9
ν=1/(2/9+2/9+1/9)=9/5
p 1 =x 1 *ν=2/5
S A =(2/5, 2/5, 1/5)
двойственная задача
L(y) = y 1 +y 2 +y 3 => max
y 1 +2y 2 +3y 3 ≤ 1 y 1 =2/9
3y 1 +y 2 +y 3 ≤1 => y 2 =2/9 max L(y) = 5/9
y 1 +3y 2 +y 3 ≤1 y 3 =1/9
ν=1/(2/9+2/9+1/9)=9/5
q 1 =y 2 *ν=(2/9)*(9/5)=2/5
q 2 =(2/9)*(9/5)=2/5
q 3 =(1/9)*(9/5)=1/5
S B =(2/5, 2/5, 1/5)
Задача mxn сводится к задаче линейного программирования.
Приближённый метод решения матричных игр mxn (Браун-Робинсон).
Игрок А и игрок В поочерёдно применяют чистые стратегии. Каждый игрок пытается увеличить свой выигрыш, используя максиминые или минимаксные подходы. Минимизируется (максимизируется) не средний выигрыш, а накопленный. В теории показывается, что такой метод неизбежно даст нам оптимальный выигрыш и оптимальные смешанные стратегии.
| В 1 | В 2 | В 3 | |
| А 1 | |||
| А 2 | |||
| А 3 | |||
| 3 * | 8 * | 9 * | 36 * | ||||||
| 3 * | 4 * | 12 * | 13 * | ||||||
| 7 * | |||||||||
| 1 * | |||
| 3 * | |||
| 4 * | |||
| 6 * | |||
| 9 * | |||
| 10 * | |||
| 12 * | |||
| 34 * |
Оптимальные чистые стратегии игроков отличаются от смешанных наличием обязательного единичного p i = 1, q i = 1. Например: P(1,0), Q(1,0). Здесь p 1 = 1, q 1 = 1.
Задача 1
По платёжной матрице найти оптимальные чистые стратегии, используя принцип строгого доминирования. В качестве ответа записать векторы P*, Q*.
R1 | R2 | R3 | R4 |
|
S1 | 3 | 1 | 2 | 5 |
S2 | 2 | 0 | 0 | 3 |
S3 | -3 | -5 | -5 | -2 |
S4 | 0 | -2 | -2 | 1 |
Решение:
Все задачи решаем с помощью калькулятора Матричная игра .
Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I.
| Игроки | B 1 | B 2 | B 3 | B 4 | a = min(A i) |
| A 1 | 3 | 1 | 2 | 5 | 1 |
| A 2 | 2 | 0 | 0 | 3 | 0 |
| A 3 | -3 | -5 | -5 | -2 | -5 |
| A 4 | 0 | -2 | -2 | 1 | -2 |
| b = max(B i) | 3 | 1 | 2 | 5 |
Верхняя цена игры b = min(b j) = 1.
Седловая точка (1, 2) указывает решение на пару альтернатив (A1,B2). Цена игры равна 1.
2. Проверяем платежную матрицу на доминирующие строки и доминирующие столбцы.
Иногда на основании простого рассмотрения матрицы игры можно сказать, что некоторые чистые стратегии могут войти в оптимальную смешанную стратегию лишь с нулевой вероятностью.
Говорят, что i-я стратегия 1-го игрока доминирует его k-ю стратегию, если a ij ≥ a kj для всех j Э N и хотя бы для одного j a ij > a kj . В этом случае говорят также, что i-я стратегия (или строка) – доминирующая, k-я – доминируемая.
Говорят, что j-я стратегия 2-го игрока доминирует его l-ю стратегию, если для всех j Э M a ij ≤ a il и хотя бы для одного i a ij < a il . В этом случае j-ю стратегию (столбец) называют доминирующей, l-ю – доминируемой.
Стратегия A 1 доминирует над стратегией A 2 (все элементы строки 1 больше или равны значениям 2-ой строки), следовательно исключаем 2-ую строку матрицы. Вероятность p 2 = 0.
Стратегия A 1 доминирует над стратегией A 3 (все элементы строки 1 больше или равны значениям 3-ой строки), следовательно исключаем 3-ую строку матрицы. Вероятность p 3 = 0.
| 3 | 1 | 2 | 5 |
| 0 | -2 | -2 | 1 |
С позиции проигрышей игрока В стратегия B 1 доминирует над стратегией B 2 (все элементы столбца 1 больше элементов столбца 2), следовательно исключаем 1-й столбец матрицы. Вероятность q 1 = 0.
С позиции проигрышей игрока В стратегия B 4 доминирует над стратегией B 1 (все элементы столбца 4 больше элементов столбца 1), следовательно исключаем 4-й столбец матрицы. Вероятность q 4 = 0.
| 1 | 2 |
| -2 | -2 |
Мы свели игру 4 x 4 к игре 2 x 2.
Решение игры (2 x n
p 1 = 1
p 2 = 0
Цена игры, y = 1
Теперь можно найти минимаксную стратегию игрока B, записав соответствующую систему уравнений
q 1 = 1
q 1 +q 2 = 1
Решая эту систему, находим:
q 1 = 1.
Ответ:
Цена игры: y = 1, векторы стратегии игроков:
Q(1, 0), P(1, 0)
∑a ij q j ≤ v
∑a ij p i ≥ v
M(P 1 ;Q) = (1 1) + (2 0) = 1 = v
M(P 2 ;Q) = (-2 1) + (-2 0) = -2 ≤ v
M(P;Q 1) = (1 1) + (-2 0) = 1 = v
M(P;Q 2) = (2 1) + (-2 0) = 2 ≥ v
Поскольку из исходной матрицы были удалены строки и столбцы, то найденные векторы вероятности можно записать в виде:
P(1,0,0,0)
Q(0,1,0,0)
Задача 2
По платёжной матрице найти нижнюю и верхнюю цену игры. При наличии седловой точки записать векторы оптимальных чистых стратегий P*, Q*.
R1 | R2 | R3 |
|
S1 | -6 | -5 | 0 |
S2 | -8 | -3 | -2 |
S3 | -3 | -2 | 3 |
Решение:
1. Проверяем, имеет ли платежная матрица седловую точку. Если да, то выписываем решение игры в чистых стратегиях.
| Игроки | B 1 | B 2 | B 3 | a = min(A i) |
| A 1 | -6 | -5 | 0 | -6 |
| A 2 | -8 | -3 | -2 | -8 |
| A 3 | -3 | -2 | 3 | -3 |
| b = max(B i) | -3 | -2 | 3 |
Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(a i) = -3, которая указывает на максимальную чистую стратегию A 3 .
Верхняя цена игры b = min(b j) = -3.
Седловая точка (3, 1) указывает решение на пару альтернатив (A3,B1). Цена игры равна -3.
Ответ: P(0,0,1), Q(1,0,0)
Задача 3
По платёжной матрице найти векторы оптимальных стратегий P*, Q*и цену игры. Кто из игроков оказывается в выигрыше?
R1 | R2 | R3 | R4 |
|
S1 | -6 | -6 | 2 | 4 |
S2 | 2 | -2 | 7 | -1 |
Решение:
1. Проверяем, имеет ли платежная матрица седловую точку. Если да, то выписываем решение игры в чистых стратегиях.
Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I.
| Игроки | B 1 | B 2 | B 3 | B 4 | a = min(A i) |
| A 1 | -6 | -6 | 2 | 4 | -6 |
| A 2 | 2 | -2 | 7 | -1 | -2 |
| b = max(B i) | 2 | -2 | 7 | 4 |
Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(a i) = -2, которая указывает на максимальную чистую стратегию A 2 .
Верхняя цена игры b = min(b j) = -2.
Седловая точка (2, 2) указывает решение на пару альтернатив (A2,B2). Цена игры равна -2.
3. Находим решение игры в смешанных стратегиях.
Решим задачу геометрическим методом, который включает в себя следующие этапы:
1. В декартовой системе координат по оси абсцисс откладывается отрезок, длина которого равна 1. Левый конец отрезка (точка х = 0) соответствует стратегии A 1 , правый - стратегии A 2 (x = 1). Промежуточные точки х соответствуют вероятностям некоторых смешанных стратегий S 1 = (p 1 ,p 2).
2. На левой оси ординат откладываются выигрыши стратегии A 1 . На линии, параллельной оси ординат, из точки 1 откладываются выигрыши стратегии A 2 .
Решение игры (2 x n ) проводим с позиции игрока A, придерживающегося максиминной стратегии. Доминирующихся и дублирующих стратегий ни у одного из игроков нет.
Максиминной оптимальной стратегии игрока A соответствует точка N, для которой можно записать следующую систему уравнений:
p 1 = 0
p 2 = 1
Цена игры, y = -2
Теперь можно найти минимаксную стратегию игрока B, записав соответствующую систему уравнений, исключив стратегию B 1 ,B 3 ,B 4 , которая дает явно больший проигрыш игроку B, и, следовательно, q 1 = 0,q 3 = 0,q 4 = 0.
-2q 2 = -2
q 2 = 1
Решая эту систему, находим:
q 2 = 1.
Ответ:
Цена игры: y = -2, векторы стратегии игроков:
Q(0, 1, 0, 0), P(0, 1)
4. Проверим правильность решения игры с помощью критерия оптимальности стратегии.
∑a ij q j ≤ v
∑a ij p i ≥ v
M(P 1 ;Q) = (-6 0) + (-6 1) + (2 0) + (4 0) = -6 ≤ v
M(P 2 ;Q) = (2 0) + (-2 1) + (7 0) + (-1 0) = -2 = v
M(P;Q 1) = (-6 0) + (2 1) = 2 ≥ v
M(P;Q 2) = (-6 0) + (-2 1) = -2 = v
M(P;Q 3) = (2 0) + (7 1) = 7 ≥ v
M(P;Q 4) = (4 0) + (-1 1) = -1 ≥ v
Все неравенства выполняются как равенства или строгие неравенства, следовательно, решение игры найдено верно.
Задача 4
Дайте развернутый ответ на вопрос
Смешанной стратегией 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)
В общем случае 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