Высшая Математика Решение задач и примеров - OnLine
./ Главная /Теория игр, ШАГ-1/ШАГ-2/Финиш >

Пример решения задачи теории игр в смешанных стратегиях нашим сервисом:



Заметьте! Решение вашей конкретной задачи будет выглядеть аналогично данному примеру, включая все таблицы, поясняющие тексты и рисунки, представленные ниже, но с учетом ваших исходных данных…

Задача:
Матричная игра задана следующей платежной матрицей :

Стратегии "B"
Стратегии "A" B1 B2
A1 3 5
A2 6
3
2

Найти решение матричной игры, а именно:
        - найти верхнюю цену игры;
        - нижнюю цену игры;
        - чистую цену игры;
        - указать оптимальные стратегии игроков;
        - привести графическое решение (геометрическую интерпретацию), при необходимости.




Шаг:1

Определим нижнюю цену игры - α

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

Найдем в каждой строке платежной матрицы минимальный элемент и запишем его в дополнительный столбец ( Выделен желтым цветом см. Табл.1 ).

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

Таблица 1
Стратегии "B"
Стратегии "A" B1 B2 Минимумы строк
A1 3 5 3*
A2 6
3
2
3
2

В нашем случае нижняя цена игры равна: α = 3, и для того чтобы гарантировать себе выигрыш не хуже чем 3 мы должны придерживаться стратегии A1



Шаг:2

Определим верхнюю цену игры - β

Верхняя цена игры β — это минимальный проигрыш, который может гарантировать себе игрок "В", в игре против разумного противника, если на протяжении всей игры он будет использовать одну и только одну стратегию.

Найдем в каждом столбце платежной матрицы максимальный элемент и запишем его в дополнительную строку снизу ( Выделена желтым цветом см. Табл.2 ).

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

Таблица 2
Стратегии "B"
Стратегии "A" B1 B2 Минимумы строк
A1 3 5 3*
A2 6
3
2
3
2
Максимумы столбцов 6 5+

В нашем случае верхняя цена игры равна: β = 5, и для того чтобы гарантировать себе проигрыш не хуже чем 5 противник ( игрок "B") должен придерживаться стратегии B2


Шаг:3
Сравним нижнюю и верхнюю цены игры, в данной задаче они различаются, т.е. α ≠ β, платежная матрица не содержит седловой точки. Это значит, что игра не имеет решения в чистых минимаксных стратегиях, но она всегда имеет решение в смешанных стратегиях.

Смешанная стратегия, это чередуемые случайным образом чистые стратегии, с определенными вероятностями (частотами).

Смешанную стратегию игрока "А" будем обозначать
SA =
A1A2
p1p2

где A1, A2 - стратегии игрока "A", а p1, p2 - соответственно вероятности (частоты), с которыми эти стратегии применяются, причем p1 + p2 = 1.

Аналогично смешанную стратегию игрока "В" будем обозначать
SB =
B1B2
q1q2

где B1, B2 - стратегии игрока "B", а q1, q2 - соответственно вероятности, с которыми эти стратегии применяются, причем q1 + q2 = 1.

Оптимальная смешанная стратегия для игрока "А" та, которая обеспечивает ему максимальный выигрыш. Соответственно для "B" - минимальный проигрыш. Обозначаются эти стратегии SA* и SB* соответственно. Пара оптимальных стратегий образует решение игры.

В общем случае в оптимальную стратегию игрока могут входить не все исходные стратегии, а только некоторые из них. Такие стратегии называются активными стратегиями.


Шаг:4
Найдем оптимальную смешанную стратегию для игрока "A":
SA* =
A1A2
p1 p2

где:  p1 , p2 - вероятности (частоты) с которыми применяются соответственно стратегии A1 и A2

Из теории игр известно, что если игрок "А" использует свою оптимальную стратегию, а игрок "B" остается в рамках своих активных стратегий, то средний выигрыш остается неизменным и равным цене игры v независимо от того как игрок "В" использует свои активные стратегии. А в нашем случае обе стратегии активные, иначе игра бы имела решение в чистых стратегиях. Поэтому если предположить, что игрок "В" будет пользоваться чистой стратегией B1, то средний выигрыш v составит:
k11p1 + k21p2 = v    ( 1 )
где:  kij - элементы платежной матрицы.

C другой стороны, если предположить, что игрок "В" будет пользоваться чистой стратегией B2, то средний выигрыш составит:
k12p1 + k22p2 = v    ( 2 )
Приравняв левые части уравнений (1) и (2) получим:
k11p1 + k21p2 = k12p1 + k22p2
А с учетом того, что p1 + p2 = 1 имеем:
k11p1 + k21(1 - p1) = k12p1 + k22(1 - p1)

Откуда несложно найти оптимальную частоту стратегии A1:
p1 = 
k22 - k21
k11 + k22 - k12 - k21
    ( 3 )
В данной задаче:
p1 = 
3
2
 -  6
3  + 
3
2
 -  5  -  6
 = 
9
13

Вероятность р2 найдем вычитанием р1 из единицы:
p2 = 1 - p1 =  1  - 
9
13
 = 
4
13


Шаг:5

Вычислим цену игры подставив р1, р2 в уравнение (1) :
v = k11p1 + k21p2  =  3  · 
9
13
 +  6  · 
4
13
 = 
51
13


