85776 (Матричные антагонистические игры с нулевой суммой в чистых стратегиях), страница 5

Теорема о минимаксе.

Можно доказать, что для любой функции F(x,y) определённой на произвольном декартовом произведении X × Y имеет место неравенство . Отсюда следует, что

Запишем 2 утверждения:

Утверждение 1. Точка 0 (в m-мерном пространстве) содержится в выпуклой оболочке m+n точек

и

Утверждение 2. Существуют числа удовлетворяющие условиям

Доказательство: Пусть А – матричная игра. Имеет место либо утверждение 1, либо утверждение 2. Если верно утверждение 1 то 0 является выпуклой линейной комбинацией m+n векторов. Поэтому существуют такие

что

Если бы все числа были бы равны нулю, то 0 оказывался бы выпуклой линейной комбинацией m единичных векторов , что невозможно, т.к. они линейно независимы. Следовательно, по крайней мере одно из чисел положительно и

тогда можно положить

и получится для всех i

Значит и

Предположим, что верно утверждение 2. Тогда , так что . Следовательно, неравенство не имеет смысла. Предположим, что игра А изменена на игру , где . Для любых х и y , поэтому . Так как неравенство не имеет смысла, то неравенство также не выполняется. Но k произвольно. Значит неравенство невозможно. Т.к. то . Что и требовалось доказать.

Принцип минимакса.

Рассмотрим игру с платежной матрицей Следует определить наилучшую стратегию игрока I среди стратегий , и игрока II среди стратегий , . Определение наилучших стратегий игроков основано на принципе, который предполагает, что противники, участвующие в игре, одинаково разумны и каждый из них делает все для того, чтобы добиться своей цели. Найдем наилучшую стратегию игрока I. Допустим, что он выбрал i-ю стратегию (i –ю строку матрицы (1)). Тогда он получит меньше, чем – наименьшее число в этой строке. Причем это будет в том случае, если игрок II каким-то образом раскроет стратегию игрока I. Из сказанного следует, что I игрок, если он не желает рисковать, т.е. играть не оптимально, должен действовать следующим образом – определить наименьшие элементы всех строк и выбрать ту из них, в которой это число наибольшее. В этом случае он гарантирует себе выигрыш равный наибольшему из меньших чисел всех строк. Этот выигрыш равен Число это “низкий выигрыш” игрока I и его называют нижним значением или нижней ценой игры. Как же рассуждает второй игрок? “Если я выберу j-ую стратегию (j-ый столбец), то самый лучший выигрыш у игрока I будет наибольшее число этого столбца. Чтобы рисковать, я должен выбрать столбец, в котором это число наименьшее. В результате I игрок не сможет получить больше, чем Число представляет собой ”верхний выигрыш” игрока I и называется верхним значение или верхней ценой игры. Можно показать, что для всякой матричной игры выполняется условие . Если , то такие игры называются играми с седловой точкой. Из неравенства следует, что . Это фактически означает, игрок I мог бы рассчитывать на выигрыш .

1.4 Матричные игры

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

Начнём непосредственно с матричных игр. Тройка (где x и y – множества, H – функция от двух переменных ) называется антагонистической игрой. Процесс разыгрывания конечной антагонистической игры (игра называется конечной, если тройка конечна) состоит в том, что игроки 1 и 2 независимо друг от друга выбирают соответственно некоторые чистые стратегии x и y, в результате чего складывается ситуация (x,y).

Мы знаем, что антагонистическую игру двух участников с нулевой суммой (напомним, что нулевая сумма – это когда выигрыш одного игрока равен проигрышу другого) удобно задавать с помощью, так называемой платёжной матрицы. Каждый элемент такой матрицы содержит числовое значение выигрыша игрока 1 (или проигрыша игрока 2) в ситуации, когда первый игрок применяет стратегию i, а второй – стратегию j. Классическим примером антагонистической игры является игра с двумя участниками, которые независимо друг от друга загадывают числа. Предполагается, что если сумма оказывается чётной, то выигрыш равный 1, достаётся первому игроку, а если нечётной, то второму. Если предположить, что загадывание нечётного числа – стратегия первого игрока, а загадывание чётного числа – стратегия второго игрока, то платёжная матрица выглядит следующим образом:

