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

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

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

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

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

.

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

.

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

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

.

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

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

.

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

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

	В 1	В 2	ai=minj aij
A 1		-3	-3
A 2	-2		-2*
bj=maxi aij	2*

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

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

Пусть верхняя и нижняя цены игры совпадают: a = b = 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				-1	-1
А 2		1**			1*
А 3			-1		-1
maxi aij		1*

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

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

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

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

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

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

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

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

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

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

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

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

2.3. Смешанные стратегии. Основные свойства решений

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

Пусть матричная антагонистическая игра двух игроков А и В задана платежной матрицей

Здесь по-прежнему а_ij = Н (А_i, В_j) – выигрыш игрока А (проигрыш игрока В) в случае выбора игроком А стратегии А_i, а игроком В – стратегии В_j. Предположим также, что игра состоит из большого числа партий. Поэтому, стремясь к максимизации суммарного выигрыша, каждый игрок может свои стратегии «смешивать», чередуя с какой-либо частотой.

Смешанной стратегией игрока А назовем неотрицательный вектор вида S_А =(р ₁, р ₂,…, р_m), где р_i – вероятность применения игроком А стратегии А_i (i =1,…, m), причем р ₁+ р ₂+…+ р_m =1.

Cмешанной стратегией игрока В назовем неотрицательный вектор S_В =(q ₁, q ₂,…, q_n), где q_j – вероятность применения игроком В стратегии В_j (j=1,…,n), причем q ₁+ q ₂+…+ q_n =1.

В отличие от таким образом определенных смешанных стратегий, исходные стратегии игроков А_i и В_j, где i =1,…, m, j =1,…, n, называют чистыми. Однако заметим, что чистые стратегии можно считать частным случаем смешанных и задавать вектором, в котором 1 стоит на месте, соответствующем данной чистой стратегии, а остальные элементы – нули. Например, А ₂=(0,1,0,…,0).

В силу того, что в смешанных стратегиях игроки используют свои чистые стратегии случайным образом, мерилом успеха такого применения может служить математическое ожидание выигрыша (или средний выигрыш) игрока в одной партии. Пусть игроки А и В независимо друг от друга выбрали соответственно стратегии S_А =(р ₁,…, р_m) и S_В =(q ₁,…, q_n). Тогда вследствие известных утверждений теории вероятности, математическое ожидание выигрыша игрока А в одной партии равно:

(2.3)

Руководствуясь принципом минимакса, каждый игрок стремится в наибольшей степени увеличить свой гарантированный средний выигрыш. Значение гарантированного среднего выигрыша игрока А в одной партии определяется выражением:

(2.4)

(аналог нижней цены игры a в случае чистых стратегий), а значение гарантированного среднего проигрыша игрока В - выражением:

(2.5)

(аналог верхней цены игры b). Здесь максимумы берутся по множеству всевозможных смешанных стратегий игрока А, а минимумы – по множеству смешанных стратегий игрока В. Основной результат теории матричных игр представлен теоремой фон Неймана о минимаксе.

Теорема. Для матричной игры с любой платежной матрицей Н величины a_S и b_S существуют и равны между собой. Более того, существует хотя бы одна пара смешанных стратегий S_A* и S_B*, для которых выполняется:

Н (S_A *, S_B *)= a_S =b_S.

При этом стратегии S_A * и S_B * называются оптимальными смешанными стратегиями; пара таких стратегий – решением игры в смешанных стратегиях, а общее значение v_S для a_S и b_S - ценой такой игры. Если v_S =0, то игра называется справедливой.

Как и в случае игры с седловой точкой, решение игры в смешанных стратегиях является устойчивым: если один из игроков придерживается своей оптимальной смешанной стратегии, то другому не может быть выгодно отступление от своей оптимальной стратегии. Иначе говоря, для произвольных смешанных стратегий S_A и S_B выполняется двойное неравенство:

H (S_A, S_B *)£ H (S_A *, S_B *) £ H(S_A *, S_B).

Отметим несколько важных свойств решений матричных игр.

Свойство 1. Игры, заданные платежными матрицами Н ⁽¹⁾ и Н ⁽²⁾ одинаковой размерности, элементы которых, а_ij ⁽¹⁾ и а_ij ⁽²⁾ связаны линейным соотношением: a_ij ⁽¹⁾= k×a_ij ⁽²⁾+ b, где k, b - некоторые действительные числа, имеют одинаковые решения в смешанных стратегиях. Цены таких игр v_S ⁽¹⁾ и v_S ⁽²⁾ связаны тем же соотношением: v_S ⁽¹⁾= k×v_S ⁽²⁾+ b.

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

Свойство 2. Для любой матричной игры справедливо двойное неравенство:

a £ v_S £ b (2.6)

где a и b - соответственно нижняя и верхняя цены игры, v_S – цена игры в смешанных стратегиях.

В частности, для игры с седловой точкой неравенство (2.6) имеет вид двойного равенства.

Прежде чем формулировать третье свойство, введем в рассмотрение новое понятие.

Пусть S_A *=(p ₁*,…, p_m *), S_B *=(q ₁*,…, q_n *) - пара смешанных стратегий. Если чистая стратегия входит в оптимальную смешанную стратегию с отличной от 0 вероятностью, то она называется активной (полезной).

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

Это утверждение имеет большое практическое значение, оно лежит в основе многих конкретных способов решения матричных игр.