Выбор в условиях неопределенности

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

ЗАДАНИЕ НЕОПРЕДЕЛЕННОСТИ С ПОМОЩЬЮ МАТРИЦЫ

В реальной практике нередко приходится иметь дело с более сложной ситуацией, когда выбор альтернативы неоднозначно определяет последствия сделанного выбора: имеется набор возможных исходов y Î Y, из которых один окажется совмещенным с выбранной альтернативой, но какой именно – в момент выбора неизвестно, а станет ясным позже, когда выбор уже сделан и изменить ничего нельзя. Хотя с каждой альтернативой x связано одно и то же множество исходов Y, для разных альтернатив одинаковые исходы имеют разное значение. В случае дискретного набора альтернатив и исходов такую ситуацию можно изобразить с помощью следующей матрицы:

X \ Y y ₁ y ₂... y_j... y_m

x ₁ q ₁₁ q ₁₂... q_1j... q _{1 m}

?..................

x_i q_{i 1} q_{i 2}... q_ij... q_im

?..................

x_n q_{n 1} q_{n 2}... q_nj... q_nm

В этой матрице все возможные исходы образуют вектор y = (y ₁,... y_m), числа q_ij выражают оценку ситуации, когда сделан выбор альтернативы x_i и реализовался исход y_j. В разных случаях числа q_ij могут иметь различный смысл: иногда это “выигрыши”, иногда “потери”, “платежи”; в литературе употребляются также и другие названия.

Если все строки q_i = (q_{i 1},..., q_im) при любых i одинаковы, то проблемы выбора между альтернативами нет. Если же строки матрицы различны, то возникает вопрос, какую альтернативу предпочесть, не зная заранее, какой из исходов реализуется.

Аналогично, в случае непрерывных множеств X и Y ситуация описывается с помощью задаваемой на этих множествах функции q (x, y), x Î X, y Î Y с соответствующей постановкой вопроса о выборе x.

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

Один класс задач называется “играми против природы”. В таких задачах считается, что исходы y ₁,..., y_m есть возможные “состояния природы”. Желательность каждой альтернативы x_i зависит от того, каково состояние природы, но узнать, каково оно, мы сможем лишь после того, как сделаем выбор.

В другом классе задач предполагается, что исходы Y – это множество альтернатив, на котором выбор осуществляет второй игрок. В отличие от бесстрастной Природы второй игрок преследует свои интересы, отличные от интересов первого игрока. При этом матрица Q = || q_ij ||, характеризующая оценки ситуаций с точки зрения игрока, выбирающего x, уже недостаточна для описания всей игры. Необходимо задать вторую матрицу U = || u_ij ||, описывающую игру с позиций второго игрока. Задание X, Y, Q и U называется нормальной формой игры. Расхождения между матрицами Q и U определяют степень антагонизма игроков. Если a_ij + u_ij = const для всех i и j, то соперничество называется строгим. В случае q_ij + u_ij = 0 имеем игру с нулевой суммой. Можно представить себе игры, где выигрыши и проигрыши сторон не связаны линейно и это будет отражать усиление или ослабление конфронтации сторон. Можно также рассматривать изменение матриц платежей после очередного хода. Например, интерес исследователей привлекли игры с нарастающей конфликтностью; примером может служить игра “в цыпленка”*, но, конечно, у такой задачи есть и более серьезные приложения. Возможны и другие обобщения, например рассмотрение игр с участием большего числа участников, с образованием коалиций между ними и т.д.

Разнообразие задач выбора в условиях неопределенности существенно возрастает в связи с тем, что и сам характер неопределенности может быть различным. Например, в “игре против природы” можно считать, что состояние природы “совершенно неизвестно”, а можно ввести на множестве Y вероятностную меру, что даст основания для усиления различий между исходами; такие разные постановки задач дают, естественно, и различные их решения.

КРИТЕРИИ СРАВНИВАНИЯ АЛЬТЕРНАТИВ ПРИ НЕОПРЕДЕЛЕННОСТИ ИСХОДОВ

Вряд ли возможно (да и целесообразно) в кратком обзоре рассмотреть все важнейшие результаты теории игр (опубликовано много монографий; интересующимся можно рекомендовать начать изучение с книг [7; 21; 29]). Однако об основных идеях и подходах к решению задач теории игр желательно иметь представление всем, кому придется проводить исследования систем.

Центральным моментом является введение критерия для оценки выбираемого варианта. В силу неопределенности исхода нужно дать оценку сразу целой строке платежной матрицы; имея такие оценки для всех строк и сравнивая их, мы и можем делать выбор.

Самым распространенным является критерий выбора “наименьшего из зол”, называемый максиминным критерием. В каждой из строк матрицы платежей находится наименьший выигрыш , который характеризует гарантированный выигрыш в самом худшем случае и считается оценкой альтернативы x_i. Теперь остается найти альтернативу x *, обеспечивающую наибольшее значение этой оценки: Эта альтернатива и называется оптимальной по максиминному критерию. Поскольку часто платежную матрицу определяют не через выигрыш, а через проигрыш, тот же принцип приводит к минимаксному критерию.

Минимаксный критерий является крайне осторожным, очень пессимистическим, поэтому были предложены другие критерии. Таков, например, критерий минимаксного сожаления, предложенный Сэвиджем. При этом по платежной матрице Q вычисляется “матрица сожалений” S, элементы которой определяются как и минимаксный критерий применяется к матрице S: .

Дальнейшее ослабление пессимистичности оценки альтернатив дает критерий пессимизма – оптимизма (критерий Гурвица), который сводится к взвешенной комбинации наилучшего и наихудшего исходов. А именно: за оценку альтернативы x_i в критерии Гурвица принимается величина

Показатель? называется показателем пессимизма – оптимизма (при??= 1 имеем снова максиминный критерий); оптимальная альтернатива есть .

ОБЩЕЕ ПРЕДСТАВЛЕНИЕ О ТЕОРИИ ИГР

Некоторые особенности игровых ситуаций хорошо видны на простейшем примере. Пусть имеется игра с континуальными множествами X и Y, строгим соперничеством сторон и нулевой суммой. Это делает достаточным рассмотрение лишь одной функции платежей q (x, y), которую один игрок старается максимизировать по x, а другой – минимизировать по y.

В тех случаях, когда , точка (x *, y *), в которой достигается это равенство, одновременно удовлетворяет амбиции обоих игроков. Эта точка равновесия интересов сторон называется седловой. Отход от этой точки невыгоден обеим сторонам, так что ее выбор решает игру.

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