2
Оптимальные стратегии
Простейший
вид стратегической игры – игра двух лиц с нулевой суммой (сумма выигрышей
сторон равна нулю). Игра состоит из двух ходов: игрок А выбирает одну из своих возможных стратегий Аi ( i= 1, 2, …, m), а игрок В
выбирает стратегию Вj ( j= 1, 2, …, n), причем
каждый выбор производится при полном незнании выбора другого игрока. В
результате выигрыши
и
каждого из игроков
удовлетворяют соотношению
, (1)
откуда, если
, имеем
.
. (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, позволяющая ограничить его
проигрыш этим же числом. Легко видеть, что отклонение одного из игроков от
оптимальной стратегии приводит к уменьшению выигрыша (для игрока А) и
увеличению проигрыша (для игрока В).