2.2. Принцип миинимакса решения матричных игр.

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

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

Рассмотрим реализацию этого принципа в игре с платежной матрицей (2.1), определив наилучшую для игрока А стратегию среди стратегий А₁,…,А_m и наилучшую для игрока В стратегию среди стратегий В₁,…,В_n.

Выбирая стратегию А_i, игрок А должен рассчитывать, что игрок В ответит на нее той стратегией В_j, для которой выигрыш игрока А минимален (а выигрыш игрока В, наоборот, максимален). Обозначим через _i наименьший выигрыш игрока А при выборе им стратегии А_i для всех возможных стратегий игрока В (наименьшее число в i-й строке платежной матрицы), т.е.

.

Среди всех чисел _i (i =1,…,m) выбираем наибольшее

.

Назовем  нижней ценой игры, или максимином. Это гарантированный выигрыш игрока А при любой стратегии игрока В. Стратегия, соответствующая максимину, называется максиминной стратегией (их может быть несколько).

Игрок В также заинтересован в увеличении своего выигрыша, а, значит, в уменьшении выигрыша игрока А. Выбирая стратегию В_j, он учитывает максимально возможный выигрыш игрока А. Обозначим (наибольшее число вj-м столбце матрицы Н). Среди всех чисел _j выберем наименьшее

.

и назовем  верхней ценой игры, или минимаксом. Это - гарантированный проигрыш игрока В ( с обратным знаком - гарантированный выигрыш игрока В). Стратегия, соответствующая минимаксу, называется минимаксной стратегией.

Пример 2.2. Найдем нижнюю и верхнюю цены игры для игры, заданной матрицей:

_.

При выборе стратегии А₁ (1-я строка матрицы) минимальный выигрыш игрока А равен₁=–3. При выборе стратегииА₂ (2-я строка матрицы) его минимальный выигрыш равен₂=–2. Гарантируя себе максимальный выигрыш при любых действиях игрока В, т.е. нижнюю цену игры=max(–3;–2)=–2, игрок А должен выбрать стратегиюА₂. Аналогично при выборе стратегииВ₁(1-й столбец) максимальный проигрыш игрока В равен 2 (когда игрок А использует стратегиюА₁):₁ = 2. При выборе стратегииВ₂(2-й столбец) максимальный проигрыш В равен 4:₂=4. Следовательно, гарантированный минимальный проигрыш игрока В определяется значением=min(2,4)=2, т.е. верхней ценой игры. При этом соответствующей минимаксной стратегией игрока В является стратегияВ₁.

Все расчеты удобнее производить cпомощью следующей таблицы:

	В1	В2	i=minj aij
A1	2	-3	-3
A2	-2	4	-2
j=maxi aij	2	4

Возникает естественный вопрос: можно ли считать таким образом найденные максиминные и минимаксные стратегии игроков безусловно оптимальными для них?

Анализ матричных игр позволяет отметить возможность возникновения двух принципиально различных ситуаций: 1) =, 2) . Рассмотрим подробно обе ситуации.

Пусть верхняя и нижняя цены игры совпадают: ==v, т. е. совпадают результаты стремлений игроков достичь своих максимальных выигрышей при самых неблагоприятных действиях противника. В этом случае общее значение v называют ценой игры, соответствующие стратегии А_i* и В_j*, при которых эти выигрыши достигаются, - оптимальными чистыми стратегиями, а их совокупность - решением. При этом решение игры обладает очень важным свойством устойчивости, а именно: если один из игроков придерживается своей оптимальной стратегии, то для другого игрока не может быть выгодным отклоняться от своей оптимальной стратегии. Математически это свойство выражается двойным неравенством:

Н(А_i , В_j*) Н(А_i*, В_j*) Н(А_i*, В_j ), (2.2)

которое справедливо для всех i=1,…,m, j=1,…,n.

Относительно платежной матрицы неравенство (2.2) означает, что ее элемент, стоящий на пересечении строки и столбца, которые соответствуют оптимальным стратегиям А_i* и В_j*, является одновременно минимальным в строке и максимальным в столбце. Поэтому такой элемент называют седловой точкой, а матричная игра, задаваемая такой матрицей, называется игрой с седловой точкой.

Пример 2.3. Рассмотрим игру, заданную платежной матрицей:

и попробуем найти ее решение.

В следующей таблице приведены все необходимые расчеты.

	В1	В2	В3	В4	minj aij
А1	5	0	3	-1	-1
А2	3	1**	2	2	1*
А3	1	0	-1	4	-1
maxi aij	5	1*	3	4

Нижняя цена игры =1 - наибольшее число в последнем столбце таблицы (отметим его знаком *); верхняя цена=1 – наименьшее число в последней строке таблицы (также отмечено *). Эти значения равны. Следовательно, это – игра с седловой точкой (седловая точка отмечена **). Решение игры – пара оптимальных чистых стратегий игроков:А₂для игрока А иВ₂для игрока В; цена игрыv=1.

Второй случай ( когда  ) более сложен для анализа. Конечно, максиминная и минимаксная стратегии позволяют игрокам получить выигрыши, не меньшие определенных значений. Однако разница между верхней и нижней ценами игры оставляет игрокам возможности для маневров, что проявляется в отсутствии седловой точки, а значит, и в неустойчивости гипотетического решения игры. Проиллюстрируем эту ситуацию на примере.

Пример 2.3. Пусть игра задана матрицей

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

	В1	В2	В3	minj aij
А1	1.5	-2	3	-2
А2	0.5	1	0	0*
А3	1	4	-1	-1
maxi aij	1.5*	4	3

Как видим, нижняя и верхняя цены игры равны соответственно =0 и =1.5; А₂ - максиминная стратегия игрока А; В₁ – минимаксная стратегия игрока В. Являются ли эти стратегии оптимальными для игроков?

Представим, что игрок А узнал, что В придерживается минимаксной стратегии В₁ (1-й столбец матрицы). Тогда А выгоднее отказаться от своей максиминной стратегии, при которой его выигрыш равен 0.5, и выбрать стратегию А₁, где его выигрыш равен 1.5. Однако, если В тоже узнал, что игрок А будет придерживаться стратегии А₁ (1-я строка), то он со своей стороны выберет стратегию В₂, сводя выигрыш к -2. При наличии этой новой информации игрок А снова изменит свою стратегию на А₃, выигрывая 4, и. т. д. Партнеры заметались по стратегиям, не зная, что лучше выбрать…

Подведем итог. В случае  пара, состоящая из максиминной и минимаксной стратегий игроков, вряд ли может считаться вполне оптимальной для них. Тем не менее можно сказать, эти стратегии приемлемы для игроков, если выполняются 3 условия:

а) игра состоит из одной партии, т.е. игроки выбирают свои стратегии А_i и В_j по одному разу и получают выигрыши, указанные в платежной матрице, согласно возникшей ситуации (А_i,В_j);

б) отсутствует всякая информация о будущих действиях игроков;

в) оба игрока стоят на позициях крайнего пессимизма и при выборе своих стратегий руководствуются принципом минимакса.

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