Строки матрицы соответствуют стратегиям игрока 1, столбцы – стратегиям игрока 2, а её элементы – результатам (т.е. выигрышам) первого. Если взять элементы матрицы с обратным знаком, то это будут выигрыши второго игрока. Здесь надо отметить, что вопрос о выборе стратегии является основным в теории игр. Для примера проанализируем произвольную игру . При выборе игроком 1 стратегии i, его выигрыш в независимости от игрока 2 составит . Стратегия I произвольно, поэтому главная цель игрока 1 максимизировать величину полученного выигрыша, т.е. получить . Такой принцип получил название принципа максимина. Напомним, что максимин – это выигрыш максимальный из минимальных. Надо также отметить, что принцип максимина обеспечивает игрокам гарантированный «выигрыш» при любых стратегиях противников.

Теорема о принципе максимина.

Для с (где - множества чистых стратегий игроков, (х, у) – ситуация игры - функции полезности игроков, заданные на множестве ситуаций игры аналитически ) общего вида

.

Доказательство.

Для

Для игры, заданной матрицей выигрышей можно записать следующее равенство .

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

Матричная игра игроков с нулевой суммой может рассматриваться как следующая абстрактная игра двух игроков.

Первый игрок имеет m страте6гий i = 1,2,...m, второй имеет n стратегий j=1,2,...n. Каждой паре стратегий (i, j) поставлено в соответствии число a , выражающее выигрыш игрока 1 за счет игрока 2, если первый игрок примет свою i-ю стратегию, а 2-ю j-ю стратегию.

Каждый из игроков делает один ход: игрок 1 выбирает свою i-ю стратегию (i= ), 2- свою j-ю стратегию (j= ) после чего игрок 1 получает выигрыш a за счет игрока 2 ( если a <0, то это значит, что игрок 1 платит второму сумму a ). На этом игра заканчивается.

Каждая стратегия игрока i= ; j= часто называется чистой стратегией.

Если рассмотреть матрицу

то проведение каждой партии матричной игры с матрицей А сводится к выбору игроком 1 i- строки, а игроком 2 j-го столбца и получения игроком 1 (за счет игрока 2) выигрыша a .

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

min a (i= )

j

т.е определяется минимальный выигрыш для игрока 1 при условии, что он примет свою i-ю чистую стратегию, затем из этих минимальных выигрышей отыскивается такая стратегия i=i , при которой этот минимальный выигрыш будет максимальным, т.е. находится

max min a = a = (1)

Определение: Число , определенное по формуле (1) называется чистой нижней ценой игры показывает, какой минимальный выигрыш может гарантировать себе игрок 1, применяя свои чистые стратегии при всевозможных действиях игрока 2.

Игрок 2 при оптимальном своем поведении должен стремиться по возможности за счет своих стратегий максимально уменьшить выигрыш игрока 1. Поэтому для игрока 2 отыскивается

max a

i

т.е. определяется max выигрыш игрока 1, при условии, что игрок 2 применит свою j-ю чистую стратегию, затем игрок 2 отыскивает свою j=j стратегию, при которой игрок 1 получит min выигрыш, т.е. находит

min max a =a = (2)

j i

Определение. Число , определяемое по формуле (2), называется чистой верхней ценой игры и показывает, какой максимальный выигрыш за счет своих стратегий может себе гарантировать игрок 1.

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

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

ПРИМЕР 3: Провести SP-разбиение матрицы игры (Н)

Решение: вычисляем верхнюю и нижнюю цену игры

Исходная игра имеет SP (x1,y1) в чистых стратегиях. Существование SP в чистых стратегиях матричной игры с полной информацией позволяет провести SP-разбиение (Н) исходной игры:

.

Формирование SP- разбиения матричной игры с SP по существу и является рациональным представлением исходной матрицы (Н) игры. Значит, понятие рациональности представления матрицы игры преследует цель сформулировать методы рационального преобразования платёжной матрицы с целью вычисления цены игры v или упрощения построения подыгры-решения.

