Методы решения матричных игр.

Если в платежной матрице игры присутствует такой элемент Методы решения матричных игр. - student2.ru , что Методы решения матричных игр. - student2.ru , то говорят, что у игры есть седловая точка. В таком случае сам элемент Методы решения матричных игр. - student2.ru называют ценой игры. Для обозначения цены игры введем особый символ Методы решения матричных игр. - student2.ru (ню). Цена игры и пара альтернатив игроков, которая обеспечила данный исход игры, составляют решение игры.

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

Как правило, в играх Методы решения матричных игр. - student2.ru , поэтому решение большинства игр находят в так называемых смешанных стратегиях. Смешанной стратегией игрока называют вектор, в котором каждая компонента соответствует вероятности (или частоте) выбора игроком соответствующей альтернативы. Ни одна компонента такого вектора не равна единице.

Обозначим смешанную стратегию игрока А Методы решения матричных игр. - student2.ru , а смешанную стратегию игрока В Методы решения матричных игр. - student2.ru . При использовании смешанных стратегий игра приобретает случайный характер, случайной величиной становится также и ее общий результат, который можно определить по формуле Методы решения матричных игр. - student2.ru . Функцию Методы решения матричных игр. - student2.ru называют платежной.

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

Методы решения матричных игр. - student2.ru .

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

Методы решения матричных игр. - student2.ru .

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

Воспользуемся левой частью этого неравенства, которую можно описать системой неравенств:

Методы решения матричных игр. - student2.ru Методы решения матричных игр. - student2.ru

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

Методы решения матричных игр. - student2.ru

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

Разделим каждое неравенство системы и сумму компонентов вектора вероятностей на положительное число Методы решения матричных игр. - student2.ru . Поскольку элементы платежной матрицы можно сделать положительными числами, то можно сделать положительным и Методы решения матричных игр. - student2.ru . Введем обозначение Методы решения матричных игр. - student2.ru . Так как игрок B стремится минимизировать исход Методы решения матричных игр. - student2.ru , то он максимизирует Методы решения матричных игр. - student2.ru

Методы решения матричных игр. - student2.ru Методы решения матричных игр. - student2.ru

Решение данной задачи позволит получить Методы решения матричных игр. - student2.ru , на основе которых вычисляются компоненты оптимального вектора Методы решения матричных игр. - student2.ru и цена игры. На основе двойственных оценок получаем оптимальный вектор Методы решения матричных игр. - student2.ru .

Статистические игры.

Статистические игры образуют специальный класс матричных игр, в которых одним из участников является субъект, принимающий решение (игрок А – статистик), а другим – «природа» (игрок П). Под термином «природа» подразумевается весь комплекс внешних условий, в которых статистику приходится принимать решение. Статистик может осуществлять выбор решения из m возможных стратегий Методы решения матричных игр. - student2.ru . Природа может находиться в одном из n возможных состояниий Методы решения матричных игр. - student2.ru .

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

Методы решения матричных игр. - student2.ru

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

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

Начнем с рассмотрения ситуации с максимальной неопределенностью, когда о математических или статистических вероятностях наступления того или иного состояния природы ничего не известно. Для таких случаев предусмотрено применение критериев Вальда, Сэвиджа и Гурвица. Можно выделить два фактора, определяющих предпочтительный выбор того или иного критерия: 1) специфика условий, в которых приходится принимать решение; 2) субъективные склонности игрока А.

Критерий Вальда будет выбран наиболее осторожным игроком или же игроком, вынужденным принимать решение в крайне неблагоприятных условиях (ограниченность ресурсов, отсутствие резервов и невозможность позволить себе нести потери и т.д.). Ориентиром в выборе оптимального решения в таком случае будет максимин, уже известное нам число Методы решения матричных игр. - student2.ru , определяемое по платежной матрице как наибольшее среди наименьших по строкам матрицы чисел Методы решения матричных игр. - student2.ru .

Методы решения матричных игр. - student2.ru

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

Методы решения матричных игр. - student2.ru

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

Методы решения матричных игр. - student2.ru

В ситуации максимальной неопределенности лицо, принимающее решение, может полагаться не только на логически структурированный выбор, но и на оценки частоты наступления наихудших и наилучших исходов, то есть на субъективное экспертное суждение. В таком случае выбор оптимальной альтернативы опирается на критерий Гурвица. Базовой основой данного критерия является параметр Методы решения матричных игр. - student2.ru , именуемый характеристикой «оптимизма-пессимизма», поскольку Методы решения матричных игр. - student2.ru соответствует частоте наступления наихудших исходов. Чем ближе Методы решения матричных игр. - student2.ru к единице, тем более пессимистичен эксперт.

Технология выбора по критерию Гурвица такова. По строкам платежной матрицы выбираются наихудшие Методы решения матричных игр. - student2.ru и наилучшие Методы решения матричных игр. - student2.ru исходы. Затем для каждой альтернативы вычисляются величины Методы решения матричных игр. - student2.ru . Оптимальной по критерию Гурвица является альтернатива с максимальным Методы решения матричных игр. - student2.ru .

Методы решения матричных игр. - student2.ru

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

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

Методы решения матричных игр. - student2.ru , то математическое ожидание выигрыша рассчитывается по формуле Методы решения матричных игр. - student2.ru . Максимальное математическое ожидание указывает на оптимальную альтернативу.

Методы решения матричных игр. - student2.ru

В ситуациях с известными вероятностями состояний природы используется критерий Байеса, который также базируется на расчете ожидаемого выигрыша. Для определения величины последнего вектор вероятностей состояний природы Методы решения матричных игр. - student2.ru необходимо умножить на вектор исходов в платежной матрице

