Решение матричной игры: графическим методом, методом линейного программирования
Решение матричной игры
Цена игры, седловая точка
Примеры решений Метод Брауна Системы массового обслуживания Матрица рисков Седловая точка Платежная матрица Цена игры Смешанные стратегии Матричная игра онлайн Чистые стратегии

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

В общем случае V* ≠ V* - седловой точки не существует. Оптимальное решение в чистых стратегиях также не существует. Однако, если расширить понятие чистой стратегии введением понятия смешанной стратегии, то удаётся реализовать алгоритм нахождения оптимального решения не вполне определённой игровой задачи. В такой ситуации предлагается использование статистического (вероятностного) подхода к нахождению оптимального решения антагонистической игры. Для каждого игрока, наряду с данным набором возможных для него стратегий, вводится неизвестный вектор вероятностей (относительных частот), с которыми следует применять ту или иную стратегию.

Обозначим вектор вероятностей (относительных частот) выбора заданных стратегий игрока A следующим образом:
P = (p1, p2,…, pm),
где pi≥ 0, p1 + p2 +…+ pm= 1. Величина pi называется вероятностью (относительной частотой) применения стратегии Ai.

Аналогично для игрока B вводится неизвестный вектор вероятностей (относительных частот) имеет вид:
Q = (q1, q2,…, qn),
где qj≥ 0, q1 + q2 +…+ qn = 1. Величина qj называется вероятностью (относительной частотой) применения стратегии Bj. Совокупность (комбинация) чистых стратегий A1, A2, …Am и B1, B2, …Bn в сочетании с векторами вероятностей выбора каждой из них называются смешанными стратегиями.

Основной теоремой в теории конечных антагонистических игр является Теорема фон Неймана: каждая конечная матричная игра имеет, по крайней мере, одно оптимальное решение, возможно, среди смешанных стратегий.
Из этой теоремы следует, что не вполне определённая игра имеет хотя бы одно оптимальное решение в смешанных стратегиях. В таких играх решением будет пара оптимальных смешанных стратегий P* и Q*, таких, что если один из игроков придерживается своей оптимальной стратегии, то и другому игроку не выгодно отклоняться от своей оптимальной стратегии.
Средний выигрыш игрока A определяется математическим ожиданием:

Если вероятность (относительная частота) применения стратегии отлична от нуля, то такая стратегия называется активной.

Стратегии P*, Q* называются оптимальными смешанными стратегиями, если MA(P, Q*) ≤ MA(P*, Q*) ≤ MA(P*, Q) (1)
В этом случае MA(P*, Q*) называется ценой игры и обозначается через V (V* ≤ V ≤ V*). Первое из неравенств (1)означает, что отклонение игрока A от своей оптимальной смешанной стратегии при условии, что игрок B придерживается своей оптимальной смешанной стратегии, приводит к уменьшению среднего выигрыша игрока A. Второе из неравенств означает, что отклонение игрока B от своей оптимальной смешанной стратегии при условии, что игрок A придерживается своей оптимальной смешанной стратегии, приводит к увеличению среднего проигрыша игрока B.

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

Пример.

472
732
218

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

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

Игроки B1 B2 B3 a = min(Ai)
A1 4 7 2 2
A2 7 3 2 2
A3 2 1 8 1
b = max(Bi) 7 7 8  

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

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

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

Для игрока II
4q1+7q2+2q3 = y
7q1+3q2+2q3 = y
2q1+q2+8q3 = y
q1+q2+q3 = 1

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

y = 41/34
p1 = 29/68 (вероятность применения 1-ой стратегии).
p2 = 4/17 (вероятность применения 2-ой стратегии).
p3 = 23/68 (вероятность применения 3-ой стратегии).

Оптимальная смешанная стратегия игрока I: P = (29/68; 4/17; 23/68)
q1 = 6/17 (вероятность применения 1-ой стратегии).
q2 = 9/34 (вероятность применения 2-ой стратегии).
q3 = 13/34 (вероятность применения 3-ой стратегии).

Оптимальная смешанная стратегия игрока II: Q = (6/17; 9/34; 13/34)
Цена игры: y = 41/34

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

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

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

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

Решение:

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

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

для стратегии В1: 10p1 + 8p2 = v;

для стратегии В2: 7p1+11p2 = v.

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

 

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

 

Итак: , n = 9.

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

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

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

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

.

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

, , , .

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

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

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

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

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

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

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

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

