Исключение доминируемых стратегий

Рассмотрим игру m ´ n, заданную платежной матрицей:

.

При постановке задач, необходимо иметь в виду некоторые преобразования, которые помогают упростить сложную задачу путем изменения – уменьшения размерности платежной матрицы посредством выделения и исключения доминируемых и дублирующих стратегий. Стратегия игрока Аi доминирует над стратегией Ак, если при любом поведении противника даст не меньший выигрыш, а если такой же, то дублирует Ак. В таком случае все элементы i строки больше (доминируют) или равны (дублируют) всех элементов строки k.

Пример. С учетом вариантов конъюнктуры В1, В2, В3, В4, В5 сложившейся на рынке и поведения покупателей в микрорайоне города коммерческое предприятие разработало шесть технологий продажи товаров А1, А2, А3, А4, А5, А6. Найти оптимальное решение. Возможные варианты среднедневного товарооборота в млн.руб. приведены в таблице:

  В1 В2 В3 В4 В5
А1 0,4 0,9 0,5 0,5 0,6
А2 0,6 0,5 0,7 0,8 0,9
А3 0,6 0,3 0,8 0,6 0,7
А4 0,3 0,8 0,5 0,4 0,3
А5 0,1 0,3 0,5 0,4 0,3
А6 0,4 0,8 0,5 0,4 0,5

 

Стратегия А1 доминирует над стратегией А6, а стратегия А4 доминирует над стратегией А5, следовательно исключаем 5 и 6 строки матрицы

  В1 В2 В3 В4 В5
А1 0,4 0,9 0,5 0,5 0,6
А2 0,6 0,5 0,7 0,8 0,9
А3 0,6 0,3 0,8 0,6 0,7
А4 0,3 0,8 0,5 0,4 0,3

 

С позиций проигрышей строки В стратегии В3, В4 и В5 доминируют над стратегией В1, поэтому эти столбцы исключаем из таблицы:

  В1 В2
А1 0,4 0,9
А2 0,6 0,5
А3 0,6 0,3
А4 0,3 0,8

 

С позиций игрока А стратегия А1 доминирует над стратегией А4, а стратегия А2 доминирует над стратегией А3, следовательно исключаем 3 и 4 строки матрицы:

  В1 В2
А1 0,4 0,9
А2 0,6 0,5

 


Метод линейного программирования


Допустим, что все элементы (выигрыши) платежной матрицы положительны (aij ³ 0) (если это не так, то можно ко всем элементам прибавлять достаточно большое число M, сделав их положительными. При этом цена игры увеличится на M, а решение задачи и не изменится). Если все aij ³ 0, то g > 0. Пусть платежная матрица не содержит седловой точки, т.е. игра решается в смешанных стратегиях:

.

Применение игроком I оптимальной смешанной стратегии гарантирует ему средний выигрыш, не меньше цены игры g, независимо от поведения игрока II. Игрок II, применяя оптимальную смешанную стратегию гарантирует для себя минимальный проигрыш (не больше g).

Если игрок II применяет свою чистую стратегию Bj, а игрок I — свою оптимальную стратегию , то средний выигрыш игрока I равен:

Если игрок I применяет чистую стратегию Аi, а игрок II – свою оптимальную смешанную стратегии , то средний выигрыш игрока II составит

Учитывая, что gj не может быть меньше g для игрока I, а и не может быть больше g для игрока II, двойственную задачу линейного программирования можно записать следующим образом:

1) для игрока I:

2) для игрока II:

Смысл этих систем уравнений заключается в следующем: игрок I стремится увеличить цену игры (g ® max), он действует так, чтобы его средний выигрыш при использовании его стратегий с вероятностями pi для любой j-й стратегии игрока II был не меньше величины g, которую он стремится увеличить. Игрок II стремится уменьшить свой проигрыш (g ® min), т.е. он действует так, чтобы его средний проигрыш при использовании его стратегий с вероятностями qj при любой i-й стратегии игрока I не превышал величину g, которую он стремится уменьшить.

Задача состоит в нахождении двух оптимальных смешанных стратегий и , которые дают для игрока I максимально возможный для него средний выигрыш, а для игрока II минимально возможный для него средний проигрыш.

Разделив левую и правую части неравенств на цену игры g > 0, получим:

Введем обозначения:

Тогда выражения примут следующий вид:

Из равенств и следует, что переменные xi и yj должны удовлетворяют условиям:

Учитывая, что игрок I стремится максимизировать g, а игрок II стремится минимизировать g, переменные xi и yj должны быть выбраны так, чтобы целевая функция достигала минимума, а целевая функция достигала максимума.

Таким образом, задача решения игры сводится к задаче линейного программирования. Оптимальные стратегии и игры с платежной матрицей А могут быть найдены путем решения симметричной пары двойственных задач линейного программирования:

Решая их, находим xi, yj, цену игры g и оптимальные стратегии и .

или

Решение игры симплекс-методом

Пример. Найти решение матричной игры с платежной матрицей:

Решение. Матричной игре с данной платежной матрицей будет соответствовать пара двойственных задач линейного программирования:

 

Найти минимум функции F(Х) = x1 + x2 + x3 при ограничениях:

 

 

Найти максимум функции T(Y) = y1 + y2 + y3 при ограничениях:

Здесь

 

Решаем последнюю задачу симплексным методом.

Базисные перемен- ные ДО
-1 -1 -1  
5/3
1/3
2/3 8/3 2/3 -1/3
-2/3  
1/4 9/4 -1/8 -5/8
1/4
1/4
-1/2  
 
 
 
 
     

 

Решение этой задачи

.

Тогда цена игры а вероятности применения стратегий игрока II будут:

Из симплекс-таблицы находим решение двойственной задачи:

Следовательно, вероятности применения стратегий игрока I:

,

таким образом, оптимальные смешанные стратегии игроков:

, , .