Шаг:6
Найдем оптимальную смешанную стратегию для игрока "B":
SB* =
B1B2
q1 q2

где:  q1 , q2 - вероятности (частоты) с которыми применяются соответственно стратегии B1 и B2

Из теории игр известно, что если игрок "B" использует свою оптимальную стратегию, а игрок "A" остается в рамках своих активных стратегий, то средний выигрыш остается неизменным и равным цене игры v независимо от того как игрок "А" использует свои активные стратегии. Поэтому если предположить, что игрок "A" будет пользоваться чистой стратегией A1, то средний выигрыш v составит:
k11q1 + k12q2 = v    ( 4 )

Поскольку цена игры v нам уже известна и учитывая, что q1 + q2 = 1, то оптимальная частота стратегии B1 может быть найдена как:
q1 = 
v - k12
k11 - k12
    ( 5 )
В данной задаче:
q1 = 
51
13
 -  5
3  -  5
 = 
7
13

Вероятность q2 найдем вычитанием q1 из единицы:
q2 = 1 - q1 =  1  - 
7
13
 = 
6
13

Ответ:


Нижняя цена игры :  α =  3
Верхняя цена игры :  β =  5
Цена игры :  v = 
51
13
Оптимальная стратегия игрока "А" :
SA* =
A1A2
9
13
4
13

Оптимальная стратегия игрока "B" :
SB* =
B1B2
7
13
6
13

Геометрическая интерпретация (графическое решение):


Дадим геометрическую интерпретацию рассмотренной игре. Возьмем участок оси абсцисс единичной длины и проведем через его концы вертикальные прямые a1 и a2 соответствующие нашим стратегиям A1 и A2. Предположим теперь, что игрок "B" будет пользоваться стратегией B1 в чистом виде. Тогда, если мы (игрок "A") будем использовать чистую стратегию A1, то наш выигрыш составит 3.Отметим соответствующую ему точку на оси a1.
Если же мы будем использовать чистую стратегию A2, то наш выигрыш составит 6. Отметим соответствующую ему точку на оси a2
(см. Рис. 1). Очевидно, если мы будем применять, смешивая в различных пропорциях стратегии A1 и A2, наш выигрыш будет меняться по прямой проходящей через точки с координатами (0 , 3) и (1 , 6), назовем ее линией стратегии B1 (на Рис.1 показана красным цветом). Абсцисса любой точки на данной прямой равна вероятности p2 (частоте), с которой мы применяем стратегию A2, а ордината - получаемому при этом выигрышу k (см. Рис.1).

Рис.1 График зависимости выигрыша k от частоты р2 при использовании противником стратегии B1

Рисунок 1.
График зависимости выигрыша k от частоты р2, при использовании противником стратегии B1.

Предположим теперь, что игрок "B" будет пользоваться стратегией B2 в чистом виде. Тогда, если мы (игрок "A") будем использовать чистую стратегию A1, то наш выигрыш составит 5.Если же мы будем использовать чистую стратегию A2, то наш выигрыш составит 3/2 (см. Рис. 2). Аналогично, если мы будем смешивать в различных пропорциях стратегии A1 и A2, наш выигрыш будет меняться по прямой проходящей через точки с координатами (0 , 5) и (1 , 3/2), назовем ее линией стратегии B2. Как и в предыдущем случае, абсцисса любой точки на этой прямой равна вероятности, с которой мы применяем стратегию A2, а ордината - получаемому при этом выигрышу, но только для стратегии B2 (см. Рис. 2).

Рис.2 Графическое определение цены игры v и оптимальной частоты р2

Рисунок 2.
Графическое определение цены игры v и оптимальной частоты р2 для игрока "А".

В реальной игре, когда разумный игрок "В" пользуется всеми своими стратегиями, наш выигрыш будет изменяться по ломаной линии, показанной на Рис.2 красным цветом. Эта линия определяет так называемую нижнюю границу выигрыша. Очевидно, что самая высокая точка этой ломанной соответствует нашей оптимальной стратегии. В данном случае, это точка пересечения линий стратегий B1 и B2. Обратите внимание, что если выбрать частоту p2 равной ее абсциссе, то наш выигрыш будет оставаться неизменным и равным v при любой стратегии игрока "B", кроме того он будет максимальным который мы можем себе гарантировать. Частота (вероятность) p2, в этом случае, есть соответствующая частота нашей оптимальной смешанной стратегии. Кстати из рисунка 2 видна и частота p1, нашей оптимальной смешанной стратегии, это длина отрезка [p2 ; 1] на оси абсцисс. (Это потому, что p1 + p2 = 1 )

Совершенно аналогично рассуждая, можно найти и частоты оптимальной стратегии для игрока "В", что иллюстрируется на рисунке 3.

Рис.3 Графическое определение цены игры v и оптимальной частоты q2

Рисунок 3.
Графическое определение цены игры v и оптимальной частоты q2 для игрока "В".

Только для него следует построить так называемую верхнюю границу проигрыша (красная ломаная линия) и искать на ней самую низкую точку, т.к. для игрока "В" цель, это минимизация проигрыша. Аналогично значение частоты q1, это длина отрезка [q2 ; 1] на оси абсцисс.


см. пример с седловой точкой...

решить мою задачу...
на ввод условия...

к списку решаемых задач...
Яндекс цитирования Ramblers Top100 Союз образовательных сайтов