Лекция: Графический метод решения матричных игр.

В настоящем пункте мы остановимся на очень простом классическом способе поиска оптимальных смешанных стратегий в матричных играх, где один из участников имеет только две стратегии (это так называемые 2 х п и т х 2 игры).

Для определенности положим, что игрок I имеет возможность выбирать между двумя стратегиями с вероятностями x1 и x2 = 1-x1, тогда его ожидаемые выигрыши, соответствующие чистым стратегиям игрока II, примут вид

или

т. е. ожидаемые выигрыши могут быть представлены в виде графиков линейных функций, зависящих от переменной x1 ∊ [0; 1] (рис. 6.1, где предполагается, что игрок II имеет три стратегии).

Линии, изображенные на рис. 6.1, задают зависимости среднего выигрыша игрока I от значения вероятности x1, с которой он выбирает свою первую стратегию, для случаев, когда его противник выбирает первую, вторую или третью чистую стратегию. Тогда значениям минимального гарантированного дохода первого игрока соответствует нижняя огибающая всех трех прямых. Согласно принципу максимина, оптимальному выбору игрока I будет соответствовать наивысшая точка, лежащая на данной огибающей, отмеченная на рисунке как (x1*, z*). Зная ее, можно определить оптимальную смешанную стратегию первого игрока х* = (x1*, 1-x2*) и цену игры, равнуюz*.

Исходя из отношения двойственности, которым, как было установлено в п. 6.1.5, связаны задачи обоих игроков, по оптимальной стратегии первого участника х* однозначно определяется оптимальная стратегия его противника у*. Поскольку у* является результатом решения задачи линейного программирования, то он обладает всеми свойствами допустимого базисного плана, т. е. в случае 2 х п игры имеет не более чем две ненулевых компоненты и не менее чем (п-2) нулевых. Номера ненулевых элементов у* определяются номерами линий, пересечение которых определило оптимальную стратегию первого игрока. Действительно, игрок II знает оптимальную стратегию соперника, и применение им стратегий, соответствующих прямым, проходящим выше точки (х1*, z*), только увеличило бы его проигрыш.

В рассматриваемом примере это линии z2 и z3, и, следовательно, в своей оптимальной стратегии второй игрок должен с ненулевыми вероятностями применять вторую и третью чистые стратегии (у2>0, у3 >0). На основе этого, а также учитывая условие нормировки

можем выразить: y3 = l – y2 тогда оптимальное значение y2* может быть найдено из условия

или

В результате получаем оптимальную стратегию игрока II у*= (0, у2*, у3*).

Очевидно, что поиск решения в игре т х 2 осуществляется аналогичным образом с точностью до наоборот: строятся графики ожидаемого проигрыша игрока II, находится их верхняя огибающая и т. д.

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

61. Алгебраический метод решения матричных игр.