Автореферат (Концепции решений в задаче коллективного выбора), страница 4

Длина такого путиесть µ-диаметр множества A, d(µ). Из определения k() следует, чтоk(µ)d(µ)(µ) при k<d(µ) и d(µ)(µ)=k(µ)=(µ) для любого k: kd(µ). Такжедолжен существовать минимальный -путь длины большей либо равной длинелюбого другого минимального µ-пути в A. Длина этого пути есть -диаметрмножества A, d().

Аналогично, k()d()() при k<d() и d()()=k()=()для всех k: kd(). Поскольку M(k) и U(k) представляют отношения k(µ) и k(),то M(d(µ)) и U(d()) суть представления отношений (µ) и (), соответственно.Также M(d(µ))M(d(µ)-1) & M(d(µ))=M(d(µ)+1) и U(d())U(d()-1) & U(d())=U(d()+1).Для того чтобы вычислить минимальное доминирующее множество MD иобъединение минимальных недоминируемых множеств MU, необходимовоспользоваться следующей теоремой: MU=MAX((µ)), MD=MAX(()).Т.к.

MU=MAX((µ)), то =(µ), а R=M(d), где d=d(µ). Согласно Лемме 4.2tr)a .для векторa множества MU получаем: mu= (M(d)  M(d)Т.к. UT=MAX(), то согласно Лемме 4.2 для вектора множества UTполучаем: ut=max()= (M(d)  T)  a . Значение d=d(µ) определяется из M(d)M(d-1)& M(d)=M(d+1).Т.к. MD=MAX(()), то =(µ), а R=U(d), где d=d(). Согласно Лемме 4.2для векторa множества MD получается формула: md= U(d)  a . Значение dопределяется из условия U(d)U(d-1) & U(d)=U(d+1).В разделе 4.6 дается матрично-векторное представление второй версииминимального слабоустойчивого множества: mwsII=(M+E) (U  M  U)  a .Представление для первой версии этого решения получить не удалось.20Вразделе4.7предлагаютсяновыеверсиинепокрытогоислабоустойчивого множеств и вычисляются их вектора.

В частности, вектортретьей версии минимального слабоустойчивого множества вычисляется поформуле mwsIII= (M  U  U)  a +diag((M+T) (M  U  E)  M ), где diag(R) обозначаетвектор, составленный из диагональных элементов матрицы R.В разделе 4.8 с помощью представлений новых версий решений,введенных в предыдущем разделе, были получены матрично-векторныепредставления классов k-устойчивых альтернатив и k-устойчивых множеств. Изопределения классов SP(k), множеств P(k), а также пустоты отношения равенстваголосов следует, что iP(k)  iMAX(k(µ)), то есть, P(k)=MAX(k(µ)).СогласноЛемме4.2длявекторамножестваP(k)получаем:p(k)= (M(k)  E)  a = M(k)  a .

Т.к. как все матрицы - булевые, то имеет месторавенствоkMi 1ki+E=(M+E)k. Следовательно, M(k)=  M i +E=Uk и p(k)= U k  a .i 1Обозначим sp(k) вектор множества SP(k). По определению P(k) iSP(k) iP(k)&iP(k-1).sp(k)i=p(k)i p(k -1)i = p(k)i  p(k -1)i ,Следовательно,тоесть,sp(k)= p(k)  p(k -1) = M(k)  a  M( k -1)  a = U k  a  U k -1  a .Введем обозначение (k) для отношения k(µ), (k)=k(µ). Такжеобозначим µ(k) асимметричную часть отношения k(µ) и (k) - симметричнуючасть этого отношения. Из определений следует, что (1)=, µ(1)=µ, (1)=.Будем рассматривать отношения (k) и µ(k) как новые версии отношений  и µ.Если множество B, BA, является k-устойчивым, то из k-устойчивогомножества следует, что любая альтернатива j, не принадлежащая B, будетдостижима из какой-то альтернативы i, принадлежащей B, за один (k)-шаг, тоесть, j: jA\B  i: iB & i(k)j.

Если порядок устойчивости B выше чем k, тоj: jA\B & i: iB  (i, j)(k). Следовательно, если B есть минимальное kустойчивое множество по отношению µ, то оно также должно бытьминимальным слабоустойчивым (согласно третьей версии определения)21множеством по отношению (k). Наоборот, если B есть минимальноеслабоустойчивое (согласно третьей версии определения) множество поотношению (k), то оно также должно быть минимальным устойчивыммножеством по отношению µ порядка устойчивости не ниже k.Обозначим ss(k) и s(k) вектора классов k-устойчивых множеств SS(k) и изсумм S(k)=SS(1)+SS(2)+…+SS(k), соответственно.

Обозначим MWSIII((k)) иmwsIII((k)) объединение минимальных слабоустойчивых (согласно третьейверсии определения) множеств, вычисленное для отношения (k) на A, и еговектор, соответственно. Тогда iSS(k)  iMWSIII((k)) и iMWSIII((k)) iSS(x), x: xk, т.е. SS(k)MWSIII((k)) и MWSIII((k))S(k)  s(k)=mwsIII((k))+s(k-1).Поскольку класс SS(1) есть не что иное, как объединение минимальныхслабоустойчивых множеств (по отношению µ), то для вычисления векторов s(k)мы получаем индуктивную формулу: s(1)=ss(1)=mws=(M+E)p(2)=U U 2  a ,~ ~~~~~ ~~s(k)=s(k-1)+mwsIII((k))=s(k-1)+ (M  U  U)  a +diag( (M  T)  (M  U  E)  M ),~~tr M( k) ) .где U =M(k), M = (M(k)Т.к. согласно Теореме 3.2 имеет место P(k)S(k)P(k+2)MD, то итерациидолжны остановиться между k=m-2 и k=m, когда s(k) станет равным md=p(m).Наконец, iSS(k)  iS(k) & iS(k-1) ss(k)i=s(k)i s(k -1)i = s(k)i  s(k -1)i , т.е.

ss(k)= s(k)  s(k -1) .В разделе 4.9 дается точная оценка сложности вычисления решений спомощью их матрично-векторных представлений.Раздел 4.10 посвящен компьютерной реализации этих алгоритмов.В Заключении сформулированы основные результаты работы ипредложены возможные направления дальнейших исследований: исследованиесвязи распределения вершин полных орграфов по классам k-устойчивыхальтернатив и множеств с другими параметрами графа, с решениями различныхигрнаграфах,иприменениеконцепциймножеств-решенийзадачиколлективного выбора для обработки данных рейтинговых голосований иданных социологических опросов, выявляющих предпочтения респондентов.22III.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИОННОЙ РАБОТЫ1. Сформулирован критерий принадлежности любой альтернативы какомулибоминимальномуслабоустойчивомумножеству.Сегопомощьюустановлено, что непокрытое множество является подмножеством объединенияминимальных слабоустойчивых множеств.2. Построены обобщения минимального доминирующего множества, и с ихпомощью выяснено, как устроена система доминирующих множеств.3.

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

Введены пять новых версий непокрытого множества и две новые версииминимального слабоустойчивого множества.5. Построено представление множеств-решений в виде булевых векторов,значениякоторыхопределяютсякакрезультатпоследовательностиарифметических операций над булевыми матрицами, представляющимиотношения. В таком виде представлены почти все рассмотренные решения(кроме и одной из трех версий минимального слабоустойчивого множества) иих обобщения (классы k-устойчивых альтернатив и k-устойчивых множеств).Логико-алгебраическое представление концепций решений определяеталгоритм их вычисления. Дана точная оценка сложности вычисления решений спомощью этих представлений. Осуществлена их компьютерная реализация.23IV. СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИРаботы, опубликованные автором в ведущих рецензируемых научныхжурналах и журналах, рекомендованных ВАК Министерства образованияи науки России:1. АлескеровФ.Т.,СубочевА.Н.Обустойчивыхрешенияхвординальной задаче выбора // Доклады Академии Наук.

2009. Т. 426. №3. Стр.318-320. 0,35 п.л. (вклад автора 0,28 п.л.)2. Субочев А.Н. Доминирующие, слабоустойчивые и непокрытыемножества: свойства и обобщения // Автоматика и Телемеханика. 2010. №1.1,00 п.л.Другиеработы,опубликованныеавторомпотемекандидатскойдиссертации3. Subochev A.

Dominant, Weakly Stable, Uncovered Sets: Properties andExtensions: Working paper WP7/2008/03. Moscow: SU - Higher School ofEconomics. 2008. 1,90 п.л.4. Субочев А.Н. Доминирующие, слабоустойчивые и непокрытыемножества: свойства и обобщения // Труды IV Международной конференции попроблемам управления. М.: ИПУ РАН. 2009. 0,65 п.л5. Aleskerov F., Subochev A. Matrix-vector representation of various solutionconcepts.

Working paper WP7/2009/03. Moscow: SU - Higher School of Economics.2009. 2,09 п.л. (вклад автора 1,67 п.л.)24Лицензия ЛР №020832 от 15 октября 1993 г.Подписано в печать 20 ноября 2009г. Формат 60х84/16Бумага офсетная. Печать офсетная.Усл. печ. л. 1,0.Тираж 100 экз. Заказ № ____Типография издательства ГУ-ВШЭ125319, г. Москва, Кочновский пр-д, д.325.