Матричные игры без седловой точки.

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

Смешанные стратегии определяются с помощью вероятностей , приписываемых игроком A его n возможным стратегиям и вероятностей , приписываемых игроком B его стратегиям , причем:

, ,

В игре со смешанными стратегиями A стремится максимизировать минимум математического ожидания (средний выигрыш) посредством выбора , тогда как B стремится минимизировать путем выбора .

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

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

Теорема минимакса. Для любой заданной матрицы выигрышей существует хотя бы одно решение, то есть пара оптимальных смешанных стратегий: для игрока А и S_B( ) для игрока В:

Каждая конечная игра двух партнеров с нулевой суммой имеет по меньшей мере одно решение, определяемое оптимальными смешанными стратегиями и . Возможно есть несколько решений, но цена игры V единственна.

Связь матричных игр с линейным программированием

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

Из этого следует, что всегда можно, увеличив элементы матрицы на какое-либо число, добиться, чтобы цена игры стала положительной v>0. Поэтому далее будем считать, что v>0.

При использовании оптимальной смешанной стратегии игроком А его выигрыш будет не меньше цены игры v, в том числе при условии, что противник выберет чистую стратегию В_к . Получаем систему неравенств:

Введем обозначения (i = 1,..., n). Так как вероятности неотрицательны и v>0, то и . Перепишем систему неравенств с новыми переменными

(*)

Учитывая, что , сумма новых переменных ,

Цена игры для первого игрока должна быть как можно больше , поэтому величина должна быть как можно меньше.

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

Аналогично, с точки зрения игрока В: его проигрыши при использовании им оптимальной смешанной стратегии S_B( ) не могут превышать цену игры, в том числе, если А применяет одну из чистых стратегий А_i. Обозначив (k = 1,…,m) и целевую функцию , получим двойственную ЗЛП.

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

Пример. Рассмотрим платежную матрицу без седловой точки, полученную в предыдущем примере . Найти решение задачи в области смешанных стратегий. ► Пусть сторона А использует первую стратегию с вероятностью p₁, вторую стратегию с вероятностью p₂. Обозначив , , получим систему ограничений:

Целевая функция

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

Из оптимального решения ЗЛП найдем:

.

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

Используя равенство экстремальных значений целевых функций в двойственных задачах линейного программирования, легко найти оптимальную смешанную стратегию второго игрока: . ◄