2 Оптимальные стратегии

 

Простейший вид стратегической игры – игра двух лиц с нулевой суммой (сумма выигрышей сторон равна нулю). Игра состоит из двух ходов: игрок А выбирает одну из своих возможных стратегий  Аi ( i= 1, 2, …, m),  а игрок В выбирает стратегию Вj ( j= 1, 2, …, n), причем каждый выбор производится при полном незнании выбора другого игрока. В результате выигрыши   и  каждого из игроков удовлетворяют соотношению

,                            (1)

откуда, если , имеем

Цель игрока А – максимизировать функцию , в свою очередь, цель игрока В – минимизировать эту же функцию. Каждый из игроков может выбирать одну из переменных, от которых зависит значение функции. Если игрок А выбирает некоторую из стратегий Аi, то это само по себе не может влиять на значение функции . Влияние Аi на величину значения  является неопределенным; определенность имеет место только после выбора, исходя из принципа минимизации , другим игроком переменной Вj. При этом Вj определяется другим игроком. Пусть . Составим матрицу А:

.

 

Строки матрицы соответствует стратегиям Аi, столбцы – стратегиям Вj. Матрица А называется платежной или матрицей игры. Элемент аij матрицы – выигрыш игрока А, если он выбрал стратегию Аi, а игрок В выбрал стратегию Вj.

Пусть игрок А выбирает некоторую стратегию Аi; тогда в наихудшем случае (например, если выбор станет известным игроку В) он получит выигрыш, равный . Предвидя такую возможность, игрок А должен выбрать такую стратегию, чтобы максимизировать свой минимальный выигрыш a:

.                                     (2)

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

Игрок В, выбирая стратегию, исходит из следующего принципа: при выборе некоторой стратегии Вj его проигрыш не превысит максимального из значений элементов j-го столбца матрицы, т.е. меньше или равен . Рассматривая множество  для различных значений j, игрок В, естественно, выберет такое значение j, при котором его максимальный проигрыш b минимизируется:

                                                             (3)

Величина b называется верхней ценой игры, а соответствующая выигрышу b стратегия Вj  – минимаксной.

Фактический выигрыш игрока А при разумных действиях партнеров ограничен нижней и верхней ценой игры. Если же эти выражения равны, т.е.

                       ,               (4)

то выигрыш игрока А – вполне определенное число, игра называется вполне определенной, а выигрыш (4.4) называется значением игры и равен элементу матрицы . Вполне определенные игры иногда называют играми с седловой точкой. Элемент в матрице такой игры является одновременно минимальным в строке i0, максимальным в столбце j0 и называется седловой точкой. Седловой точке соответствуют оптимальные  стратегии игроков, их совокупность – это решение игры, которое обладает следующим свойством: если один из игроков придерживается своей оптимальной стратегии, то для другого отклонение от его оптимальной стратегии не может быть выгодно.

Пример 1 Определить нижнюю и верхнюю цены для игр, заданных платежными матрицами А1 и А2 :

.

Решение. Минимальные значения  в строках матрицы А1 равны соответственно 2, 3, 1. Максимальное значение из них равно 3. Следовательно, a1 – нижняя цена игры, которой соответствует матрица А1, равна 3.

Для определения b1 (верхней цены данной игры) найдем максимальные значения элементов в столбцах матрицы. По столбцам соответственно имеем: 4, 5, 6, 5. Следовательно, b1 = 4. Для матрицы А2

a2 = max{0; 2; –1} =2,      b2= min {3; 2; 4; 5} =2.

Таким образом, a2 = b2= v – цена игры. Решение данной игры состоит в выборе игроком А стратегии А2, при  этом его выигрыш не меньше 2; для игрока В оптимальной является стратегия В2, позволяющая ограничить его проигрыш этим же числом. Легко видеть, что отклонение одного из игроков от оптимальной стратегии приводит к уменьшению выигрыша (для игрока А) и увеличению проигрыша (для игрока В).