§ 5.5. Построение ядра в пространстве QO

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

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

Рис. 5.2.

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

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

1. Прообраз множества в пространстве относительно отображения непуст. В этом случае за ядро исходного множества X принимаем прообраз ядра множества

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

В качестве такой точки предлагается рассматривать максимальную точку содержащуюся (в смысле «не превосходящую»)

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

Следующее утверждение позволит нам указать алгоритм для построения отношения

Теорема 5.4. Образ точки приотображении совпадает с транзитивным замыканием отношения

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

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

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