II. Игры с нулевой суммой

Тема 1. Выбор стратегии

Примем за основу гипотезу крайней осторожности – гипотезу антагонизма: «При выборе стратегии надо рассчитывать на самый худший возможный вариант». Как в этом случае можно оценить ту или иную стратегию?

Встанем на позицию игрока I. Выбрав свою i-ю стратегию, игрок I может получить в зависимости от выбора игрока II один из возможных выигрышей a_i1, a_i2, … , a_in. В худшем случае игрок I получит выигрыш

Число называется гарантированным результатом – наименьшим возможным выигрышем игрока I при выборе им i-ой стратегии.

Надо выбрать такую стратегию i, при которой гарантированный выигрыш будет наибольшим. Наибольший гарантированный выигрыш игрока I будет

Число называется наибольшим гарантированным результатом (выигрышем) игрока I в игре.

Выбранная таким образом стратегия называется максиминной для игрока I – его выигрыш в любом случае будет не меньше максиминного значения (или нижней цены игры).

Проведем аналогичные рассуждения за игрока II.

В качестве оценки j-ой стратегии игрока II выступает его максимальный возможный проигрыш при использовании им j-ой стратегии, т.е. гарантированный результат игрока II при использовании им j-ой стратегии равен

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

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

Из алгебры матриц известно, что для произвольной прямоугольной матрицы всегда выполняется неравенство

Если верхняя цена игры равна нижней, т.е. ,то значение v называется ценой игры, а соответствующий ему элемент – седловой точкой матрицы.

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

Принцип оптимальности в антагонистической игре заключается в следующем: ситуация в игре является оптимальной, если от нее ни одному из игроков невыгодно отклоняться. Определенная таким способом оптимальная ситуация называется равновесной ситуацией, а принцип оптимальности, основанный на построении равновесной ситуации, ­­–принципом равновесия.

Теорема. Для того чтобы в матричной игре существовала ситуация равновесия, необходимо и достаточно выполнение равенства .

Пример 1. Пусть у игрока I две стратегии, а у игрока II – три стратегии, причем матрица выигрышей для игрока I имеет вид

.

Найти седловую точку матрицы А, т.е. определить цену игры.

, для I игрока максимином является 1-ая стратегия.

, для II игрока минимаксом является 2-ая стратегия.

Седловой точкой матрицы выигрышей является элемент , v

Пример 2.Рассмотрим игру с матрицей A =

Нижняя цена игры:

Верхняя цена игры:

следовательно, седловой точки нет.

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