Приведение матричной игры к задаче линейного программирования

Приведение матричной игры к задаче линейного программирования. Игра mn в общем случае не имеет наглядной геометрической интерпретации. Е решение достаточно трудомко при больших m и п, однако принципиальных трудностей не имеет, поскольку может быть сведено к решению задачи линейного программирования.

Покажем это. Пусть игра mn задана платжной матрицей р, i 1, 2 m j 1, 2 n. Игрок А обладает стратегиями, игрок В стратегиями. Необходимо определить оптимальные стратегии и, где вероятности применения соответствующих чистых стратегий Оптимальная стратегия удовлетворяет следующему требованию.

Она обеспечивает игроку А средний выигрыш, не меньший, чем цена игры v, при любой стратегии игрока В и выигрыш, равный цене игры v, при оптимальной стратегии игрока В. Без ограничения общности полагаем v 0 этого можно добиться, сделав все элементы 0. Если игрок А применяет смешанную стратегию против любой чистой стратегии игрока В, то он получает средний выигрыш, или математическое ожидание выигрыша 2 п т.е. элементы j-го столбца матрицы почленно умножаются на соответствующие вероятности стратегий результаты складываются.

Для оптимальной стратегии все средние выигрыши не меньше цены игры v, поэтому получаем систему неравенств 3 Каждое из неравенств можно разделить на число v 0. Введм новые переменные v, v v. Тогда система примет вид 4 Цель игрока А максимизировать свой гарантированный выигрыш, т.е. цену игры v. Разделив на равенство, получаем, что переменные i 1, 2 т удовлетворяют условию v. Максимизация цены игры v эквивалентна минимизации величины 1v, поэтому задача может быть сформулирована следующим образом определить значения переменных 0, i 1, 2 т, так чтобы они удовлетворяли линейным ограничениям и при этом линейная функция 5 обращалась в минимум. Это задача линейного программирования.

Решая задачу 3-4, получаем оптимальное решение и оптимальную стратегию. Для определения оптимальной стратегии следует учесть, что игрок В стремится минимизировать гарантированный выигрыш, т.е. найти. Переменные удовлетворяют неравенствам 6 которые следуют из того, что средний проигрыш игрока В не превосходит цены игры, какую бы чистую стратегию не применял игрок А. Если обозначить v 2 п, 7 то получим систему неравенств 8 Переменные j 1, 2 n, удовлетворяют условию. Игра свелась к следующей задаче.

Определить значения переменных, j1, 2 n, которые удовлетворяют системе неравенств и максимизируют линейную функцию 9 Решение задачи линейного программирования определяет оптимальную стратегию. При этом цена игры v 1max 1min . 10 Составив расширенные матрицы для задач 4, 5 и 8, 9, убеждаемся, что одна матрица получилась из другой транспортированием Таким образом, задачи линейного программирования 4, 5 и 6, 9 являются взаимно-двойственными.

Очевидно, при определении оптимальных стратегий в конкретных задачах следует выбрать ту из взаимно-двойственных задач, решение которой менее трудомко, а решение второй задачи найти с помощью теорем двойственности.

При решении произвольной конечной игры размером рекомендуется придерживаться следующей схемы 1. Исключить из платежной матрицы заведомо невыгодные стратегии по сравнению с другими стратегиями. Такими стратегиями для игрока A игрока B являются те, которым соответствуют строки столбцы с элементами, заведомо меньшими большими по сравнению с элементами других строк столбцов. 2. Определить верхнюю и нижнюю цены игры и проверить имеет ли игра седловую точку.

Если седловая точка есть, то соответствующие ей стратегии игроков будут оптимальными, а цена совпадет с верхней нижней ценой. 3. Если седловая точка отсутствует, то решение следует искать в смешанных стратегиях. Для игр размером рекомендуется симплексный метод, для игр размером 2х2, 2хn, nх2 возможно геометрическое решение. На практике реализация оптимального решения в смешанных стратегиях может происходить несколькими путями.

Первый состоит в физическом смешении чистых стратегий Ai в пропорциях, заданных вероятностями pi. Другой путь - при многократном повторении игры - в каждой партии чистые стратегии применяются в виде случайной последовательности, причм каждая из них с частотой, равной ее вероятности в оптимальном решении.