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

Обозначим вектор вероятностей (относительных частот) выбора заданных стратегий игрока A следующим образом:
P = (p₁, p₂,…, p_m),
где p_i≥ 0, p₁ + p₂ +…+ p_m= 1. Величина p_i называется вероятностью (относительной частотой) применения стратегии A_i.

Аналогично для игрока B вводится неизвестный вектор вероятностей (относительных частот) имеет вид:
Q = (q₁, q₂,…, q_n),
где q_j≥ 0, q₁ + q₂ +…+ q_n = 1. Величина q_j называется вероятностью (относительной частотой) применения стратегии B_j. Совокупность (комбинация) чистых стратегий A₁, A₂, …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.

В общем случае подобные задачи успешно решаются этим калькулятором.

Пример.

1. Проверяем, имеет ли платежная матрица седловую точку. Если да, то выписываем решение игры в чистых стратегиях.

Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I.

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(a_i) = 2, которая указывает на максимальную чистую стратегию A₁.
Верхняя цена игры b = min(b_j) = 7. Что свидетельствует об отсутствии седловой точки, так как a ≠ b, тогда цена игры находится в пределах 2 ≤ y ≤ 7. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии).

2. Проверяем платежную матрицу на доминирующие строки и доминирующие столбцы.
В платежной матрице отсутствуют доминирующие строки и доминирующие столбцы.

3. Находим решение игры в смешанных стратегиях.
Запишем систему уравнений.
Для игрока I
4p₁+7p₂+2p₃ = y
7p₁+3p₂+p₃ = y
2p₁+2p₂+8p₃ = y
p₁+p₂+p₃ = 1

Для игрока II
4q₁+7q₂+2q₃ = y
7q₁+3q₂+2q₃ = y
2q₁+q₂+8q₃ = y
q₁+q₂+q₃ = 1

Решая эти системы методом Гаусса, находим:

y = 4¹/₃₄
p₁ = ²⁹/₆₈ (вероятность применения 1-ой стратегии).
p₂ = ⁴/₁₇ (вероятность применения 2-ой стратегии).
p₃ = ²³/₆₈ (вероятность применения 3-ой стратегии).

Оптимальная смешанная стратегия игрока I: P = (²⁹/₆₈; ⁴/₁₇; ²³/₆₈)
q₁ = ⁶/₁₇ (вероятность применения 1-ой стратегии).
q₂ = ⁹/₃₄ (вероятность применения 2-ой стратегии).
q₃ = ¹³/₃₄ (вероятность применения 3-ой стратегии).

Оптимальная смешанная стратегия игрока II: Q = (⁶/₁₇; ⁹/₃₄; ¹³/₃₄)
Цена игры: y = 4¹/₃₄

Пример №2. Матричную игру 2х2 решить в смешанных стратегиях:

1) аналитически (для игрока А); геометрически (для игрока В)

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

Игра задана платежной матрицей: .

Решение:

1. Найдем аналитически оптимальную стратегию игрока А и соответствующую цену игры Х*(р₁, р₂), n.

Так как Х* - оптимальная, то она должна гарантировать средний выигрыш игроку А, равный цене игры при любом поведении игрока В:

для стратегии В₁: 10p₁ + 8p₂ = v;

для стратегии В₂: 7p₁+11p₂ = v.

С учетом того, что сумма компонентов смешанной стратегии равна 1, получаем систему уравнений:

Вычтем из первого уравнения второе: 3p₁ - 3p₂ = 0 или p₁ = p₂.Значит:

Итак: , n = 9.

Найдем геометрически оптимальную смешанную стратегию игрока В: Y*(q₁, q₂).

Стратегию А₁ изобразим точками с ординатами 10 и 7 на прямых В₁ и В₂ соответственно. Стратегию А₂ - точками с ординатами 8 и 11 (см. рис. 1).

Рис. 1. Геометрическая интерпретация матричной игры для игрока В

Каждой точке на отрезке [0; 1] соответствует смешанная стратегия игрока В. Среди них оптимальной будет та, которая определяется самой низкой точкой ломанной А₁МА₂, т.е. точкой М. Для нахождения компонентов оптимальной стратегии игрока В надо найти координаты точки М, причем если М (х, у), то q₁ = 1 - х, q₂ = х, n = y. Для этого найдем уравнения прямых А₁А₁ и А₂А₂, воспользовавшись уравнением прямой, проходящей через две точки:

.

Так как А₁(0; 10) и А₁(1; 7), то

, , , .

Т.е. уравнение прямой А₁А₁ имеет вид: 3x + y - 10 = 0.

Так как А₂(0; 8) и А₂(1; 11), то

, , 3x = y-8, 3x-y + 8=0.

Т.е. уравнение прямой А₂А₂ имеет вид: 3x-y + 8 = 0.

Найдем координаты точки М, решив систему уравнений прямых А₁А₁ и А₂А₂:

Итак, , значит n = 9, или .

Ответ: , , n = 9.

2. Проведем моделирование результатов решения с помощью таблицы равномерно распределенных случайных чисел. Для 30 партий хватит 60 чисел, на основе которых будут выбираться стратегии игроками. Используемые случайные числа сгенерированы в MS Excel функцией =СЛЧИС(). В приложении достаточно много чисел, но использовать для моделирования можно любые 60, выбранные произвольно с любого места таблицы. Мы возьмем первые числа.

Заполним расчетную таблицу:

Частоты использования игроками своих чистых стратегий соответственно равны:

Х(18/30;12/30), Y(21/30; 9/30) или

Х(0,6; 0,4), Y(0,7; 0,3)

Сравнивая с теоретическими оптимальными стратегиями Х*(0,5; 0,5) и Y*(0,67; 0,33) можно сделать вывод, что результаты моделирования достаточно близко им соответствуют даже для небольшого количества партий.

Пример №2. Проверяем, имеет ли платежная матрица седловую точку. Если да, то выписываем решение игры в чистых стратегиях.

 Решая эти системы методом Гаусса, находим:
y = 4³/₅
p₁ = ⁴/₅ (вероятность применения 1-ой стратегии).
p₂ = ¹/₅ (вероятность применения 2-ой стратегии).

 Оптимальная смешанная стратегия игрока I: P = (⁴/₅; ¹/₅)

 q₁ = ²/₅ (вероятность применения 1-ой стратегии).
q₂ = ³/₅ (вероятность применения 2-ой стратегии).

 Оптимальная смешанная стратегия игрока II: Q = (²/₅; ³/₅)

 Цена игры
y = 4³/₅