Решение матричной игры в смешанных стратегиях

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

Смешанной стратегией игрока  называют вектор  где

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

Функцию  называют платежной или функцией выигрыша.

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

Величину  называют ценой игры.

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

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

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

Пусть имеем игру размерности   с матрицей:

Обозначим через  оптимальные смешанные стратегии игроков  к . Стратегия  игрока  гарантирует ему выигрыш не меньше , независимо от выбора стратегии , игроком . Это можно записать так:

где .

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

где .

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

Преобразуем системы неравенств, разделив обе части каждого неравенства на положительное число , и введем новые обозначения   ;  . Получим:

где:

где

Так как игрок А стремится максимизировать цену игры , то обратная величина  будет минимизироваться, поэтому оптимальная стратегия игрока А определится из задачи линейного программирования следующего вида:

найти минимальное значение функции  при  ограничениях (1) и (2).

Оптимальная смешанная стратегия игрока  определится решением задачи следующего вида:

найти максимальное значение функции  при  ограничениях (3) и (4).

Решив пару двойственных задач графическим (для случая двух переменных) или симплексным методом, далее определим:

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

и из строки целевой функции последней симплекс-таблицы, содержащей компоненты оптимального вектора, выписать значения компонент оптимального вектора двойственной задачи.

При поиске оптимальных стратегий в матричных играх размерностей  и  целесообразно использовать графический метод решения ЗЛП и свойства оптимальных планов пары двойственных задач: если в оптимальном плане задачи переменная положительна, то соответствующее ограничение двойственной задачи ее оптимальным планом обращается в равенство; если оптимальным планом задачи ограничение обращается в строгое неравенство, то в оптимальном плане двойственной задачи соответствующая переменная равна нулю.