МС лекции (Лекции), страница 8

4. В чем заключается принцип минимакса и максимина?

5. При каких условиях можно говорить, что игра имеет седловую точку?

6. Какие подходы существуют к определению оптимальных стратегий?

7. Что называется “ценой игры”?

8. Дать определение понятию “смешанная стратегия”.

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

Принципиально иная ситуация возникает при изучении процессов принятия решений несколькими субъектами, интересы которых могут не совпадать. При этом возникают задачи со многими целевыми функциями (критериями). Область математики, изучающая данные проблемы, получила название теории игр. Задачи теории игр относятся к области принятия решений в условиях неопределенности, а их специфика состоит в том, что, как правило, подразумевается неопределенность, возникающая в результате действий двух или более «разумных» противников, способных оптимизировать свое поведение за счет других. Среди типичных примеров такого поведения могут быть названы действия конкурирующих фирм на одном рынке или планирование военных операций.

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

Теория игр берет начало от работ Э.Бореля (1921г.), а принципиальным этапом в ее становлении как самостоятельного научного направления стала монография Дж.Неймана, вышедшая в 1944 г.

3.2. Терминология и классификация игр. Особенностью теории игр как научной дисциплины стала употребляемая в ней специфическая терминология. Термин «игра» применяется для обозначения совокупности правил и соглашений, которыми руководствуются субъекты, поведение которых мы изучаем. Каждый такой субъект k, где , или игрок, характеризуется наличием индивидуальной системы целевых установок и стратегий , т.е. возможных вариантов действий в игре.

Достаточно распространенный способ математического описания игры основан на задании функций , каждая из которых определяет результат (платеж, выигрыш), получаемый игроком в зависимости от набора стратегий , примененного всеми участниками игры. Такие функции также называют функциями выигрыша, или платежными функциями. В том случае, если для любых S игра называется игрой с нулевой суммой. Игру с двумя участниками и нулевой суммой называют антагонистической. Антагонистические игры, т.е. игры, в которых выигрыш одного участника равен проигрышу другого, в силу относительно простой постановки задачи являются наиболее изученным разделом теории игр. Однако содержание теории игр, безусловно, не исчерпывается ими. В классификации игровых моделей выделяют игры с конечными и бесконечными наборами стратегий у игроков, выделяют игры по возможным количествам ходов у участников. Также игры делят на некооперативные и кооперативные, т.е. те, в которых функции выигрыша участников зависят от образуемых ими коалиций. Помимо этого игры можно различать по объему информации, имеющейся у игроков относительно прошлых ходов. В этой связи они делятся на игры с полной и неполной информацией.

3.3. Матричные игры и понятие седловой точки. Рассмотрим более подробно антагонистические игры и их основные свойства. Удобным способом задания игры двух участников с нулевой суммой является платежная матрица. Отсюда, кстати, происходит еще одно их название – матричные игры. Каждый элемент платежной матрицы a_ij содержит числовое значение выигрыша игрока I (проигрыша игрока I), если первый применяет стратегию i, а второй - стратегию j. Термины выигрыш и проигрыш следует понимать в широком смысле, т.к. они могут принимать отрицательные значения и с житейской точки зрения означать противоположное. Нетривиальность задачи прежде всего заключается в том, что каждый из игроков делает свой выбор, не зная о выборе другого, что существенно осложняет процесс оптимизации выбираемой стратегии.

	Нечет.	Чет.
Нечет.	1	-1
Чет.	-1	1

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

(6.1)

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

Более сложная и содержательная платежная матрица может быть получена, если несколько модифицировать предложенную игру. Допустим, что оба участника имеют право загадывать числа от 1 до 4, что составляет их соответствующие стратегии. В случае, если результат сложения задуманных чисел будет четным, то второй игрок выплачивает первому получившуюся сумму, а если нечетным, то первый – второму. Запишем платежную матрицу для такой игры:

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

Как уже отмечалось, важнейшим в теории игр является вопрос об оптимальности решения (выбора стратегии) для каждого из игроков. Проанализируем с этой точки зрения некоторую матричную игру, для которой задана платежная матрица A = || a_ij ||_mxn . При выборе игроком I стратегии i его гарантированный доход независимо от действий игрока II составит min a_i,j. Поскольку он может выбирать i самостоятельно, то целесообразно этот выбор сделать таким, чтобы он при любой стратегии противника максимизировал величину гарантированного дохода, т.е. обеспечивал получение max (min a_i,j). Такой принцип выбора стратегии получил название «принцип максимина» . С другой стороны, аналогичные рассуждения могут быть проведены по поводу действий второго игрока. Его наибольший проигрыш при выборе стратегии j составит max a_i,j, и, следовательно, ему следует выбирать стратегию так, чтобы минимизировать величину проигрыша при любых действиях соперника, т.е. обеспечить min (max a_i,j). В этом суть принципа минимакса.

Можно доказать справедливость следующего соотношения:

max min aij min max aij i j j i

(6.3)

Однако очевидный интерес представляет ситуация, при которой значение выигрыша (платежа), получаемого игроком I при выборе им максиминной стратегии, равно платежу (проигрышу) II-го игрока при минимаксной стратегии

max min aij = min max aij i j j i

(6.4)

В этом случае говорят, что игра имеет седловую точку. Совпадение значений гарантированных выигрышей игроков при максиминной и минимаксной стратегии означает возможность достижения в игре некоторого оптимального (стабильного, равновесного) состояния, от которого невыгодно отклоняться ни одному из участников. Понятие «оптимальность» здесь означает, что ни один разумный (осторожный) игрок не стремится изменить свою стратегию, так как его противник, в принципе, сможет выбрать такую стратегию, которая даст худший для первого результат. Стратегии i* и j*, образующие седловую точку, называются оптимальными, а значение называют ценой игры. Тройка (i*, j*, v) считается решением матричной игры с седловой точкой.

Нетрудно заметить, что не всякая игра обладает седловой точкой. В частности, как игра (1), так и игра (2) седловой точки не имеют. Примером игры, имеющей седловую точку, является игра с платежной матрицей (5).

(6.5)

В данной матрице минимальные (гарантированные) выигрыши первого игрока по строкам равны 1, 5 и (-3). Следовательно, его максиминному выбору будет отвечать стратегия 2, гарантирующая выигрыш 5. Для второго игрока максимальные проигрыши по столбцам матрицы составляют 8 . 10, 5, 17, поэтому имеет смысл остановиться на стратегии 3, при которой он проиграет только 5. Таким образом, вторая стратегия первого игрока и третья стратегия второго образуют седловую точку со значением 5, т.е. для игры с матрицей (5) имеет решение (2; 3; 5).

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

Смешанной стратегией игрока I в игре с матрицей A = || a_ij ||_mxn называется упорядоченный набор действительных чисел , удовлетворяющих условиям

(6.6)

Числа интерпретируются как вероятности применения игроком I стратегий 1,e2,…,mm, которые, в отличие от смешанных, также называются чистыми стратегиями.

Аналогично вводится понятие смешанных стратегий игрока II, которые определяются как набор чисел удовлетворяющих условиям

(6.7)

Тогда, если игрок I применяет смешанную стратегию x = (x₁, x₂ … x_m), а игрок II смешанную стратегию y = (y₁, y₂ … y_n), то математическое ожидание выигрыша игрока I (проигрыша игрока II) определяется соотношением

(x,y) =

(6.8)

В дальнейшем через Х будем обозначать множество допустимых смешанных стратегий игрока I, определяемое условием (7), а через Y - определяемое условием (8) множество допустимых смешанных стратегий игрока II.