Алгебраическое описание мер доверия, ближайших к заданной вероятностной мере с приложением в теории игр

Размещено на http://www.allbest.ru/

Алгебраическое описание мер доверия, ближайших к заданной вероятностной мере с приложением в теории игр

Лепский А.Е., д.ф.-м.н., доцент

Технологический институт ЮФУ г. Таганрог

тел.: (8634-)371-741

e-mail: lepskiy@mail.ru

Введение

Пусть - некоторое конечное множество, - множество всех подмножеств из . Рассмотрим на меру (функцию) доверия (belief measure) [1] , , которая в так называемой теории свидетельств (theory of evidence) [2] трактуется как степень доверия принадлежности элемента множеству [1]. В теории свидетельств функция доверия определяется с помощью функции множеств , называемой базовым вероятностным назначением (basic probability assignment), следующим образом [2]:

, .

Тогда . Множество всех мер доверия на будем обозначать через .

Наряду с функцией доверия в теории свидетельств рассматривается и двойственная ей функция - функция правдоподобия , причем отношение двойственности устанавливается с помощью равенства , .

В работах [3, 4] рассматривалась задача нахождения вероятности, наименее уклоняющейся в среднеквадратичном от заданной меры доверия g Кроме того, в этих же работах исследовалась обратная задача, а именно, для заданной вероятности ( _ множество всех вероятностных мер на ) находилось множество всех таких мер доверия g, для которых вероятность оказывалась ближайшей вероятностью. Множество всех таких мер доверия будем называть классом ближайших мер доверия и обозначать через .

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

доверие коалиционный игра алгебраический

1. Вероятностная МЕРА, наименее уклоняющаяся от заданной меры доверия

Важным классом нижних вероятностей является класс так называемых примитивных мер, т.е. мер вида , , () [5]. В данной работе нам понадобятся примитивные меры в случае, когда ( _ мощность множества). Для таких мер (вероятностных мер Дирака) будем использовать обозначения , . Очевидно, что , где _ символ Кронекера.

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

Пусть . Введем в рассмотрение коэффициенты , . Заметим, что , если и , если . В работах [3,4] были получены следующие основные результаты.

Теорема 1. Для любой меры доверия существует единственная вероятностная мера такая, что норма будет минимальной, причем , где

, , .

Следствие. Имеем , где .

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

Пример 1. Предположим, что 10 экспертов определяют одну из четырех компаний a, b, c и d, акции которой будут расти быстрее всего: 3 эксперта высказались, что это будет компания a или b; 3 других эксперта высказались в пользу компаний b, c или d; еще 3 эксперта выразили мнение, что это будет компания a, c или d; наконец, 1 эксперт уверен, что это будет компания a или c. По частоте высказываний найдем базовое вероятностное назначение: , . Далее найдем значения функции доверия для одноэлементных множеств: и трехэлементных множеств: , . Найдем значения меры правдоподобия событий , , и : , , , . Таким образом, мы получили нижние и верхние вероятности событий: , , , . Причем неопределенности вероятностей событий , и , _ попарно одинаковы. Если же найти оптимальные вероятности событий , , и , то получим: , , , . Т.е. событие здесь оказывается значительно менее вероятным, чем событие , а событие _ более вероятно, чем .

2. Меры доверия, ближайшие в среднеквадратичном к заданной вероятности

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

Теорема 2. Класс состоит из функций множеств , где числа , , удовлетворяет условиям:

1) , ;

2) , ; 3) .

Следствие. Пусть . Тогда в том и только том случае, если числа , , удовлетворяют условиям:

1) , ;

2) , ; 3) .

3. Экстремальные меры доверия, ближайшие к вероятностной мере

Класс является выпуклым множеством. Согласно теореме Крейна-Мильмана любое выпуклое множество является выпуклой оболочкой своих крайних (экстремальных) точек [6].

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

, , ,

следует либо , либо .

Множество всех экстремальных точек (крайнее множество) выпуклого множества будем обозначать через .

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

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

Решим сначала указанную задачу для класса , где _ равновероятная мера ( для всех ).

Некоторые множества экстремальных мер доверия, ближайших в среднеквадратичном к равновероятной мере

Пусть _ такое семейство непустых подмножеств из , что . Рассмотрим меру доверия:

.

Найдем достаточные условия того, чтобы мера была экстремальной мерой в классе . Пусть . Из теоремы 2 видно, что тогда и только тогда, когда семейство множеств и числа , , удовлетворяют системе

, , (1)

, . (2)

Предположим, что для семейства и чисел , , выполняются условия

, . (3)

Тогда будет выполняться условие (1), а уравнения (2) будут равносильны уравнениям

, . (4)

Справедлива следующая лемма.

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

1) _ множество всех подмножеств из одной мощности;

2) _ разбиение , т.е. такое множество непустых подмножеств, что и для любых , из следует, что .

Тогда для справедливо условие (4).

Следствие. Пусть семейство различных непустых подмножеств из удовлетворяет одному из условий 1), 2) леммы 1. Тогда, если для чисел , , выполняется условие (3), то .

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

Лемма 2. Если семейство различных непустых подмножеств из удовлетворяет условию (4), то также удовлетворяет этому условию.

Исследуем экстремальность мер, удовлетворяющих условиям (3) и 1) леммы 1.

