ЭКОНОМИКА И МАТЕМАТИЧЕСКИЕ МЕТОДЫ, 2014, том 50, № 3, с. 130-133
МАТЕМАТИЧЕСКИЙ АНАЛИЗ ЭКОНОМИЧЕСКИХ МОДЕЛЕЙ
НОВЫЕ ПОДХОДЫ К АНАЛИЗУ ПАРНЫХ СРАВНЕНИЙ
© 2014 г. А.А. Заславский
(Москва)
Традиционными задачами обработки парных сравнений являются количественная оценка нетранзитивности данной матрицы и поиск транзитивной матрицы, ближайшей к данной. В работе содержится обзор предложенных в последнее время методов решения этих задач для парных сравнений с ничьими, а также обсуждаются новые постановки задач, связанные с ослаблением условия транзитивности.
Ключевые слова: парные сравнения, транзитивность, матрица расстояний. Классификация 1ЕЬ: С02.
1. ВВЕДЕНИЕ
Парные сравнения (Дэвид, 1978) являются одним из видов экспертных оценок. Применяться они начали раньше остальных видов оценок. Поэтому к настоящему времени разработано множество алгоритмов анализа парных сравнений (Пригарина, Чеботарев, 1989), в том числе статистические методики, процедуры, использующие различные меры близости, подходы теории группового выбора и т.д.
В данной работе мы будем рассматривать парные сравнения п объектов с ничьими. Это означает, что когда эксперту предъявляют пары объектов, то он сообщает, какой из двух объектов предпочтительнее, либо объявляет их равноценными (ничья). Результаты сравнений записываются в матрицу X (без диагональных элементов). Это означает, что если эксперт предпочел объект г объекту у, то х у = 1 и х]г = 0, а если объекты равноценны, то ху = ху = 1/21. Таким образом, для любых различных г и у Ху + Хр = 1. Для каждого объекта найдем сумму набранных им очков:
= /х у. Будем считать объекты упорядоченными по возрастанию этих сумм, т.е. 51 < ... < яп.
У !г
Вообще говоря, ответы эксперта могут содержать противоречия, т.е. для некоторых объектов ¿1,., гт может оказаться, что хг-1г-2>1/2, хг2г3>1/2, ..., х1т1 т >1/2, х тг1>1/2, причем среди этих неравенств есть строгие. Тогда можно показать (см., например, (Заславский, Френкин, 2009)), что в матрице X обязательно найдется подматрица 3*3 одного из следующих видов:
- 1 0' ' - 1 1/2' ' - 1/2 1 '
^1 = 0 - 1 , ^2 = 0 - 1 , ^ = 1/2 - 1/2
1 0 -' ,1/2 0 - ' , 0 1/2 - '
Если X не содержит таких подматриц, объекты можно разбить на несколько классов, причем объекты из одного класса эксперт считает равноценными, а объект из класса с большим номером предпочитает объекту из класса с меньшим номером. Такие матрицы будем называть транзитивными.
Если матрица ответов эксперта нетранзитивна, то возникает задача количественной оценки степени ее нетранзитивности. Для парных сравнений без ничьих естественной мерой нетранзи-
1 Можно рассмотреть более общую постановку, когда эксперт оценивает степень предпочтительности, т.е. величины могут принимать произвольные значения между 0 и 1, но в данной работе мы этого делать не будем.
НОВЫЕ ПОДХОДЫ К АНАЛИЗУ ПАРНЫХ СРАВНЕНИИ
131
тивности является количество ЫТ подматриц 3*3, равных У1. Как показано в (Дэвид, 1978), ЫТ выражается через числа я 1 следующим образом
ЫТ = п(п -1)(2п - 1)/12 - (/я21/2.
=1 /
Для парных сравнений с ничьими существуют три вида нетранзитивных подматриц, поэтому выбор меры нетранзитивности не столь очевиден. Кроме того, эта мера не может быть выражена только через числа я,. Подход к оценке нетранзитивности таких матриц будет описан в разд. 2.
В практических экспертизах, как правило, ответ на поставленный вопрос дают несколько экспертов, после чего их мнения агрегируются. Получение агрегированного мнения является достаточно сложной математической задачей, для решения которой разработано множество методов, большинство из них основаны на введении некоторой меры близости d между ответами
N
экспертов и нахождении матрицы X, минимизирующей сумму /d(X, X1), где X1,..., ХЫ - мат-
I=1
рицы, полученные от различных экспертов. В частности, в методе парных сравнений часто применяется метрика Хемминга (Кемени, Снелл, 1972), согласно которой матрица X находится по правилу большинства:
' N N
1 /4 > /4"
Ху
1 =1
N
1 =1 N
1/2, /4=/4,
1=1 1=1
N N
0 /4 < /х'и.
1=1
1=1
Известно, что матрица X может оказаться нетранзитивной даже при транзитивных X1,., XN. Поэтому, если результат экспертизы должен быть транзитивным, возникает задача определения транзитивной матрицы, ближайшей к X В случае использования в качестве меры близости метрики Хемминга эта задача оказывается в вычислительном отношении весьма сложной (Гильбурд, 1988). Альтернативный подход к ее решению будет описан ниже.
2. ИЗМЕРЕНИЕ НЕТРАНЗИТИВНОСТИ ДЛЯ ПАРНЫХ СРАВНЕНИИ С НИЧЬИМИ
Мерой нетранзитивности естественно считать величину Ж1 = а + Ьх + су, где а, Ь, с - число подматриц, равных У1, У2, У3 соответственно; х, у - некоторые коэффициенты. Понятно, что для вычисления ^ недостаточно знать количества очков я,, но, возможно, его удастся выразить через числа V, п, р, выигрышей, ничьих и проигрышей каждого объекта. Таким образом, необходимо найти ответ на вопросы:
1) существуют ли веса х, у, при которых Ж1 выражается через V,, п,, р
2) какова формула для Ж1 при этих значениях х, у.
Ответ на оба вопроса был получен в работе (Заславский, Френкин, 2009): х = 1/2, у = 1/6 и ^ = ((п3 - п) - /п,(п, + 2) - з/(у^ - р,)2)/24. Разумеется, если все п{ = 0, то vi= я,,р, = п - 1 - я, и эта формула переходит в приведенную выше.
Стоит отметить, что практическая ценность полученной формулы несколько снижается из-за отсутствия содержательной интерпретации найденных значений весов х, у. Действительно, если значение 1/2 для отношения весов подматриц У2 и У1 выглядит довольно логичным, то содержательно обосновать выбор значения у = 1/6 пока не удалось.
132
ЗАСЛАВСКИИ
3. ПОСТРОЕНИЕ ТРАНЗИТИВНОЙ матрицы, ближайшей к ДАННОЙ
В работе (Заславский, 2007) был предложен следующий "геометрический" подход к построению по данной матрице ближайшей транзитивной.
В п-мерном пространстве для каждой матрицы Xвозьмем точку с координатами (я1, ..., *п) и построим выпуклую оболочку М этих точек. Следующее утверждение описывает строение множества М.
Теорема 1. Мявляется вписанным в сферу (п - 1)-мерным многогранником, вершины которого соответствуют транзитивным матрицам.
Построим теперь точку Р ! М, соответствующую матрице X, и будем искать ближайшую к Р вершину М. Так как М вписано в сферу, для решения этой задачи можно предложить весьма эффективный алгоритм, описанный в работе (Заславский, Шевлякова, 2010). Проведенный вычислительный эксперимент показал, что этот алгоритм дает результаты, достаточно близкие к традиционным, но по эффективности значительно превосходит стандартные методы.
4. ОСЛАБЛЕНИЕ УСЛОВИЯ ТРАНЗИТИВНОСТИ
Требование транзитивности матрицы парных сравнений представляется слишком жестким. Представим, что у нас есть п предметов различной массы и чашечные весы с некоторым порогом чувствительности, т.е. их чашки остаются в равновесии, если массы положенных на них предметов отличаются меньше чем на критическое значение е. Тогда, если взвесить каждую пару предметов и составить из результатов взвешиваний матрицу, то в ней вполне могут оказаться подматрицы, равные У3 (если разности весов первого и второго, а также второго и третьего предметов меньше порога, но разность весов первого и третьего больше).
Вместо транзитивности полученная матрица обладает следующим, более слабым свойством: если я, > р то для любого к, отличного от ,, у х,к > х]к. Назовем такую матрицу правильной. В (Заславский, Френкин, 2009) доказана следующая теорема.
Теорема 2. Матрица Xявляется правильной тогда и только тогда, когда она не содержит подматриц, равных У1, У2, а также подматриц 4*4 вида
- 1/2 1 1 - 1/2 1/2 1
1/2 - 1/2 1/2 1/2 - 1 1/2
, Z 2 =
0 1/2 - 1 1/2 0 - 1/2
0 1/2 0 - , 0 1/2 1/2 -
Для количественной оценки неправильности матрицы представляется естественным использовать какую-нибудь функцию от числа подматриц, равных У1, У2, Z1, Z2. Однако найти такую просто вычисляемую функцию не удается. По-видимому, если такая функция и существует, то она является нелинейной. Поэтому рассмотрим другой подход к оценке неправильности.
Построим по данной матрице Xматрицу В расстояний между ее строками, элементы которой вычисляются по формуле
п
dij = ^ I х,к - хрк I к =1
(диагональные элементы матрицы X предполагаются равными 1/2). Нетрудно убедиться, что верна следующая теорема.
Теорема 3. Для любой матрицы X и любых ,, р имеет место неравенство
^ > I* - 4 (1)
Причем матрица Xявляется правильной тогда и только тогда, когда все неравенства (1) обращаются в равенства.
НОВЫЕ ПОДХОДЫ К АНАЛИЗУ ПАРНЫХ СРАВНЕНИЙ 133
Таким образом, для оценки неправильности NP матрицы X можно использовать, например, величину
NP = /(dy - Sj+s)
i<j
(напоминаем, что мы считаем объекты упорядоченными по возрастанию s,).
Соответственно, для построения правильной матрицы нужно будет в некоторой метрике найти матрицу, удовлетворяющую условию NP = 0 и ближайшую к исходной. Но пока эффективные алгоритмы решения этой задачи неизвестны.
СПИСОК ЛИТЕРАТУРЫ
Гильбурд М.М. (1988). Об эвристических методах построения медианы в задачах группового выбора // Автоматика и телемеханика. № 7. С. 131-136.
Дэвид Г. (1978). Метод парных сравнений. М.: Статистика.
Заславский А.А. (2007). Геометрия парных сравнений // Автоматика и телемеханика. № 3. С. 181-186. Заславский А., Френкин Б. (2009). Математика турниров. М.: МЦНМО.
Заславский А.А., Шевлякова А.Н. (2010). Геометрический метод анализа парных сравнений. Результаты вычислительного эксперимента // Вестник МЭИ. № 6. С. 5-12.
Кемени Дж., Снелл Дж. (1972). Кибернетическое моделирование. М.: Сов. радио.
Пригарина Т.А., Чеботарев П.Ю. (1989). Методы экспертных оценок на примере определения предпочтительности оценок. Препринт. М.: ЦЭМИ.
Поступила в редакцию 04.07.2013 г.
New Approaches for Analysis of Paired Comparisons
A.A. Zaslavsky
Two traditional problems of paired comparisons analysis are considered: the estimation of non-transitivity and the construction of transitive matrix closest to the given one. Some recent methods for solution of these pro
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.