Методы решения матричных игр. - student2.ru

Оптимальна по критерию Байеса та альтернатива, у которой значение ожидаемого выигрыша Методы решения матричных игр. - student2.ru максимально.

Рассмотрим применение разнообразных критериев выбора на примере.

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

Оценки затрат для каждого варианта решения приведены в таблице 26.

Таблица 26. Затраты, связанные с реализацией решений ( в ден. ед.).

Состояния   Альтернативы 1 2 3
1
2

Предположим, вероятности состояний оборудования неизвестны. Следовательно, мы можем опираться на критерии Вальда, Сэвиджа, Гурвица или, с известной долей условности, на критерий Лапласа.

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

Таблица 27. Платежная матрица задачи.

  Методы решения матричных игр. - student2.ru Методы решения матричных игр. - student2.ru Методы решения матричных игр. - student2.ru
Методы решения матричных игр. - student2.ru -2 -6 -10
Методы решения матричных игр. - student2.ru -10 -4 -8
Методы решения матричных игр. - student2.ru -14 -12 -6

Рассмотрим выбор на основе критерия Вальда ( табл. 28).

Таблица 28. Иллюстрация выбора на основе критерия Вальда.

  Методы решения матричных игр. - student2.ru Методы решения матричных игр. - student2.ru Методы решения матричных игр. - student2.ru Методы решения матричных игр. - student2.ru
Методы решения матричных игр. - student2.ru -2 -6 -10 -10
Методы решения матричных игр. - student2.ru -10 -4 -8 -10
Методы решения матричных игр. - student2.ru -14 -12 -6 -14

По критерию Вальда можно с одинаковым основанием выбрать либо первую, либо вторую альтернативу.

Теперь выберем оптимальную альтернативу по критерию Сэвиджа ( табл. 29 и 30). Сначала выберем наилучшие исходы по каждому из состояний.

Таблица 29. Выбор Методы решения матричных игр. - student2.ru .

  Методы решения матричных игр. - student2.ru Методы решения матричных игр. - student2.ru Методы решения матричных игр. - student2.ru
Методы решения матричных игр. - student2.ru -2 -6 -10
Методы решения матричных игр. - student2.ru -10 -4 -8
Методы решения матричных игр. - student2.ru -14 -12 -6
Методы решения матричных игр. - student2.ru -2 -4 -6

Далее рассчитаем риски Методы решения матричных игр. - student2.ru и сделаем выбор.

Таблица 30. Иллюстрация выбора по критерию Сэвиджа.

Методы решения матричных игр. - student2.ru   Методы решения матричных игр. - student2.ru 1 2 3 Методы решения матричных игр. - student2.ru
1
2

Критерий Сэвиджа предписывает остановить выбор на первой альтернативе.

Покажем применение критерия Лапласа (табл. 31). В данной задаче использование критерия Лапласа основано на допущении о равновероятности состояний оборудования. Вероятность каждого состояния в данном случае составляет Методы решения матричных игр. - student2.ru

Таблица 31. Иллюстрация выбора по критерию Лапласа.

  Методы решения матричных игр. - student2.ru Методы решения матричных игр. - student2.ru Методы решения матричных игр. - student2.ru Методы решения матричных игр. - student2.ru
Методы решения матричных игр. - student2.ru -2 -6 -10 -6
Методы решения матричных игр. - student2.ru -10 -4 -8 -7,33
Методы решения матричных игр. - student2.ru -14 -12 -6 -10,67

Критерий Лапласа указывает на первую альтернативу.

Методы решения матричных игр. - student2.ru И в завершение анализа ситуации с неизвестными вероятностями состояний покажем использование критерия Гурвица (табл. 32), предположив, что авторитетный эксперт оценил частоту наступления наихудших исходов на уровне 60%, то есть Методы решения матричных игр. - student2.ru . Основой выбора является вычисление величин

Таблица 32. Иллюстрация выбора по Гурвицу.

  Методы решения матричных игр. - student2.ru Методы решения матричных игр. - student2.ru Методы решения матричных игр. - student2.ru Методы решения матричных игр. - student2.ru Методы решения матричных игр. - student2.ru Методы решения матричных игр. - student2.ru
Методы решения матричных игр. - student2.ru -2 -6 -10 -10 -2 -6,8
Методы решения матричных игр. - student2.ru -10 -4 -8 -10 -4 -7,6
Методы решения матричных игр. - student2.ru -14 -12 -6 -14 -6 -10,8

По критерию Гурвица оптимальна первая альтернатива.

Методы решения матричных игр. - student2.ru Перейдем к анализу ситуации «б». Предположим, стали доступны данные об опыте эксплуатации аналогичного оборудования, из которых следует, что в 30% наблюдаемых случаев наступало первое состояние, в 60% - второе и лишь в 10% - третье. Следовательно, вектор вероятностей

Методы решения матричных игр. - student2.ru Для вычисления ожидаемых выигрышей воспользуемся формулой

Выбор по критерию Байеса показан в таблице 33.

Таблица 33. Иллюстрация выбора по критерию Байеса.

  Методы решения матричных игр. - student2.ru Методы решения матричных игр. - student2.ru Методы решения матричных игр. - student2.ru Методы решения матричных игр. - student2.ru
Методы решения матричных игр. - student2.ru -2 -6 -10 -5,2
Методы решения матричных игр. - student2.ru -10 -4 -8 -6,2
Методы решения матричных игр. - student2.ru -14 -12 -6 -12

На основе критерия Байеса рекомендуется выбрать первую альтернативу.

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

Наши рекомендации