Предложение 1. Пусть _ множество всех подмножеств из одной мощности , а числа , , удовлетворяют условие (3). Тогда мера в том и только том случае, если или .

Исследуем экстремальность мер, удовлетворяющих условиям (3), когда _ разбиение множества . Обозначим через множество всех разбиений множества . Нам понадобится следующая лемма.

Лемма 3. Если , то система

имеет единственное решение , .

Предложение 2. Пусть , а числа , , удовлетворяют условие (3). Тогда мера .

Используя результат леммы 2 и осуществляя выкладки, аналогичные доказательству предложения 2, нетрудно показать справедливость следствия.

Следствие. Пусть , а числа , , удовлетворяют условие (3). Тогда мера .

Подытоживая результаты предложения 2 и его следствия, можно сделать следующий вывод.

Теорема 3. Пусть . Тогда меры и , , , являются экстремальными мерами класса .

Пример 2. 1) Если , то ;

2) если , , то , .

Экстремальные меры доверия, ближайшие в среднеквадратичном к произвольной вероятностной мере

Исследуем теперь множество экстремальных мер доверия класса , когда _ произвольная вероятностная мера. Рассмотрим отображение , действующее по правилу: если , то , , где такое наибольшее число, что . Тогда .

Нетрудно видеть, что _ сюръективное отображение. Действительно, если _ общее решение системы уравнений , , , то _ общее решение однородной системы , , , а _ частное решение неоднородной системы , , . Поэтому _ общее решение этой же неоднородной системы. Выбор такого наибольшего числа , чтобы обеспечивает выполнения условия , . Согласно теореме 2 _ произвольная мера класса .

Справедливо следующее предложение.

Предложение 3. Если , то .

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

Лемма 4. Пусть такая вероятностная мера, что для всех . Тогда , в том и только том случае, когда .

Оценка числа экстремальных мер доверия, ближайших в среднеквадратичном к равновероятной мере

Оценим число экстремальных мер класса , удовлетворяющих теореме 3. Это число связано с числом всех разбиений конечного множества . Общее число разбиений множества в комбинаторике называется числом Белла [7] и обозначается . Для чисел Белла известна рекуррентная формула [7] , .

Через обозначим число экстремальных мер класса . Число экстремальных мер класса не превосходит числа вершин (0-граней) мерного выпуклого многогранника с гипергранями, где , , . Следующее предложение нетрудно доказать, используя теорему 3 и точные оценки для возможного числа 0-граней мерного выпуклого многогранника с гипергранями [8].

Предложение 4. Для числа экстремальных мер класса справедлива оценка: , где ,

Следствие. Если такая вероятностная мера, что для всех , то для числа экстремальных мер класса справедлива оценка: , где _ числа из предложение 4.

Пример 3. Из предложения 4 следует, что , , .

Найдем экстремальные меры класса , когда .

Пример 4. Пусть . Тогда , где , . Этим разбиениям соответствуют экстремальные меры и . В силу предложения 4 . Поэтому _ крайнее множество в классе , если .

Пример 5. Пусть . Тогда , где , , , , . Причем только разбиение имеет новое непустое «дополнение» . Таким образом имеем 6 экстремальных мер удовлетворяющих теореме 3 (пусть , , ): , , (), . Покажем, что множество , если , т.е. для любой меры найдутся такие числа , , , что

. (5)

Если , то решением уравнения (5) будут числа , , (), , где _ индекс элемента множества с наименьшим основным вероятностным назначением, т.е. . Тогда нетрудно видеть, что , , и . Таким образом, , если .

Пример 6. Пусть . Найдем экстремальные меры класса с помощью отображения , зная экстремальные меры класса , найденные в примере 5. Пусть , . Тогда имеем:

1) , где такое наибольшее число, что . Нетрудно показать, что . Следовательно, . Аналогично:

2) .

3) , .

4) .

4. Задача оценки выигрышей коалиций при заданных полезностях отдельных игроков

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

Требуется оценить выигрыши отдельных коалиций.

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

и .

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

,

где , , а -е неравенство в системе можно представить в виде

,

. Аналогично,

,

где . Поэтому система равносильна системе

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

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

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

, , ,

, , .

Литература

1. Smets P. Belief Functions and Transferable Belief Model

2. http://ippserv.rug.ac.be.

3. Shafer G. A Mathematical Theory of Evidence. - Princeton, N.J.: Princeton University Press, 1976.

4. Лепский А.Е. Вероятностная аппроксимация мер доверия// Интегрированные модели и мягкие вычисления в искусственном интеллекте. Труды IV-й Международной научно-практической конференции (Коломна, 28-30 мая 2007 г.). - М.: Физматлит, 2007. - С.212-219.

5. Lepskiy A.E. The Class of Nearest Belief Functions to a Given Probability Measure// Proceedings of the NAFIPS'08. _ New York. - 2008. - №60608.

6. Murofushi T., Sugeno M. An Interpretation of Fuzzy Measures and the Choquet Integral as an Integral with Respect to a Fuzzy Measure// Fuzzy Sets and Systems. - 1989. - №29.

7. Эдвардс Р. Функциональный анализ. _ М.: Мир, 1969.

8. Стенли Р. Перечислительная комбинаторика. _ М.: Мир, 1990.

9. Брёнстед А. Введение в теорию выпуклых многогранников. _ М.: Мир, 1988.

Размещено на Allbest.ru