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

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

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

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

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

.

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

.

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

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

.

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

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

.

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

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

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

Анализ матричных игр позволяет отметить возможность возникновения двух принципиально различных ситуаций: 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. Рассмотрим игру, заданную платежной матрицей:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Cмешанной стратегией игрока В назовем неотрицательный вектор SВ=(q1,q2,…,qn ), где qj – вероятность применения игроком В стратегии Вj (j=1,…,n), причем q1+q2+…+qn=1.

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

В силу того, что в смешанных стратегиях игроки используют свои чистые стратегии случайным образом, мерилом успеха такого применения может служить математическое ожидание выигрыша (или средний выигрыш) игрока в одной партии. Пусть игроки А и В независимо друг от друга выбрали соответственно стратегии SА=(р1,…,рm) и SВ=(q1,…,qn). Тогда вследствие известных утверждений теории вероятности, математическое ожидание выигрыша игрока А в одной партии равно:

(2.3)

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

(2.4)

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

(2.5)

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

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

Н(SA*,SB*)=aS =bS .

При этом стратегии SA* и SB* называются оптимальными смешанными стратегиями; пара таких стратегий – решением игры в смешанных стратегиях, а общее значение vS для aS и bS — ценой такой игры. Если vS=0, то игра называется справедливой.

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

H(SA,SB*)£H(SA*,SB*) £ H(SA*,SB).

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

Свойство 1. Игры, заданные платежными матрицами Н(1) и Н(2) одинаковой размерности, элементы которых, аij(1) и аij(2) связаны линейным соотношением: aij(1)=k×aij(2)+b, где k, b — некоторые действительные числа, имеют одинаковые решения в смешанных стратегиях. Цены таких игр vS(1) и vS(2) связаны тем же соотношением: vS(1)=k×vS(2)+b.

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

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

a £ vS£ b (2.6)

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

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

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

Пусть SA*=(p1*,…,pm*), SB*=(q1*,…,qn*) — пара смешанных стратегий. Если чистая стратегия входит в оптимальную смешанную стратегию с отличной от 0 вероятностью, то она называется активной ( полезной ).

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

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