Максиминная и минимаксная стратегии

Основные понятия и классификация

Теория матричных игр

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

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

Конфликтная ситуация будет антагонистической, если увеличение выигрыша для одной из сторон происходит только за счет другой стороны, что характерно для «салонных» игр (шахматы, карточные игры и т. п.). Как первые формализованные модели конфликтов, требующие определенной изобретательности для выигрыша, они не только удобны как иллюстративные примеры, но и послужили основой для используемой терминологии. Так, лица, принимающие решения, называются игроками, а целевая функция – платежной функцией. Математическая модель конфликта – игра, которая представляет собой совокупность правил, определяющих как «права» каждого игрока, так и исход игры. Ход – это момент игры, когда игроки выбирают один из возможных вариантов. Если ход выбирается сознательно, это личный ход, а если случайным выбором – случайный.

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

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

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

Теория игр в настоящее время бурно развивается. Ее возникновение относится к 1944 г., когда вышла монография Дж. фон Неймана и О. Моргенштерна «Теория игр и экономическое поведение», содержащая в основном экономические примеры.

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

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

По количеству стратегий различают конечные и бесконечные игры. В конечных играх число возможных стратегий у игроков ограничено. Примером игры с бесконечным числом стратегий может ситуация «продавец –покупатель», когда как цена, так и количество товара могут быть названы любыми. Разумеется, при реальном торге фактически используется ограниченное число округленных значений цены.

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

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

Таблица 6.1

			…
			…
			…
…	…	…	…
			…

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

Таблица 6.2

				-3
					-6

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

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

Таблица 6.3

				-3			-3
							1
					-6		-6
	7	9		6	6	7

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

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

Таблица 6.4

						1
			-3		-1	-3
	7	4		5	6

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

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

Таблица 6.5

			-3		-1	-3

Дата добавления: 2014-12-07