Содержание к диссертации
Введение
Глава 1. Постановка задачи коллективного выбора. Обзор концепций ее решений 14
1.1 Отношение мажоритарного доминирования и связанные с ним понятия 14
1.2 Доминирующее, недоминируемое и незапертое множества 18
1.3 Непокрытое и незахваченное множества 21
1.4 Слабоустойчивое множество 28
Глава 2. Сравнительный анализ основных решений, строящихся с помощью отношения мажоритарного доминирования 29
Глава 3. Концепции классов k-устойчивых альтернатив и к-устойчивых множеств 43
3.1 К-устойчивые альтернативы 43
3.2 К-устойчивые множества 47
Глава 4. Матрично-векторное представление решений и его компьютерная реализация 53
4.1 Матрично-векторное представление множеств и отношений: основные определения 53
4.2 Отношения ц, т и и. Победитель Кондорсе и ядро 57
4.3 Непокрытое множество 60
4.4 Незахваченное множество 64
4.5 Минимальное доминирующее, минимальное недоминируемое и незапертое множества 65
4.6 Минимальное слабоустойчивое множество 68
4.7 Новые версии непокрытого и слабоустойчивого множеств 68
4.8 Классы k-устойчивых альтернатив и к-устойчивых множеств 74
4.9 Оценка сложности вычислений решений с помощью формул их матрично-векторного представления 79
4.10 Компьютерная реализация вычислений решений с помощью формул их матрично-векторного представления 83
Заключение 84
Литература 89
Приложение 95
- Доминирующее, недоминируемое и незапертое множества
- Сравнительный анализ основных решений, строящихся с помощью отношения мажоритарного доминирования
- К-устойчивые множества
- Отношения ц, т и и. Победитель Кондорсе и ядро
Введение к работе
В настоящей диссертации рассматриваются основные концепции решений в задаче коллективного выбора, связанные с отношением мажоритарного доминирования, которое моделирует предпочтения коллектива. Сравниваются такие решения как ядро, минимальное доминирующее множество, непокрытое множество, минимальное слабоустойчивое множество и другие; выявляется связь между ними. Рассматривается концепция k-устойчивых альтернатив и вводится концепция k-устойчивых множеств; устанавливается их соотношение с вышеназванными решениями. Дается матрично-векторное представление всех рассмотренных множеств-решений, определяющее алгоритм их практического вычисления. Вычисляется сложность этих алгоритмов.
Актуальность работы. Принятие коллективных решений является неотъемлемой частью человеческой жизни. Одной из ключевых проблем моделирования коллективного выбора является отсутствие в общем случае победителя Кондорсе, то есть альтернативы, более предпочтительной для коллектива, чем любая другая альтернатива.
Начиная с конца 70-х гг. прошлого века предпринимаются попытки локализовать результат коллективного выбора в некотором всегда непустом подмножестве множества альтернатив, на котором определено отношение мажоритарного доминирования, моделирующее предпочтения группы. В числе основных концепций решений данного рода были предложены минимальное доминирующее множество, непокрытое множество, минимальное слабоустойчивое множество и другие множества-решения.
Будучи различными воплощениями идеи оптимального коллективного выбора, эти множества позволяют оценивать результаты голосований и даже делать предсказания на основании информации о предпочтениях участников голосования. Ранее применение данных концепций в эмпирических исследованиях затруднялось проблемой вычисления, но в связи с развитием
вычислительной техники в настоящее время интерес к ним активно
возрождается. В частности, совсем недавно (в 2007 г.) были предложены новые концепции решений - незахваченное и незапертое множества. Практическая применимость требует и стимулирует дальнейшее теоретическое исследование данных моделей, чему и посвящена данная работа.
Цель и задачи работы. Целью настоящей диссертационной работы является сравнительный анализ, построение обобщений и нахождение способа вычисления основных концепции решений в задаче коллективного выбора, связанных с отношением мажоритарного доминирования. Для достижения данной цели в настоящей работе решаются следующие задачи.
1. Устанавливаются взаимные соотношения между этими множествами.
2. Обобщаются концепции минимального доминирующего множества,
непокрытого множества, минимального слабоустойчивого множества.
Устанавливается соотношение этих обобщений с другими решениями.
Строится матрично-векторное представление всех рассмотренных множеств-решений, определяющее алгоритм их вычисления.
Методы исследований. Исследование взаимосвязи множеств-решений в задаче коллективного выбора, является фундаментальной теоретической задачей. Методологической парадигмой исследования является теория рационального выбора. Основные методы и средства анализа относятся к математическому аппарату теории графов и теории множеств. Вычисление множеств-решений осуществляется с помощью представления отношений мажоритарного доминирования и отношения равенства голосов и концепций решений задачи коллективного выбора, строящихся с их помощью, в виде булевых матриц и булевых векторов, значения которых определяются как результат последовательности арифметических операций над данными матрицами. Т.о. в анализе также используются логико-алгебраические объекты.
Научная новизна. В ходе решения поставленных задач получены следующие новые результаты:
1. Сформулирован критерий, с помощью которого проверяется
принадлежность любой альтернативы минимальному слабоустойчивому
множеству. С его помощью установлено, что непокрытое множество является подмножеством объединения минимальных слабоустойчивых множеств;
Построены обобщения минимального доминирующего множества, и с их помощью выяснено, как устроена система доминирующих множеств.
Установлены новые соотношения между множествами-решениями.
4. Для турниров впервые введено понятие обобщенно-устойчивого
множества альтернатив. С помощью этого понятия построено обобщение
слабоустойчивого множества - класс k-устойчивых множеств. Доказана теорема
о непустоте классов k-устойчивых альтернатив, и установлено наличие
отношения вложения для классов k-устойчивых альтернатив и k-устойчивых
множеств.
В итоге показано, что в турнирах иерархии классов k-устойчивых альтернатив и k-устойчивых множеств вместе с иерархией доминирующих множеств порождают соответственно микро- и макро-структуру множества альтернатив, в основе которой лежит различие в степени устойчивости.
Предложены два новых определения слабой устойчивости множеств и, соответственно, две новых версии такого решения, как объединение минимальных слабоустойчивых множеств. Предложены пять новых версий непокрытого множества.
Посредством представления отношения мажоритарного доминирования и отношения равенства голосов в виде булевых матриц построено представление соответствующих множеств-решений в виде булевых векторов, значения которых определяются как результат последовательности арифметических операций над данными матрицами. В таком виде представлены почти все рассмотренные концепции решений (победитель Кондорсе, ядро, десять версий непокрытого множества, две из трех версий минимального слабоустойчивого множества, незахваченное множество, незапертое множество, минимальное недоминируемое множество и минимальное доминирующее множество) и их обобщения (классы к-
устойчивых альтернатив и k-устойчивых множеств).
7. Построенное таким образом логико-алгебраическое представление концепций решений определяет алгоритм их вычисления. Дана точная оценка сложности вычисления решений с помощью этих представлений. Осуществлена их компьютерная реализация.
Теоретическая и практическая значимость. Теоретическая ценность работы состоит в том, что выполнен исчерпывающий анализ и дано последовательное и единообразное описание известных множеств-решений. При этом описать удалось практически все известные решения, строящиеся с помощью отношения мажоритарного доминирования, (кроме двух). Используемое описание также позволило предложить новые версии концепций решений, ранее в литературе не рассматривавшиеся. Результаты работы использовались при обновлении программы учебной дисциплины "Методы анализа политических процессов", читаемой студентам 2 курса бакалавриата факультета прикладной политологии Государственного университета - Высшей школы экономики, и учебной дисциплины "Теория коллективного выбора", читаемой студентам 4 курса бакалавриата отделения прикладной математики и информатики факультета бизнес-информатики Государственного университета - Высшей школы экономики.
Достоверность. Достоверность полученных теоретических результатов определяется доказательствами соответствующих утверждений, теорем и лемм и анализом результатов компьютерного моделирования.
Апробация работы и публикации. Основные положения и полученные результаты диссертационной работы прошли апробацию на следующих научных конференциях и семинарах:
IX Международная научная конференция "Модернизация экономики и глобализация", ГУ-ВШЭ, Москва, 1-3 апреля 2008 г., доклад "Концепции стабильных множеств альтернатив - равновесных решений игр, связанных с голосованием";
Общемосковский научный семинар "Математические методы анализа
решений в экономике, бизнесе и политике" (научные руководители д.т.н. Ф.Т.
Алескеров, д.т.н. В.В. Подиновский), Москва, 16 апреля 2008 г., доклад "Концепции стабильных множеств альтернатив - равновесных решений игр, связанных с голосованием";
Общемосковский научный семинар "Экспертные оценки и анализ данных" (научный руководитель д.т.н. Ф.Т. Алескеров), Институт проблем управления им. Трапезникова РАН, Москва, 23 апреля 2008 г., доклад "Концепции решений и их свойства";
Научный семинар "Математическая экономика" (научный руководитель академик РАН В.М. Полтерович), Центральный экономико-математический институт РАН, Москва, 28 октября 2008г., доклад "Множества-решения задачи коллективного выбора: сравнительный анализ";
Научный семинар "Теория управления организационными системами" (научный руководитель член-корреспондент РАН д.т.н. Д. А Новиков), Институт проблем управления им. Трапезникова РАН, Москва, 13 ноября 2008 г., доклад "Доминирующее, слабоустойчивое и непокрытое множества: свойства и обобщения";
Научный семинар отдела "Математическое моделирование экономических систем" Вычислительного центра РАН (научный руководитель академик РАН А. А. Петров), Москва, 19 ноября 2008 г., доклад "Доминирующее, слабоустойчивое и непокрытое множества: свойства и обобщения";
IV Международная конференция по проблемам управления, Институт проблем управления им. Трапезникова РАН, Москва, 26-30 января 2009 г., доклад "Доминирующее, слабоустойчивое и непокрытое множества: свойства и обобщения";
Научный семинар лаборатории теории игр и принятия решения Санкт-петербургского экономико-математического института РАН (научный руководитель д.ф.-м.н. Е.Б. Яновская, Санкт-Петербург), 27 мая 2009 г., доклад "Концепции решений задачи коллективного выбора";
Научный семинар кафедры теории управления факультета прикладной
математики - процессов управления Санкт-Петербургского государственного
университета (научный руководитель д.ф.-м.н. В.Д. Ногин), Петергоф, 28 мая 2009 г., доклад "Концепции решений в задаче коллективного выбора. Доминирующее, слабоустойчивое и непокрытое множества";
Международная конференция ADRES (Association pour le Developpement de la Recherche en Economie et Statistiques) в честь Мориса Салля, университет г. Кан (University of Caen), Кан, Франция, 11 июня 2009 г., доклад "Stable Solutions on Majority Relation", соавтор - Ф.Т. Алескеров;
Международная конференция Association of Southern European Economic Theorists (ASSET) Annual Meeting 2009, Босфорский Университет, Стамбул, Турция, 31 октября 2009 г., доклад "Stable Solutions to the Social Choice Problem: Dominant, Weakly Stable, Uncovered Sets and their Extensions", соавтор - Ф.Т. Алескеров;
Публичная лекция в университете Bilgi, Стамбул, Турция, 5 ноября 2009г. Тема лекции "Solutions on Majority Preference Relation";
Научный семинар кафедры алгебры механико-математического факультета Московского государственного университета, Москва, 17 ноября 2009 г., доклад "Устойчивые решения в задаче коллективного выбора и их матрично-векторное представление", соавтор - Ф.Т. Алескеров;
Результаты исследования также опубликованы в 5 работах, список, которых приводится в конце автореферата.
Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения и списка литературы, включающего 72 наименований. Основная часть работы изложена на 95 страницах, содержит 7 рисунков и 4 таблицы и 1 приложение.
Доминирующее, недоминируемое и незапертое множества
Победителем Кондорсе CW, С We А, называется альтернатива, доминирующая над всеми другими альтернативами, Vx (x CW = CWfxx). Альтернатива х называется слабым победителем Кондорсе тогда и только тогда, когда, во-первых, над ней не доминирует никакая другая альтернатива, и, во-вторых, существует, по крайней мере, одна альтернатива, находящаяся с х в отношении равенства голосов, Vy ут х = (xuy v хту) & 3ZGA XTZ. Множество всех недоминируемых альтернатив называется (мажоритарным) ядром Сг, хєСг = Vy у х = (xuy v хту). В играх, связанных с последовательным голосованием, ядро является т.н. устойчивым решением фон Неймана-Моргенштерна [53], т.е. множеством, обладающим как внутренней, так и внешней устойчивостью (по фон Нейману-Моргенштерну).5
Из определения ядра следует, что ядро есть множество максимальных элементов отношения мажоритарного доминирования. Поэтому ядро является первым и естественным решением задачи коллективного выбора. К сожалению, в общем случае ядро пусто и выбрать что-либо с его помощью невозможно. У отношения коллективного предпочтения может не быть максимальных элементов, т.е. для коллектива может не существовать наилучших альтернатив даже тогда, когда предпочтения каждого индивидуального субъекта являются линейными порядками, и для него есть одна и только одна наилучшая альтернатива. Это обстоятельство получило название парадокса Кондорсе. Данный парадокс за последние полвека исследований в теории коллективного выбора привел к появлению множества альтернативных концепций решений. Были предприняты многочисленные попытки по расширению множества выбираемых альтернатив до некоторых всегда непустых подмножеств общего множества альтернатив, строящихся с помощью отношения мажоритарного доминирования на основании альтернативных интерпретаций условия оптимальности выбора. Исторически первыми концепциями данного рода стали доминирующее и недоминируемое множества. Множество D, DczA, называется доминирующим множеством [63, 72], если оно непусто, и любая альтернатива из D доминирует над всеми альтернативами, не принадлежащими D, Т Ф0 & ((xeD & yD) = xjj.y)}. Доминирующее множество MD (sMD(i)) называется минимальным доминирующим множеством [33, 49, 64] если ни одно из его собственных подмножеств не является доминирующим множеством. Множество MD(2) называется минимальными доминирующим множеством второго порядка, если оно является минимальным доминирующим множеством для множества AYMD. МО(5) есть минимальное доминирующее множество і-того порядка, если оно является минимальным доминирующим множеством для множества A\(uMD(j)), l j i-l. Множество U, UczA, называется недоминируемым множеством [72], если никакая альтернатива, не принадлежащая U, не доминирует ни над какой альтернативой из U, (xeU & ygU) = (у, x)gjj.. Недоминируемое множество MU называется минимальным недоминируемым множеством [66], если ни одно из его собственных подмножеств не является недоминируемым множеством. Если минимальное недоминируемое множество не единственно, то в качестве решения задачи коллективного выбора берется объединение этих множеств [68], которое тоже будет обозначаться MU. Говорят, что альтернатива х запирает альтернативу у, если х доминирует над у и не достижима из у через отношение JI, то есть, хну, и не существует пути оту дох [22]. Незапертое множество [22] UT состоит из альтернатив, которые не заперты никакими другими альтернативами. Впервые концепции доминирующего и недоминируемого множества появляются в работе Б. У орда [72], который называл их "мажоритарными множествами", отобранными согласно "сильной" и "слабой" процедурам, соответственно.
Дж. Смит [63] для оценки различных процедур выбора сформулировал критерий, названный им "критерием Кондорсе", который также можно рассматривать как определение доминирующего множества. Из определения этого критерия следует, что процедура, ему удовлетворяющая, приводит к выбору только альтернатив из минимального доминирующего множества, поэтому именно Смита часто называют автором данной концепции решения, хотя ни один из вышеназванных авторов не формулировал условие минимальности для введенных им множеств явным образом. Другими названиями минимального доминирующего множества, встречающимися в литературе, являются "минимальное недоминируемое множество", "множество Кондорсе" [36, 49]; "GETCHA" [69]; "слабый верхний цикл". Хотя П. Фишберн [33] и не определяет концепцию минимального доминирующего множества явным образом, он говорит о "принципе Кондорсе-Смита", применение которого эквивалентно выбору только тех альтернатив, которые принадлежат минимальному доминирующему множеству.
Сравнительный анализ основных решений, строящихся с помощью отношения мажоритарного доминирования
Доказательство: По построению Vj i MD flMD ) и uMD(i)=A, следовательно Vx (xeD = Зі: xeMD ). Если DnMD(i) 0, то DIDMD(J). Предположим обратное: DDMD(l) 0 & MD(l)\D 0. Поскольку D есть доминирующее множество Vx, у (xeDDMD(i), yeMD YD = xjiy). По определению MD(i) Vx, у (XGDHMD , ye(A\uMD(j))\MD(j), l j i-l = xjiy). Следовательно, DflMD не является доминирующим множеством в A\uMD(j), l j i-l. MD(i)\D#0 = DflMD czMD (лемма 2.1), следовательно, MD(1) не является минимальным доминирующим множеством в A\uMDw, l j i-l. Мы пришли к противоречию. Следовательно, D должно быть прямой суммой некоторого числа множеств MD .
По построению Vx, у: xeMD(i), yeMD(k) при k i имеет место xjiy. Следовательно,, если MD(i) есть минимальное доминирующе множество с наибольшим порядком из числа тех, что входят в D, то все MDQ порядка-j: l j i-l тоже должны быть подмножествами D. В противном случае D не было бы доминирующим множеством. Согласно леммам 2.1, 2.2 и 2.3 множество всех доминирующих множеств в А для любого [І может быть представлено как последовательность некоторого числа s множеств D(j), l i s, строго вложенных друг в друга: MDcD(2)C.. . zD(j.i)C=D(oc:.. .cD(s)=A, D(i)=MD+MD(2)+.. .+MD0_i)+MD0)+.. .+MD(i), D(i)\D(1.1)=MD(i). По построению минимальные доминирующие множества различных порядков не пересекаются, а объединение всех таких множеств совпадает с А. Следовательно, любая альтернатива из А принадлежит к одному и только одному множеству MD(i). Таким образом, иерархию доминирующих множеств можно рассматривать как макроструктуру множества А, в которой все элементы (то есть альтернативы) распределены по "вертикально" уПОрЯДОЧеННЫМ УРОВНЯМ (MD(i)}. Еще Шварц [69] установил, что объединение минимальных недоминируемых множеств всегда является подмножеством минимального доминирующего множества, MUczMD. Очевидно, что ядро Сг всегда есть подмножество MU, CrcMU, так как любое множество {х}, где хєСг, по определению ядра есть минимальное недоминируемое множество. Из CnzMU и MUeMD следует CrcMD. Незапертое множество UT всегда непусто и вложено между сильным и слабым верхними циклами, MUczUTczMD [22].
Следствием вложений MUcUT и CrcMU является вложение CrczUT. Из определений следует, что любое доминирующее множество является также недоминируемым. Т.о. из леммы 2.2 следует непустота MU, откуда следует непустота UT. В турнирах понятия доминирующего и недоминируемого множеств совпадают (в этом случае данное множество называют просто верхним циклом). Следовательно, в турнирах незапертое множество совпадает с минимальным доминирующим множеством [22]. О версиях непокрытого множества можно сказать следующее. Очевидно, что UCIV=UCnuUCin, UCtUCncUCIV; UCtUCnIcUCIV и UCIvcUCv. Множества UC и UC не связаны отношением вложения, в чем можно непосредственно убедиться на следующем примере: Так как любая недоминируемая альтернатива по определению не покрыта никакой другой, то ядро всегда является подмножеством непокрытого множества, CrcUC. Вложение может быть строгим, CrcUC, например, А={а, Ь, с, d}, ц={(а, b), (Ь, с), (с, d), (d, b)}, Cr={a}, исЦа, с, d}. Вложение UCczMD справедливо для всех версий отношения покрытия, тогда как MU и UC в общем случае не связаны отношением вложения: в турнирах всегда UCcMU=MD, но орграф, изображенный на рис. 1, представляет случай, когда MU={x, у, z} строго вложено в UC-{c, х, у, z}, MUcUC1. Этот пример также служит доказательством того, что множества UC11, UC и, UC и UC в общем случае не связаны отношением вложения с незапертым множеством UT: в турнирах UCn=UCin=UCIV=UCvcUT=MD, тогда как в данном случае UTcUC11, UTczUC111, UTcUCIV и UTcUCv, поскольку UC4jT={c, х, у, z}; UCn={b, с, x, у, z}; UCUI={a, с, x, у, z}; UCIV=UCV=A. Согласно первой версии определения отношения покрытия UC1 всегда является подмножеством UT, UCtUT.
К-устойчивые множества
По аналогии с альтернативами множество альтернатив X будет называться обобщенно-устойчивым множеством, если любая альтернатива, не принадлежащая X, достижима из какой-либо альтернативы, принадлежащей X, в противном случае множество X считается неустойчивым. Альтернатива у, не принадлежащая X, достижима их X за к шагов, если существует путь длиной в к шагов до у от какой-либо х из X. Так как все альтернативы достижимы из альтернатив, принадлежащих MD, но альтернативы из MD недостижимы из альтернатив, MD не принадлежащих, то любое множество X, имеющее непустое пересечение с MD, является обобщенно-устойчивым, в противном случае оно неустойчиво.
В терминах 1(х, у), X обобщенно-устойчиво, если VyeA\X ЭхеХ: 1(х, у) оо. Аналогично, функция 1(Х, у)=тіпхєХ1(х, у) при уєА\Х будет называться функцией наименьшего расстояния от множества X до альтернативы у. Значение 1(Х, у) полагается равным сю, если у недостижима ни из одной альтернативы из X, и 1(Х, у)=0, если уєХ.
Соответственно, 1тах(Х)= тахуєА1(Х, у). Если lmax(X)=k oo, то Vy ЗхеХ: 1(х, у) к & ЗуєА\Х: VxeX 1(х, у) к. Значение функции 1тах(Х) есть порядок устойчивости множества альтернатив X. Если порядок устойчивости множества альтернатив X равен к, то X будет называться к-устойчивым множеством. к-устойчивое множество является минимальным к-устойчивым множеством, если ни одно его подмножество (коме самого множества) не является к-устойчивым.
Пусть SS(k) обозначает класс альтернатив, каждая из которых принадлежит к какому-либо минимальному k-устойчивому множеству и не принадлежит ни к какому минимальному устойчивому множеству порядка меньше к. По построению эти классы не пересекаются, SS(i)nSS(j)=0 при Щ.
Наконец, пусть S(k) обозначает объединение всех минимальных обобщенно-устойчивых множеств, из которых можно достичь любой альтернативы, не принадлежащей данному множеству, за не более чем к шагов. Очевидно, множество S(k) есть прямая сумма классов устойчивых множеств порядка к и меньше, S(k)=SS(i)+SS(2)+.. .+SS(k
Из леммы 2.5 следует, что к-устойчивое множество порядка к=1 эквивалентно слабоустойчивому множеству. Следовательно, S(i) совпадает с объединением минимальных слабоустойчивых множеств MWS, S(iy=MWS.
Между множествами, введенными с помощью понятия устойчивости, существует связь, аналогичная связи, установленной для UC и MWS теоремой 2.1. Эта связь определяется теоремой 3.2. Теорема 3.2 1) P(2)cS(i)CP(3) (то есть UCcMWScUCp); Зц: P(2)cS0)cP(3); 2) Vk l P(k)cS(k) =P(k+2).
Доказательство: 1) P(2)=UCcMWS=S(i)cUCp=P(3) есть утверждение следствия теоремы 2.1. Пример на рис. 5 (см. ниже) доказывает, что Зц: P(2)cS(i)dP(3). 2) Предположим, альтернатива х k-устойчива, xeSP(k). Всегда существует минимальное к-устойчивое множество В, состоящее из одной альтернативы - х, В={х}. Следовательно, если х принадлежит P(k)=SP(2)+...+SP(k), то она также должна принадлежать S(kf=SS(i)+SS(2)+...+SS(k), из чего следует P(k)CS(k) и xeSP(k) = xeSS(i), i k.
Предположим, х принадлежит некоторому минимальному к-устойчивому множеству В, к 1. Поскольку В k-устойчиво, то всегда возможно достичь любой альтернативы, не принадлежащей В, от некоторой альтернативы из В за не более чем к шагов.
Если все альтернативы в В\{х} доминируемы альтернативой х, то из х можно достичь любой альтернативы в В за 1 шаг. Следовательно, из х можно достичь любой альтернативы за не более чем к+1 шаг, т. е. хєР(к+і), из чего Следует ХЄР(к+2).
Предположим, в В есть альтернатива у, доминирующая над х, ЗуєВ: уц,х. Так как В минимально, то В\{х} не является k-устойчивым. Из этого следует, что есть альтернатива z, не принадлежащая В\{х}, не достижимая из какой-либо альтернативы, принадлежащей В\{х} (включая у), за менее чем к+1 шаг. Альтернатива z доминирует над всеми альтернативами в В\{х}, следовательно, z x, поскольку по предположению в В\{х} существует альтернатива у, доминирующая над х. Альтернатива z достижима из х за не менее чем к шагов, в противном случае существовал бы путь от у до z через х длиной, меньшей к+1. Но поскольку В - это k-устойчивое множество, в В должна быть альтернатива, из которой z достижима не более чем за к шагов. Так как такой альтернативой не может быть ни одна альтернатива из В\{х}, ей должна быть х. Следовательно, z достижима из х ровно за к шагов. Пусть х—»zi—»Z2— ...—»zk_ і—»z - путь длины к от х до z. Вторая альтернатива в последовательности zi должна доминировать над у: Zijjy, в противном случае существовал бы путь у— zi- z2— ...— Zk-i z от у до z длины к, меньшей к+1. xjazi & Z\\iy & yjix = у достижима из х за 2 шага. Таким образом, любая альтернатива в В\{х} либо доминируема х, либо достижима из х за 2 шага. Поскольку В к-устойчиво, любая альтернатива в В достижима из х за не более чем к+2 шага, т. е. хєР(к+2). Таким образом, xeS(k) = xeP(k+2), из чего следует S(K)cP(k+2).n
Отношения ц, т и и. Победитель Кондорсе и ядро
Рассмотрим задачу коллективного выбора. По определению отношение мажоритарного доминирования \х и отношение равенства голосов т иррефлексивны, то есть, (i, і)ец, (і, i)gx для любой альтернативы і из А. Обозначим и отношение, являющееся объединением отношений д,, т и s: u=iuxus. Из определений (і, т и є следует, что и полно и рефлексивно, а также, что имеют место равенства р.=тг(и) И тиє=а(и). Если отношение ц - турнир, то, очевидно, циє=и. Обозначим М=[Шу] матрицу, представляющую отношение ц: ту=1 если альтернатива, номер которой равен номеру строки (то есть, альтернатива і), доминирует над альтернативой, номер которой равен номеру столбца (то есть, над альтернативой j), и ггіу=0 если альтернатива і доминируема альтернативой j или находится с ней в отношении равенства голосов. T=[ty] и U=[Uy] будут, соответственно, обозначать матрицы, представляющие отношения т и и. Очевидно, что M=P(U) и T+E=S(U), следовательно, согласно лемме 4.1 имеют место следующие равенства: U=M+T+E=M?, M+Mtr+E=T, M+Mtr+T+E=I. Если булева матрица R есть сумма каких-то матриц X и Y, то есть, если R=X+Y, то гц=1 = Ху=1 v Уц=1. Пусть R=M+E. Если гу=1 для любого j: j i, тогда альтернатива і есть победитель Кондорсе. Следовательно, cw=(M + E)-a будет характеристическим вектором множества победителей Кондорсе. k=l равен нулю тогда и только тогда, когда существует, по крайней мере, одна альтернатива к, такая, что альтернатива і доминирует над альтернативой k, а альтернатива к доминирует над альтернативой j. То есть, г О тогда и только тогда, когда существует ji-путь в два шага от і до j: ід.к & kpj. Поскольку мы полагаем, что все векторы и матрицы являются булевыми, то ги—1 тогда и только тогда, когда существует ц-путь в два шага от і до j, и гу=0 если такого пути не существует. Соответственно, если R=M, то гу=1 тогда и только тогда. когда существует путь в два шага от і до j, в котором первый шаг есть ц-шаг ijik, а второй шаг есть х-шаг kxj. Иными словами, гу=1 о Зк, кєА: ijak & kxj, в противном случае Гу=0. Аналогично, если R=T-M, то гу=1 = Зк, кєА: ітк & kuj, и если R=T, то Гу=1 Зк, кє А: ітк & kxj, в противном случае Гу—0. Так как для общего случая хФ0 было предложено пять версий определения отношения покрытия а, то обозначим их а1, а11, а111, а и а , соответственно. Поскольку , во всех версиях отношение покрытия асимметрично, то только непокрытые альтернативы являются максимальными элементами отношения покрытия а, то есть, UC HVlAXCa,1), UCIr=MAX(an), иСш=МАХ(аш), UCIV=MAX(aIV) и UCv=MAX(av). Построим матрицы, представляющие отношения a1, a", a111, aIV и av. Пусть Q=JVT+M+T+E. Если Яу=1, то имеет место либо i=j, либо ixj, либо iaj, либо 3k: ifik & kij. Следовательно, если qj,=l, то альтернатива і не покрыта альтернативой j согласно первой версии определения отношения покрытия, то есть, (j, і)0a1. Если существует альтернатива], такая, что qij=0, то не имеет п места ни i=j, ни ixj, ни ijjj, из чего следует, что j ii. Также ]mlk -mk]=0 = (mkj=l k=I = Шік=0) = (Vk (kuj = (kui v kxi))). Следовательно, если qij=0, то альтернатива і покрыта альтернативой j согласно первой версии определения отношения покрытия, то есть, (j, і) є а1. Утверждение (qij=l = (j, i)ea! и qij=0 = (j, і)єа ) эквивалентно тому, что Q = (М М + М + Т + Е)"" =R есть матрица, представляющая отношение а1. Аналогичные рассуждения приводят нас к следующему заключению: (М-Т + М-М + М + Т + Е) , (Т-М + М-М + М + Т + Е)", (Т-М + М-Т + М-М + М + Т + Е) и (Т-Т + Т-М + М-Т + М-М + М + Т + Е) суть матрицы, представляющие отношения a", a111, aIV и av, соответственно. Поскольку во всех пяти версиях отношение покрытия асимметрично, то, согласно лемме 4.2, для характеристических векторов ис1, ис11, исш, ucIV и ucv непокрытых множеств UCr, UC11, UC111, UCIV и UCV получаются следующие формулы:
