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

Пусть у игроков А и В соответственно m и n чистых стратегий, которые обозначим через и .

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

Платежную матрицу удобно также представить в виде таблицы 5

			¼
			¼
			¼
¼	¼	¼	¼	¼
			¼

В ее строках расположены чистые стратегии игрока А, а в столбцах – чистые стратегии игрока В.

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

Число a называют нижней ценой игры и является гарантированным выигрышем игрока А.

Очевидно, a находится в одной из строк матрицы H, к примеру в строке . Тогда стратегию называют максиминной, т.к. .

В свою очередь игрок В, стремясь минимизировать проигрыш и используя принцип осторожности, сначала для каждой чистой стратегии найдет максимально возможный проигрыш – , а затем среди выберт минимальное значение . Ему будет соответствовать чистая стратегия , называемая минимаксной, т.к. . Число называют верхней ценой игры. Оно показывает какой максимальный проигрыш может быть у игрока В. Таким образом, правильно используя чистые стратегии, игрок А обеспечит выигрыш не меньше a, а игрок В не позволит игроку А выиграть больше чем b.

Рассмотрим примеры нахождения и .

Пример 1. Пусть игра задана платежной матрицей :

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

Верхняя и нижняя цены игры совпали: .

Пример 2. Задана платежная матрица

Здесь .

Теорема 1. В любой матричной игре нижняя цена игры не превосходит верхней цены игры, т.е. .

Обозначим через и номера чистых стратегий, при котором . Пару чистых стратегий и при этом называют седловой точкой игры, а – седловым элементом платежной матрицы.

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