Далее рассмотрим такое понятие, как решение, при помощи фиктивного разыгрывания. Есть 2 игрока, которые без теории игр, хотят сделать игру несколько раз, причём каждый из них склонен к статистике и оценивает стратегию своего противника. При каждом разыгрывании противоборствующие стороны стремятся максимизировать свой ожидаемый выигрыш против наблюдаемого вероятностного распределения противника: если игрок 2 использует j-ю стратегию раз, то игрок 1 выберет i-ю стратегию, чтобы максимизировать . Аналогично, если игрок 1 использует i-ю стратегию раз, то игрок 2 выберет j-ю стратегию, чтобы минимизировать . Условно эмпирические распределения сходятся к оптимальным стратегиям. Точнее, пусть - число использований первым игроком i-ой стратегии в течение первых N розыгрышей. Пусть , то тогда является смешанной стратегией. Здесь справедливо утверждение о том, что предел любой сходящейся подпоследовательности является оптимальной стратегией, т.е. если и полученные стратегии игроков 1 и 2, то выполняется равенство . Такой метод полезен в случае игры с большим числом стратегий.

Опишем некоторые свойства решений матричных игр. Пусть G(X,Y,A) – игра двух лиц с нулевой суммой, в которой игрок 1 выбирает стратегию , а игрок 2 - , после чего игрок 1 получает выигрыш A=A(x,y) за счёт игрока 2.

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

Свойство 2: Ни одна доминируемая чистая стратегия игрока не содержится в спектре его оптимальной стратегии.

Свойство 3: Если – конечная антагонистическая игра, а , подыгра игры G причём - чистая стратегия игрока 1 в игре G, доминируемая над некоторой стратегией , спектр которой не содержит . Тогда всякое решение игры является решением игры G.

Свойство 4: Тройка является решением игры , когда является решением игры , где а – любое вещественное число, к>0

ГЛАВА 2. Игры с нулевой суммой в чистых стратегиях

2.1 Вычисление оптимальных стратегий на примере решения задач

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

Теорема: пусть А – матричная игра и строки данной матрицы являются доминирующими. Тогда игрок 1 имеет такую оптимальную стратегию х, что ; кроме того, любая оптимальная стратегия для игры, получающаяся в результате удаления доминирующих строк, будет также оптимальной для первоначальной игры.

Пример 1. Игра доминирования

Рассмотрим игру с матрицей . Здесь второй столбец доминирует 4 и игрок 2 соответственно не будет использовать 4 стратегию. Поэтому можно рассмотреть матрицу следующего вида . В этой матрице третья строка доминирует первую. При удалении получается матрица . А в этой матрице третий столбец доминируется вторым. Следовательно, исходная матрица сводится к следующей матрице .

Пример 2. Игра на уклонение.

Предполагается, что игроки выбирают целые числа i и j между 1 и n, а игрок 1 выигрывает величину , т.е. расстояние между i и j. Пусть первый игрок придерживается стратегии , тогда для всех (( - значение игры).

• Пусть нечётно, тогда игрок 2 имеет чистую стратегию для всех

• Предположим, что чётно, тогда игрок 2 имеет такую стратегию где , , , , , для всех . Теперь используя теорему можно убедиться, что значение игры . Игрок 1 имеет оптимальную стратегию , а оптимальная стратегия игрока 2 равна , если и если

Приведём теорему, по которой решалась эта игра. Теорема: для того, чтобы ситуация была равновесной в игре , а число - значение игры , необходимо и достаточно выполнение следующего неравенства. Для всех и : ).

Ситуация называется ситуацией равновесия в чистых стратегиях, если для любых выполнено двойное неравенство (*). Если каждый из игроков стремится достичь ситуации равновесия, то принцип, которому они следуют, называют принципом равновесия. Для игры, заданной матрицей равенство (т.е. верхнее значение игры равно нижнему значению) записывается в виде , а неравенство (*) – в виде , где чистые максиминная и минимаксная стратегии соответственно игроков I и I I.

Пример 3. Игра «Дуэль».

Два дуэлянта (игроки А и В) начинают сходиться в момент времени t=0. Встреча произойдёт в момент времени t=1. У каждого есть возможность выстрелить в любой момент времени. Если одному из них удастся выстрелить раньше соперника, то он становится победителем. Если же оба выстрелят одновременно, то дуэль закончится вничью. Если игрок А произведёт выстрел в момент времени x ( ) то его выстрел будет успешным с вероятностью р(x). Подобным образом будет вероятным выстрел игрока В в момент времени y ( ) c вероятностью q(y). При условии игрок А выиграет с вероятностью р(x), а проиграет с вероятностью (1- р(x)) q(y). Тем самым его средний выигрыш при будет равен . С другой стороны, если x> y, то его средний выигрыш будет равен . При x= y средний выигрыш . Таким образом, функция H(x,y) игрока А имеет вид