Выигрыш-критерий Байеса является основным критерием оптимальности стратегий, который используется при принятии решений в условиях риска (см. §2.1).
Рассмотрим игру с природой, задаваемой платежной матрицей А (см. (2.1.2)). Пусть q = - вектор вероятностей состояний природы, удовлетворяющих условиям (2.1.1), которые удобно расположить в добавленной строке матрицы (2.1.2):
Референд Томас Байес
(1702 - 17.04.1761)
Выигрыш-критерием Байеса оптимальности чистых стратегий с вектором ч вероятностей состояний природы (В 1 ’ (q) -критерием 2 ) называется критерий, по которому:
- показателем (В’’ (q) -показателем) эффективности чистой стратегии
A-(i = 1,2.....т) называется величина
- ценой (В 1 ’(q)-ценой) игры в чистых стратегиях (множества S c ), называется наибольший из показателей эффективности Bj’{q), /" = 1,2..., т, чистых стратегий:
- оптимальной (В 1 ’ (q) -оптимальной) во множестве S c чистых стратегий называется стратегия A k е S 1 с максимальным показателем эффективности
Оптимальную стратегию также называют байесовской стратегией. Так как показатель эффективности Bj’(q) стратегии А к есть взвешенная средняя выигрышей при этой стратегии, то оптимальная стратегия является по этому критерию оптимальной не в каждом отдельном случае, а во взвешенно среднем.
Равенство (2.5.2) можно записать в векторной форме:
где « г » - значок транспонирования.
Как видно из (2.5.3) и (2.5.4) во множестве чистых стратегий показатель эффективности оптимальной стратегии совпадает с ценой игры.
Интерпретируя чистую стратегию А- как дискретную случайную величину со значениями a n ,a i2 ,...,a irl , которые она принимает с вероятностями соответственно q u q 2 ,...,q n , получаем, что B"‘(q) - показатель эффективности стратегии А- сеть ее математическое ожидание. Именно поэтому выигрыш-критерий Байеса называют также «критерием математического ожидания».
Из (2.5.2) и (2.5.3) следуют оценки: где а™" = min а, я"“ = шах а п, а а " ттт = max min а, и max max л, -соот-
ISjSn 1 1 Klfimisy&i ’ 1 j 1
встственно максимин и максияшкс игры в чистых стратегиях. Подчеркнем, что левые и правые части неравенств (2.5.5) и (2.5.6) нс зависят от вектора q.
Чистая стратегия, наименьший выигрыш при которой совпадает с максими- ном, называется максиминной стратегией. Если игрок А придерживается макси- минной стратегии А к, то при любом состоянии природы Я имеет место неравенство а к1 >а"” т =а" юхтт, у = 1,2,..., и, означающее, что максимин экономически
представляет собой гарантированный наименьший выигрыш игрока А при любых вероятностях состояний природы, если только игрок А придерживается максиминной стратегии.
Множество чистых стратегий, оптимальных во множестве S c чистых стратегий по B p (q) -критерию, обозначим через (? с) 0(а "’»_ общее решение игры с природой в чистых стратегиях можно интерпретировать как двухэлементное множество {(S c) 0 , ?"(()}.
Под частным решением игры с природой в чистых стратегиях можно понимать двухэлементное множество, одним из элементов которого является непустая неполная совокупность чистых стратегий, оптимальных во множестве чистых стратегий, а другим - цена игры в чистых стратегиях.
Перейдем в область смешанных стратегий 5.
По В 1 ’(q) -критерию оптимальности смешанных стратегий:
- показателем (В 1 ’ (q) -показателем) эффективности смешанной стратегии Р = (р 1 ,р 2 ,...,р т) назовем взвешенно среднее значение выигрышей (2.2.3) с весами q l ,q 2 ,...,q ll:
- ценой (B p (q) -ценой) игры в смешанных стратегиях назовем наибольший из показателей эффективности (2.5.7):
- оптимальной (В’’(q) -оптимальной) во множестве S смешанных стратегий назовем стратегию Р° =(р", с наибольшим показателем эффективности:
Легко видеть, что если, в частности, смешанная стратегия Р является чистой, например, А к, к е {1,2,...,от}, то её показатель эффективности B p (P;q) как смешанной стратегии, выражаемый формулой (2.5.7), превращается в ее показатель эффективности B p (A t ;q) = Bj’(q) как чистой стратегии, вычисляемый по формуле (2.5.2).
Нетрудно убедиться в том, что показатель эффективности B p (Pq) можно представить в матричной форме:
где А - матрица игры.
В связи с бесконечностью множества 5 смешанных стратегий встает вопрос о существовании оптимальной стратегии в этом множестве. Положительный ответ дает следующая теорема.
Теорема 2.5.1. В любой игре с природой с любым вектором вероятностей ее состояний существует стратегия, оптимальная во множестве смешанных стратегий по выигрыш-критерию Байеса.
Доказательство. Из (2.2.3) и (2.5.7) заключаем, что показатель эффективности В 1 ’ (P,q) как функция смешанной стратегии Р линейна и, следовательно, непрерывна на множестве 5, которое, будучи симплексом, ограничено и замкнуто в от-мерном евклидовом пространстве R"". Следовательно, по теореме Вейерштрасса (, с. 298) функция B p (P;q) достигает на симплексе 5 своей верхней грани, т.е. найдется стратегия Р° = (/>,",р") е 5, удовлетворяющая равенству (2.5.9) ?
Множество S""(су)-оптимальных стратегий во множестве S смешанных стратегий обозначим через s 0(B (ч)) .
В следующей теореме устанавливается связь между показателями эффективности чистых и смешанных стратегий.
Теорема 2.5.2. Показатель эффективности B"Pq) смешанной стратегии Р = (Pi’PiP m) 1,0 В р (q)-критерию представляет собой взвешенное среднее показателей эффективности Bj’(q) чистых стратегий Д, / = 1,2,...,от, по тому же критерию с весами р (, / = 1,2,...,от:
Доказательство. Применяя последовательно равенства (2.5.7), (2.2.3) и (2.5.2), получим:
Пусть Р = (/; | ,р 2 ,...,р т) - произвольная смешанная стратегия. Умножая все части двойного неравенства (2.5.5) на р , и суммируя полученные неравенства по номеру /" от 1 до от, получим на основании (2.5.11) диапазон изменения показателя эффективности B p (Pq) при любых векторах вероятностей состояний природы:
Следующая теорема устанавливает связь между ценами игры в чистых и смешанных стратегиях.
Теорема 2.5.3. По выигрыш-критерию Байеса цены игры в чистых и в смешанных стратегиях равны.
Доказательство. Пусть P = (p l ,p 2 ,...,p m) е S. Используя (2.5.11), (2.5.3) и нормировочное условие вероятностей /?, i = 1,2,...,от, получим:
Так как это неравенство справедливо для любой смешанной стратегии Р, то оно справедливо, в том числе и для стратегии Р°, оптимальной во множестве смешанных стратегий 5: В р Р°q Но левая часть последнего неравенства,
по определению (2.5.9) оптимальной смешанной стратегии, равна цене игры в смешанных стратегиях. Таким образом,
С другой стороны, поскольку с5, то max Bf (q) max В 1 ’ (P:q) или, что то же
Неравенства (2.5.13) и (2.5.14) доказывают требуемое равенство B p c (q) = B p (q) ,
В силу этой теоремы можно нс говорить поотдельности о ценах в чистых и в смешанных стратегиях, а их общее значение назвать просто ценой игры по выигрыш-критерию Байеса и обозначить через B p показано, что идеальный эксперимент является выгодным тогда и только тогда, когда его стоимость меньше минимального ожидаемого риска:
где rij - риски, C - стоимость эксперимента.
Для изложения байесовского подхода к переоценке вероятностей напомним некоторые понятия из теории вероятностей.
Условная вероятность события A при условии, что произошло событие B, обозначается P(A/B) и вычисляется по формуле
Рассмотрим следующую теоретико-вероятностную схему. Пусть B1, B2, …, Bm - полная группа событий и для каждого события Bj, j= известна её вероятность P(Bj). Пусть произведён опыт, в результате которого произошло событие A. Если известны условные вероятности P(A/Bj) для всех j=, тогда условная вероятность (послеопытная) вероятность события Bj (j=,) может быть найдена по формуле Байеса
Рассмотрим теперь в схематической форме задачу принятия решения в условиях риска, заданную с помощью матрицы выигрышей, которая имеет вид табл.
Таблица 1. Платёжная матрица с вероятностным вектором состояния среды
|
Состояния среды |
||||
Здесь B1, B2, …, Bm - состояния среды, aij - выигрыш игрока в ситуации, когда он выбирает стратегию Xi, а среда принимает состояние Bj. ЛПР известна вероятность P(Bj)= qj наступления состояния Bj, причём P(Bj)?0 и. Предполагается, что среда может находиться в одном и только в одном из состояний B1, B2, …, Bm. Другими словами, случайные события B1, B2, …, Bm образуют полную группу событий, поэтому их можно взять в качестве гипотез. Известные ЛПР вероятности состояний среды P(Bj) (j=) являются безусловными (доопытными, априорными) вероятностями.
Предположим, что проводится некоторый эксперимент, результат которого как-то зависит от имеющегося состояния среды. Если в результате эксперимента наблюдается событие A и, кроме того, известны условные вероятности P(A/Bj) для всех j=, то используя формулу Байеса, можно найти послеопытные (апостериорные) вероятности каждого состояния среды. Знание уточненных вероятностей состояний среды позволяет более точно указать стратегию ЛПР.
Описанный подход к принятию решений в условиях риска называется байесовским, так как он основан на формуле Байеса. Этот подход иллюстрируется примером, рассмотренным ниже.
Задача. Бурение нефтяной скважины.
Руководитель поисковой группы должен принять решение: бурить нефтяную скважину или нет. Скважина может оказаться "сухой" (С), т.е. без нефти, "маломощной" (М), т.е. с малым содержанием нефти, и "богатой" (Б), т.е. с большим содержанием нефти. Альтернативами руководителя группы являются: x1 - бурить и x2 - не бурить. Чистая прибыль при выборе одной из альтернатив в зависимости от возможного типа скважины приведена в таблице прибылей (см. табл. 1)
Таблица 1. Платёжная матрица
|
Тип скважины |
|||
Кроме того, руководителю поисковой группы известно, что в данной местности вероятности сухой, маломощной или богатой скважины таковы: P(C)=0.5, P(M)=0.3, P(Б)=0.2.
Руководитель поисковой группы может провести эксперимент с целью уточнения структуры грунта (состояния среды). Этот эксперимент представляет собой сейсморазведку, результатом которой будет ответ - какова структура грунта в данной местности (но не ответ на вопрос о типе скважины!). В принципе структура грунта может быть либо открытой (О), либо замкнутой (З). Руководитель группы имеет таблицу результатов экспериментов, приведённой в этой местности (см. табл. 2).
Таблица 2. Таблица экспериментальных данных
Эта таблица показывает, сколько раз на грунтах открытой и грунтах замкнутой структуры встречались скважины типа С, М, Б (т.е. даёт совместную статистику грунта и типа скважин для данной местности).
Проведём анализ экспериментальных данных полученной таблицы. Предположим, что произведено n экспериментов, результаты которых являются значениями дискретных случайных величин X (тип скважины) и Y (структура грунта), которые принимают соответственно значения С, М, Б и О, З. Обозначим через n11 число экспериментов, в которых X=С и Y=О, через n12 число экспериментов, в которых X=С и Y=З, через n21 число экспериментов, в которых X=М и Y=О и т.д. В нашем случае n=100, n11=45, n12=5, n21=11. Разделив значения таблицы 2 на 100 (на число проведённых экспериментов), мы получим закон распределения двумерной случайной величины (X, Y) заданной в табличной форме (см. табл. 3).
Таблица 3. Статистический ряд распределения двумерной с.в. (X, Y)
Из таблицы 3 следует, что Р(X=C)=P(C)=0.5, Р(X=M)=P(M)=0.3, Р(X=Б)=P(Б)=0.2; Р(Y=O)=P(O)=0.6, Р(Y=З)=P(З)=0.4,
Итак, руководитель группы должен принять решение:
- · проводить ли эксперимент (его стоимость составляет 10 единиц);
- · если проводить, то, как поступать в дальнейшем в зависимости от результатов эксперимента.
Таким образом, получена многошаговая задача принятия решений в условиях риска. Опишем методику нахождения оптимального решения.
Шаг 1. Построим дерево (рис. 1), на котором указаны все этапы процесса принятия решений - дерево решений. Ветви дерева соответствуют возможным альтернативам, а вершины - возникающим ситуациям. Альтернативами руководителя поисковой группы являются: б - отказ от эксперимента, в - проведение эксперимента, x1 - бурить, x2 - не бурить. Состояния природы: выбор типа скважины (С, М, Б), а также выбор структуры грунта (О, З).
Построенное дерево определяет игру руководителя группы с природой. Позициями данной игры служат вершины дерева, а ходами игроков - выбираемые ими решения. Позиции, в которых ход делает руководитель группы, изображены прямоугольником; позиции, в которых ход делает природа, - кружком.
Игра протекает следующим образом. В начальной позиции ход делает руководитель группы. Он должен принять решение - отказаться от эксперимента (выбрать решение б) или проводить эксперимент (выбрать решение в). Если он отказался от эксперимента, то игра переходит в следующую позицию, в которой руководитель группы должен принять решение: бурить (выбрать альтернативу x1) или не бурить (выбрать альтернативу x2). Если же он решает проводить эксперимент, то игра переходит в позицию, в которой ход делает природа, выбирая одно из состояний О или З, соответствующих возможным результатам эксперимента, и т. д. Игра заканчивается тогда, когда она переходит в окончательную позицию (т.е. вершину дерева, для которой нет исходящих из неё ветвей)
Шаг 2. Для каждого решения, которое является ходом природы (т.е. исходит из позиции, изображённой кружком), надо найти вероятность этого хода. Для этого поступаем следующим образом. Для каждой позиции дерева существует единственный путь, соединяющий эту позицию с начальной позицией. Если это для позиции природы, путь, соединяющий её с с начальной позицией, не проходит через позицию (Э), означающую проведение эксперимента, то вероятности состояний Р(С), Р(М) и Р(Б) являются безусловными (доопытными) и находятся из табл. 3:
Р(С)=50/100, Р(М)=30/100, Р(Б)=20/100.
Если же для позиции природы путь, соединяющий её с начальной позицией, проходит через позицию (Э), то вероятности состояний среды становятся условными вероятностями и находятся по формулам (1), используя данные табл. 3:
В позиции (Э) вероятности ходов, приводящих к позициям (О) и (З), находятся из таблицы 3: Р(О)=0.6, Р(З)=0.4.
Рис. 1.
Шаг 3. Произведём оценку всех позиций дерева игры, "спускаясь" от конечных позиций к начальной. Оценкой позиции служит ожидаемый выигрыш в этой позиции. Оценки конечных позиций находим из таблицы 2. Укажем теперь способ нахождения оценки произвольной позиции дерева игры в предположении, что уже найдены оценки всех следующих за ней позиций.
Для позиции природы её оценка представляет собой ожидаемый выигрыш (см. рис 2);
Для позиции игрока оценкой служит максимум всех за ней позиций. Мотив: в "своей" позиции игрок может сделать любой ход, поэтому он выберет тот, который приводит к наибольшему возможному выигрышу (см. рис 3). В каждой позиции игрок помечает черточкой ту ветвь дерева, которая приводит к позиции, имеющей максимальную оценку.
Обратимся к рис. 1. Получаем, что в начальной позиции ожидаемая прибыль без проведения эксперимента (альтернатива б) - 20 единиц; ожидаемая прибыль с проведением эксперимента (альтернатива в) - 28 единиц. Таким образом, целесообразным является решение - проводить эксперимент (сейсморазведку). Далее, если эксперимент покажет, что грунт открытый, то бурение производить не следует, а если замкнутый, то нужно бурить.
- 1 - ветвь: =20
- 2 - ветвь: 0
- 3 - ветвь:= -30
- 4 - ветвь: 0
- 5 - ветвь: =95
- 6 - ветвь: 0
Как следует из условия задачи, значение в 95 единиц мы можем получить с вероятностью 0.4. Следовательно, ожидаемый выигрыш будет равен 0.4*95=38 единицам. Вычитаем расходы на проведение эксперимента равное 10 единицам.
В итоге получим 28 единиц.
Деревья решений иерархически представляют собой логическую структуру принятия решений, и облегчает тем самым понимание задачи и процесс её решения. В отличие от матрицы решений здесь можно видеть временной ход процесса принятия решения. Дерево решений нельзя, однако, в общем случае представить простой матрицей решений; так могут быть представлены лишь отдельные этапы процесса. Разбиение на этапы производят так, чтобы выбор решения начинался с некоторого узла решений, от которого исходят одна или несколько ветвей, представляющих варианты решений. Далее следуют узлы событий и на конце - листья", представляющие конечные состояния с указанием значений соответствующих выходных параметров. Если же за узлами событий следует опять узел решений с соответствующими действиями, тогда это и всё последующие разветвления относятся к более поздней стадии выбора решения.. Таким образом, можно проследить весь путь с начала до конца дерева решений.
В дереве решений различают узлы событий и узлы решений. Можно себе представить, что в узлах событий выбор дальнейшего пути определяется внешними условиями (природой, в теории игр противником), а в узлах решений - лицом, принимающим решение.
Деревья решений легко поддаются модификации: при необходимости их можно дополнительно развить, а в случаях, когда какие-либо ветви практически лишены значения, - соответственно уменьшить. Узлы решений, если они связаны с одним действием и не разделены узлами событий могут быть объединены. То же справедливо и для узлов событий.
Доверенности
