Упрощение платёжной матрицы

Упрощение платёжной матрицы

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

Дублирующими называются стратегии, которым соответствуют одинаковые значения элементов в матрице, т.е. матрица содержит одинаковые строки (столбцы). Если все элементы  i-й строки матрицы меньше соответствующих элементов  k-й строки, то  i-я стратегия для игрока  А  называется доминирующей. Если же элемент  r-го столбца матрицы больше соответствующих элементов  j-го столбца, то для игрока  В  стратегия  В_r – доминирующая. Например, в матрице платежей  C=  для игрока  В  заведомо невыгодна четвёртая стратегия, так как все значения элементов 4-го столбца  c_i4  превышают соответствующие значения первого и второго столбца. Четвёртый столбец матрицы можно исключить (игрок  В  никогда не воспользуется этой стратегией).

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

Рассмотрим матрицу  С, разбитую на четыре подматрицы, для которых выполняется условие равенства сумм элементов по строкам и столбцам:

C=.

Объединяя стратегии  А₁, А₂, и А₃, А₄ и А₅, В₁ и В₂, В₃ и В₄, приводим матрицу к виду:

Полученная матрица содержит седловую точку. Поэтому решение первоначальной игры, заданной матрицей  С, таково: Р*=(1/3; 1/3; 1/3; 0; 0), Q*=(1/2; 1/2; 0; 0). Цена игры равна единице. В результате упрощения игры решение её стало очевидным: оптимальной для игрока  А  является комбинация стратегий  А₁, А₂ и А₃, а для игрока  В  комбинация стратегий  В₁  и  В₂. Вероятности применения стратегий А₁, А₂ и А₃ равны между собой, сумма их равна 1, поэтому  Р*=(1/3; 1/3; 1/3; 0; 0). Аналогично, оптимальная стратегия игрока  В   имеет вид  Q*=(1/2; 1/2; 0; 0).

Рекомендуемые материалы

Таким образом, при решении игры  mxn  следует:

а) проверить, содержит ли матрица седловую точку;

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

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

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

Эти условия зависят не от сознательных действий другого игрока, а от объективной действительности, которую принято называть природой. Такие игры называются играми с природой. Решения в этих играх получают с помощью теории стратегических решений. Человек  А  в играх с природой старается действовать осмотрительно, используя например, минимаксную стратегию, позволяющую получить наименьший проигрыш. Второй игрок  В  (природа) действует совершенно случайно, возможные стратегии определяются как её состояния (например, условия погоды в данном районе, спрос на определённую продукцию, объём перевозок, некоторое сочетание производственных факторов и т.д.). В некоторых задачах для состояний природы может быть задано распределение вероятностей, в других – и оно неизвестно.

Условия игры, как и в рассмотренных выше задачах теории игр, задаются в виде матрицы:

C=.

Элемент  с_ij  равен выигрышу игрока  А, если он использует стратегию  А_i, а состояние природы – В_j.

В ряде случаев при решении игр рассматривают матрицу рисков R. Элемент матрицы  r_ij  представляет собой разность между выигрышем, который получил бы игрок  А, если бы он знал состояние природы  B_j, и выигрышем, который он получит в тех же условиях, применяя стратегию  A_i, т.е.  r_ij=b_j - с_ij, где  _.

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

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

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

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

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

Как критерий Вальда, так и критерий Сэвиджа основаны на самой пессимистической оценке обстановки. В отличие от них критерий Гурвица учитывает как пессимистический, так и оптимистический подход к ситуации. Такого рода компромиссное правило, определяющее выбор решения в условиях полной неопределённости, когда распределение вероятностей состояний природы неизвестно, заключается в том, что неразумно, приняв во внимание самый маленький выигрыш, не учитывать самый большой, для чего субъективным образом вводится некоторый коэффициент оптимизма (он выполняет роль вероятности). Этот принцип часто называется обобщённым максимином. Принимается решение о выборе стратегии, при которой имеет место

, где  0 £ l £1.

Значение  l  выбирают на основании субъективных соображений. Чем больше желание подстраховаться в данной ситуации, тем ближе к нулю значение  l. Применим принцип Гурвица к решению примера:

Таблица 9.4

По принципу обобщённого максимина необходимо стороне  А  использовать стратегию  А₃.

Кроме перечисленных принципов (минимакса, обобщённого максимина и минимальных потерь), используют принцип Байеса-Лапласа, который отступает от условий полной неопределённости. При этом предполагается, что возможным состояниям природы  В₁, В₂, …, B_n можно приписать определённую вероятность, соответственно равную  q₁, q₂,…, q_n. Этот принцип используется, если есть возможность определить вероятность возникновения отдельных состояний природы (например, статистическая обработка метеосводок), если нет – применяют принцип равновероятности (принцип недостаточного основания Лапласа). Он заключается в том, что всем возможным состояниям природы приписывается одинаковая вероятность, и решение игры ищется при таких условиях. Однако во всех случаях нельзя утверждать, что принятое решение оптимальное, оптимальным оно является только относительно принятого распределения вероятностей состояний природы.

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

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

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