0,029880,125580,259740,176410,009370,522640,080860,848580,994270,49452
0,611090,490420,610760,658340,255790,806410,076750,844190,182680,29702
0,766060,958540,207040,451540,273670,562610,300370,964850,472520,55084
0,738680,564210,071830,994200,111840,805240,428970,450310,053500,67078
0,944830,257100,391900,724910,888880,037910,507730,630340,940910,80165
0,416470,886640,835190,469300,392850,341590,772520,659870,487500,79735
0,513140,226250,062110,392990,843360,808590,526940,733060,368740,93390
0,717490,467270,181820,457910,086670,585700,754950,686450,902700,87484
0,994010,822350,891220,336310,426940,370530,704130,598050,404250,96181
0,412440,244260,375530,094640,562080,688890,595030,923780,031080,33182
Будем выбирать стратегии игроков, используя геометрическое определение вероятности. Так как все случайные числа из отрезка [0; 1], то чтобы стратегия А1 появлялась примерно в половине случаев, будем ее выбирать если случайное число меньше 0,5; в остальных случаях выбирается стратегия А2. Аналогично для игрока В. Стратегию В1 будем выбирать, если соответствующее случайное число меньше 23 ≈ 0.67, в противном случае выбираем стратегию В1.

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

Номер партииСлучайное число игрока АСтратегия игрока А (А1: < 0,5)Случайное число игрока ВСтратегия игрока В (В1: < 0,667)Выигрыш АНакоплен­ный выиг­рыш АСредний выигрыш А (цена игры)
10,029А10,125В1101010,000
20,611А20,490В18189,000
30,766А20,958В211299,667
40,738А20,564В18379,250
50,944А20,257В18459,000
60,416А10,886В27528,667
70,513А10,226В110628,857
80,717А20,467В18708,750
90,994А20,822В211819,000
100,412А10,244В110919,100
110,259А10,176В1101019,182
120,610А20,658В181099,083
130,207А10,451В1101199,154
140,071А10,994В271269,000
150,391А10,724В271338,867
160,835А20,469В1111449,000
170,062А10,392В1101549,059
180,181А10,457В1101649,111
190,891А20,336В181729,053
200,375А10,094В1101829,100
210,009А10,522В1101929,143
220,255А10,806В271999,045
230,273А10,562В1102099,087
240,111А10,805В272169,000
250,888А20,037В182248,960
260,392А10,341В1102349,000
270,843А20,808В2112459,074
280,086А10,585В1102559,107
290,426А10,370В1102659,138
300,562А20,688В2112769,200
Таким образом, в результате моделирования в 30 партиях цена игры (средний выигрыш) равен 9,2. Этот результат согласуется с теоретической ценой игры 9.

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

Х(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. Проверяем, имеет ли платежная матрица седловую точку. Если да, то выписываем решение игры в чистых стратегиях.

ИгрокиB1B2a = min(Ai)
A1454
A2733
b = max(Bi )750

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = 4, которая указывает на максимальную чистую стратегию A1. Верхняя цена игры b = min(bj) = 5.
Что свидетельствует об отсутствии седловой точки, так как a ≠ b, тогда цена игры находится в пределах 4 ≤ y ≤ 5. Находим решение игры в смешанных стратегиях.
Запишем систему уравнений.
Для игрока I
4p1+7p2 = y
5p1+3p2 = y
p1+p2 = 1
Для игрока II
4q1+5q2 = y
7q1+3q2 = y
q1+q2 = 1

 Решая эти системы методом Гаусса, находим:
y = 43/5
p1 = 4/5 (вероятность применения 1-ой стратегии).
p2 = 1/5 (вероятность применения 2-ой стратегии).

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

 q1 = 2/5 (вероятность применения 1-ой стратегии).
q2 = 3/5 (вероятность применения 2-ой стратегии).

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

 Цена игры
y = 43/5

Динамическое программирование
Задачи динамического программирования: задача распределения инвестиций, задача замены оборудования, задача Джонсона
xf1(x)f2(x)f3(x)
16.345
25.267
34.34.67.8
4563
5*76.38.2
Решить онлайн
Учебно-методический
√ курсы переподготовки и повышения квалификации
√ вебинары
√ сертификаты на публикацию методического пособия
Подробнее
Библиотека материалов
√ Общеобразовательное учреждение
√ Дошкольное образование
√ Конкурсные работы
Все авторы, разместившие материал, могут получить свидетельство о публикации в СМИ
Подробнее