О числе пар объектов, связанных отношением

Парето-доминирования

Димитриади Г. Г. (george d@mail.ru)

Институт системного анализа РАН Введение

Рассмотрим множество альтернатив таких и только таких, что каждой из них могут быть присвоены оценки по некоторым выработанным заранее критериям. При этом предполагается, что по каждому критерию имеется порядковая шкала оценок. Первая оценка по шкале считается лучше второй оценки, вторая - лучше третьей и т.д. Будем рассматривать бинарное отношение на множестве альтернатив. Альтернативы в паре могут находиться в следующих отношениях: равенства (если они равны), доминирования по Эджворту-Парето (одна альтернатива «лучше» другой; см. ниже точное определение) и несравнимости (во всех остальных случаях).

Требуется число пар альтернатив, находящихся в отношении Эджворта-Парето.

Теперь рассмотрим точную математическую постановку задачи.

Задача. Будем считать, что выработаны критерии и шкалы оценок по ним. Все критерии и оценки имеют словесные названия. Отвлечемся от них и будем критерии и оценки на них обозначить числами. Пусть имеется набор Q критериев (Q>2) с nq >2 оценками по каждому критерию (q = 1,!,Q). Оценки по q-ому критерию будем обозначать числами 1,2,..., nq, причем 1-ую оценку по критерию будем считать лучше 2-ой, 2-ую - лучше 3-ей и т.д. Рассматриваем множество всех такие и только таких объектов (или альтернатив), которым может быть сопоставлен набор оценок (j1,у2,...,jQ), j1 е1,...,n1, j2е1,...,n2 , ...,

jQ e 1,!, nQ по этим критериям. Дадим определение доминирования по Эджвор-ту-Парето.

Определение. Говорят, что альтернатива A(j, j2jQ) строго доминирует

или доминирует по Эджворту-Парето альтернативу B(j",f2jQ), если по

шкалам всех критериев оценки альтернативы A не хуже оценок альтернативы B, а хотя бы по одному критерию оценка у альтернативы A лучше, т.е. jq > jyq = 1,!,Q и 3qe 1,!,Q : j > j"q.

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

Нахождение искомого числа пар

Вектор оценок можно рассматривать как набор координат, и каждой аль-

тернативе однозначно соответствует точка из Ry с соответствующими координатами. Тогда все объекты и только они будут изображены графически точками с натуральными координатами из Q-мерного прямоугольного параллелепипеда [1, n1 ] х [1, n2] X! х [1, nQ ]. В такой геометрической интерпретации данную альтернативу (т.е. точку из r Q) с координатами (jjQ) доминируют по Парето

те и только те точки с натуральными координатами, что лежат в прямоугольном параллелепипеде P = [1,j]х[1,j2]х...х[1,jQ] (кроме самой точки (jjQ))

(См. двумерную иллюстрацию). Значит, число альтернатив, доминирующих данную вершину, есть j j2 - jQ -1. Для нахождения ответа на вопрос задачи надо указанное количество просуммировать по всем возможным наборам (j1,! jQ) (т.е. по всем точкам с натуральными координатами из Q-мерного прямоугольного параллелепипеда P = [1, n1 ] х [1, n2] х... х [1, nQ ]). В итоге получим:

1] = x ц-jq]- x 1

A

[j1 - jQ ] - n1-nQ

A

АП1 + 1

A = n,--...nQ

1 nQ

nQ +1

11 2 ""Q 2

П1... nQ = nQ [

(П1 + 1)-(nQ + 1)

2*

-1]

Последняя формула и дает искомое число A.

Заметим, что полученная формула дает те же результаты, что и более частная, выведенная в [2].

Примеры. 1) Пусть критериев Q = 3, оценок по ним - n1 = n2 = n3 = 2. Тогда 27

A = 8(--1) = 19. В том, что эта число верно, можно убедиться непосредствен-

8

ным подсчетом.

2) Пусть критериев Q = 4, оценок по ним - n1 = n2 = n3 = n4 = 2. Тогда

A = 16(- -1) = 65. 16