автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Концепции решений в задаче коллективного выбора

На правах рукописи

Субочев Андрей Николаевич

КОНЦЕПЦИИ РЕШЕНИЙ В ЗАДАЧЕ КОЛЛЕКТИВНОГО ВЫБОРА

Специальность 05.13.18 - "Математическое моделирование, численные методы и комплексы

программ"

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2009

003487715

Работа выполнена в Государственном образовательном бюджетном учреждении высшего профессионального образования «Государственный университет - Высшая школа экономики» при частичной финансовой поддержке Научного фонда ГУ-ВШЭ (грант №08-040008), Российского фонда фундаментальных исследований (совместный российско-турецкий исследовательский проект, грант №09-01-91224-СТ_а) и Лаборатории методов выбора и анализа решений Центра фундаментальных исследований ГУ-ВШЭ.

доктор технических наук, Алескеров Фуад Тагиевич

доктор физико-математических наук, профессор Васин Александр Алексеевич доктор физико-математических наук Чеботарев Павел Юрьевич Федеральное государственное образовательное учреждение высшего профессионального образования

"Санкт-Петербургский государственный университет"

200_Э^г. вЛ-ОСХасов на заседании диссертационного совета Д 212.048.09 при Государственном университете - Высшей школе экономики по адресу: ]05187, г. Москва, ул. Кирпичная, д. 33/5^ Сл. 2. О6.

С диссертацией можно ознакомиться в библиотеке Государственного университета - Высшей школы экономики по адресу: 101990, г. Москва, ул. Мясницкая, д. 20.

Автореферат разослан // 200 9 г.

Ученый секретарь диссертационного совета д.т.н., доцент „

Научный руководитель: Официальные оппоненты:

Ведущая организация:

Защита состоится 2

В.А.Фомичев

I. ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

возрождается. В частности, совсем недавно (в 2007 г.) были предложены новые с-концепции решений - незахваченное и незапертое множества. Практическая применимость требует и стимулирует дальнейшее теоретическое исследование данных моделей, чему и посвящена данная работа.

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

1. Устанавливаются взаимные соотношения между этими множествами.

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

3. Устанавливается соотношение этих обобщений с другими решениями.

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

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

Научная новизна. В ходе решения поставленных задач получены следующие новые результаты:

1. Сформулирован критерий, с помощью которого проверяется принадлежность любой альтернативы минимальному слабоустойчивому

4'

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

2. Построены обобщения минимального доминирующего множества, и с их помощью выяснено, как устроена система доминирующих множеств.

3. Установлены новые соотношения между множествами-решениями.

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

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

5. Предложены два новых определения слабой устойчивости множеств и, соответственно, две новых версии такого решения, как объединение минимальных слабоустойчивых множеств. Предложены пять новых версий непокрытого множества.

6. Посредством представления отношения мажоритарного доминирования и отношения равенства голосов в виде булевых матриц построено представление соответствующих множеств-решений в виде булевых векторов, значения которых определяются как результат последовательности арифметических операций над данными матрицами. В таком виде представлены почти все рассмотренные концепции решений (победитель Кондорсе, ядро, десять версий непокрытого множества, две из трех версий минимального слабоустойчивого множества, незахваченное множество, незапертое множество, минимальное недоминируемое множество и минимальное доминирующее множество) и их обобщения (классы к-устойчивых альтернатив и к-устойчивых множеств).

5

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

Теоретическая и практическая значимость. Теоретическая ценность работы состоит в том, что выполнен исчерпывающий анализ и дано последовательное и единообразное описание известных множеств-решений. При этом описать удалось практически все известные решения, строящиеся с помощью отношения мажоритарного доминирования, (кроме двух). Используемое описание также позволило предложить новые версии концепций решений, ранее в литературе не рассматривавшиеся. Результаты работы использовались при обновлении программы учебной дисциплины "Методы анализа политических процессов", читаемой студентам 2 курса бакалавриата-факультета прикладной политологии Государственного университета - Высшей школы экономики, и учебной дисциплины "Теория коллективного выбора", читаемой студентам 4 курса бакалавриата отделения прикладной математики и информатики факультета бизнес-информатики Государственного университета - Высшей школы экономики.

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

Апробация работы и публикации. Основные положения и полученные результаты диссертационной работы прошли апробацию на следующих научных конференциях и семинарах:

1. IX Международная научная конференция "Модернизация экономики и глобализация", ГУ-ВШЭ, Москва, 1-3 апреля 2008 г., доклад "Концепции , стабильных множеств альтернатив - равновесных решений игр, связанных с голосованием";

2. Общемосковский научный семинар "Математические методы анализа решений в экономике, бизнесе и политике" (научные руководители д.т.н. Ф.Т.

Алескеров, д.т.н. В.В. Подиновский), Москва, 16 апреля 2008 г., доклад "Концепции стабильных множеств альтернатив - равновесных решений игр, связанных с голосованием";

3. Общемосковский'научный семинар "Экспертные оценки и анализ данных" (научный руководитель д.т.н. Ф.Т. Алескеров), Институт проблем управления им. Трапезникова РАН, Москва, 23 апреля 2008 г., доклад "Концепции решений и их свойства";

4. Научный семинар "Математическая экономика" (научный руководитель академик РАН В.М. Полтерович), Центральный экономико-математический институт РАН, Москва, 28 октября 2008г., доклад "Множества-решения задачи коллективного выбора: сравнительный анализ";

5. Научный семинар "Теория управления организационными системами" (научный руководитель член-корреспондент РАН д.т.н. Д. А Новиков), Институт проблем управления им. Трапезникова РАН, Москва, 13 ноября 2008 г., доклад "Доминирующее, слабоустойчивое и непокрытое множества: свойства и обобщения";

6. Научный семинар отдела "Математическое моделирование экономических систем" Вычислительного центра РАН (научный руководитель академик РАН А.А. Петров), Москва, 19 ноября 2008 г., доклад "Доминирующее, слабоустойчивое и непокрытое множества: свойства и обобщения";

7. IV Международная конференция по проблемам управления, Институт проблем управления им. Трапезникова РАН, Москва, 26-30 января 2009 г., доклад "Доминирующее, слабоустойчивое и непокрытое множества: свойства и обобщения";

8. Научный семинар лаборатории теории игр и принятия решения Санкт-петербургского экономико-математического института РАН (научный руководитель д.ф.-м.н. Е.Б. Яновская, Санкт-Петербург), 27 мая 2009 г., доклад "Концепции решений задачи коллективного выбора";

9. Научный семинар кафедры теории управления факультета прикладной математики - процессов управления Санкт-Петербургского государственного

7

университета (научный руководитель д.ф.-м.н. В.Д. Ногин), Петергоф, 28 мая 2009 г., доклад "Концепции решений в задаче коллективного выбора. Доминирующее, слабоустойчивое и непокрытое множества";

10. Международная конференция ADRES (Association pour le Développement de la Recherche en Economie et Statistiques) в честь Мориса Салля, университет г. Кан (University of Caen), Кан, Франция, 11 июня 2009 г., доклад "Stable Solutions on Majority Relation", соавтор - Ф.Т. Алескеров;

11. Международная конференция 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", соавтор - Ф.Т. Алескеров;

12. Публичная лекция в университете Bilgi, Стамбул, Турция, 5 ноября 2009г. Тема лекции "Solutions on Majority Preference Relation";

13. Научный семинар кафедры алгебры механико-математического факультета Московского государственного университета, Москва, 17 ноября 2009 г., доклад "Устойчивые решения в задаче коллективного выбора и их матрично-векторное представление", соавтор - Ф.Т. Алескеров;

Результаты исследования также опубликованы в 5 работах, список, которых приводится в конце автореферата.

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения и списка литературы, включающего 72 наименований. Основная часть работы изложена на 95 страницах, содержит 7 рисунков и 4 таблицы и 1 приложение.

II. КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

Первая глава диссертации содержит постановку задачи, определения и ? обозначения основных понятий и концепций, историю их возникновения и обзор состояния исследований в данной области. Поскольку отправной точкой исследования является то обстоятельство, что ядро в общем случае может быть пусто, основное внимание в обзоре уделяется работам конца 70-х - начала 80-х гг. прошлого века, где и были введены основные решения, которые предлагалось использовать вместо ядра.

В разделе 1.1 строится математическая модель ситуации коллективного выбора, определяются отношение мажоритарного доминирования ц, моделирующее предпочтения коллектива, и отношение равенства голосов т. Отношение мажоритарного доминирования есть бинарное отношение /д на множестве альтернатив А, цсАхА, строящееся следующим образом: хцу тогда и только тогда, когда альтернатива х является (строго) более предпочтительной чем у для большинства (каким угодно образом определенного) субъектов у процесса принятия коллективных решений. Показывается, как отношение может быть представлено ориентированным графом. Вводятся понятия шага, пути, нижнего контура L(x) (множества альтернатив, доминируемых альтернативой х), верхнего контура D(x) (множества альтернатив, доминирующих над х) и горизонта Н(х) (множества альтернатив, находящихся с х в отношении равенства голосов). Также вводится понятие турнира - важного частного случая, когда отношение мажоритарного доминирования является : полным, то есть когда для любой пары альтернатив можно сказать, какая из них более предпочтительна для большинства.

В разделе 1.2 даются определения таких решений как победитель

Кондорсе CW (альтернатива, доминирующая над всеми другими при парном

9

сравнении), ядро Сг (множество недоминируемых альтернатив, то есть множество максимальных элементов отношения - мажоритарного доминирования), доминирующее множество Б (множество, в котором любая принадлежащая ему альтернатива доминирует над любой не принадлежащей ему альтернативой, концепция введена Б.Уордом), минимальное доминирующее множество МО (доминирующее множество, ни одно собственное подмножество которого не является доминирующим, концепция введена Дж.Смитом, Н.Миллером, Т.Шварцем), недоминируемое множество и (множество, в котором любая принадлежащая ему альтернатива недоминируема никакой не принадлежащей ему альтернативой, концепция введена Б.Уордом), минимальное недоминируемое множество МП (концепция введена Т.Шварцем). ° Вводится запирающее отношение у (альтернатива а запирает альтернативу Ь, если а доминирует над Ь, и не существует пути от Ь до а) и такое решение как незапертое множество ЦТ (множество максимальных элементов запирающего отношения, концепция введена Дж.Дугганом). Также в этом разделе строятся обобщения минимального доминирующего множества - минимальные доминирующие множества высших порядков МО0).

В разделе 1.3 приводятся пять версий определения отношения покрытия а. Например, третья версия определения - альтернатива а покрывает альтернативу Ь, если ацЬ и Б(а)сО(Ь). Соответственно, вводится пять версий такого решения как непокрытое множество иС (множество максимальных элементов отношения покрытия, концепция введена Н.Миллером и П.Фишберном). В этом разделе также определяется отношение захвата |3 (в турнире альтернатива а захватывает альтернативу Ь, если ац.Ь, и не существует пути от Ь до а длины ¡' менее четырех шагов). Вводится незахваченное множество иСр (множество максимальных элементов отношения захвата, концепция введена Дж.Дугганом). Обсуждаются история введения данных концепций и их интерпретация.

В разделе 1.4 вводится понятие слабоустойчивого множества (оно обладает следующим свойством: если х принадлежит WS, и какая-то

'■У

альтернатива у, не принадлежащая доминирует над х, то в обязательно найдется альтернатива г, доминирующая над у, концепция введена Ф.Алескеровым и Е.Курбановым). Определяется такое решение как минимальное слабоустойчивое множество (слабоустойчивое множество, ни одно собственное подмножество которого не является слабоустойчивым множеством).

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

Связи между доминирующими и минимальными доминирующими множествами разных порядков устанавливается Леммами 2.1,2.2 и 2.3.

Лемма 2.1. Если О] и Бг - доминирующие множества, то имеет место либо 0,сБ2, либо ОгсБ].

Лемма 2.2. Минимальное доминирующее множество единственно и всегда непусто.

Лемма 2.3. Если Б - доминирующее множество, тогда Б есть прямая сумма некоторого числа 1 минимальных доминирующих множеств первых 1 порядков (начиная с первого и заканчивая ьым, без пропусков),

В=МВ+МО(2)+.. .+МВ0.1)+МВЦ)+.. ,+МЕ>(0.

Согласно Леммам 2.1, 2.2 и 2.3 множество всех доминирующих множеств в А для любого ¡а может быть представлено как последовательность некоторого числа б множеств Бщ, 1<1<з, строго вложенных друг в друга:

МБСБ(2)С.. .СБ(М)сВ0)С. ..С1Э(5)=А,

В(])=МО+МБ(2)+.. .+МВ(Н)+МБШ+.. .+МО(0,О(0\В(М)=МБ(0.

11

По построению минимальные доминирующие множества различных > порядков не пересекаются, а объединение всех таких множеств совпадает с А. Следовательно, любая альтернатива из А принадлежит к одному и только одному множеству МОд. Таким образом, иерархию доминирующих множеств можно рассматривать как макроструктуру множества А, в которой все элементы (то есть альтернативы) распределены по "вертикально" упорядоченным уровням {МБ^}.

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

Теорема 2.1. Если ц является турниром, то альтернатива х принадлежит объединению минимальных слабоустойчивых множеств М\У8 тогда и только тогда, когда 1) либо сама х - непокрыта, 2) либо какая-то из альтернатив, принадлежащих нижнему контуру х, непокрыта.

С помощью этого критерия устанавливается, что непокрытое множество является подмножеством объединения минимальных слабоустойчивых множеств. Попутно предлагается новое определение слабой устойчивости множеств (множество В слабоустойчиво тогда и только тогда, когда существует путь в один шаг от какой-либо альтернативы из В до любой альтернативы, не принадлежащей В), которое совпадает со старым определением в случае, если ц - турнир, и, соответственно, предлагается новая версия такого решения, как объединение минимальных слабоустойчивых множеств- ШУБ11. Теорема 2.1 обобщается на случай произвольного отношения ц.

Теорема 2.1а. Для отношения мажоритарного доминирования ц произвольного вида альтернатива х принадлежит объединению минимальных , слабоустойчивых множеств тогда и только тогда, когда 1) либо х

непокрыта согласно третьей версии определения отношения покрытия, 2) либо

какая-то из альтернатив, принадлежащих нижнему контуру х, непокрыта согласно третьей версии определения отношения покрытия.

Наконец, для всех рассматриваемых множеств-решений устанавливается наличие или отсутствие отношения вложения, как в общем случае, так и для турниров. Полученные результаты приводятся в таблицах 1 и 2.

Таблица 1. Соотношение множеств-решений. Общий случай-

ис1 ис11 ис ис UCV ЛШБ1 иср ми ит МБ

Сг с с с с с с с с с с с

ис1 с с с с п.п. с с п.п. с с

ис" п.п. с с п.п. п.п. с п.п. п.п. с

ис"1 с с п.п. £ с п.п. п.п. с

ис™ с п.п. п.п. с п.п. п.п. с

ису п.п. п.п. П.П. п.п. п.п. с

М\У8' п.п. с п.п. с е

М\У8" с п.п. п.п. с

иср п.п. п.п. е

ми с с

ит е

Таблица 2. Соотношение множеств-решений. Турниры.

ис1 ис11 ис111 ис'у ису MWS" иср ми ит МБ

Сг е с с с с с с с с с е

ис1 = = = = с с е с с с

ис" = = = с с с с с с

ис"1 = = с с с Е с с

ис* = с с с с с с

ису с с с. с е с

= с 5 с £

мws" с 5 с с

иср С с с

ми - =

ит =

В третьей главе рассматриваются турниры. Для турниров рассматривается понятие обобщенно-устойчивой альтернативы (введено Ф.Алескеровым) и вводится понятие обобщенно-устойчивого множества альтернатив. Альтернатива х называется обобщенно-устойчивой, если любая другая альтернатива в А достижима из х, в противном случае х называется неустойчивой. По аналогии с альтернативами множество альтернатив X называется обобщенно-устойчивым множеством, если любая альтернатива, не принадлежащая X, достижима из какой-либо альтернативы, принадлежащей X, в противном случае множество X считается неустойчивым.

Определенная данным образом устойчивость может быть интерпретирована динамически. Естественно рассматривать некоторую позицию (состояние системы), как более устойчивую, если ее "труднее" изменить. В играх, связанных с голосованием, под "системой" подразумевается объект коллективного управления. Альтернативами являются различные значения параметров или условий функционирования объекта, зависящие от решений управляющей группы. При этом под "состоянием системы" может пониматься как сама альтернатива, являющаяся status quo, то есть текущее значение параметров управления, так и некоторое множество альтернатив, к которому status quo принадлежит. Данное состояние системы тем "труднее" изменить, чем меньше усилий (шагов игры, раундов голосования) необходимо для того, чтобы вернуть систему назад в это состояние после того, как состояние системы было изменено в очередном раунде голосования.

Вводится понятие расстояния до альтернативы от альтернативы и от множества альтернатив. Устойчивые альтернативы и устойчивые множества различаются по степени своей устойчивости, которая измеряется расстоянием до самой далекой альтернативы от данной альтернативы или множества. Устойчивые альтернативы и минимальные устойчивые множества одного порядка устойчивости к образуют, соответственно, класс к-устойчивых альтернатив SP(k) и класс k-устойчивых множеств SS^j. Множества этих классов являются фильтрациями минимального доминирующего множества, то есть

14

образуют микроструктуру турнира. Их можно рассматривать как обобщения непокрытого множества и слабоустойчивого множества, поскольку класс 2-устойчивых альтернатив есть непокрытое множество, БР^иС, а класс 1-устойчивых множеств есть объединение минимальных слабоустойчивых множеств 88(к)=М\У8.

Доказывается теорема о непустоте классов к-устойчивых альтернатив.

Теорема 3.1 Если победитель Кондорсе отсутствует, то каждый класс устойчивых альтернатив порядка к меньшего либо равного максимальному н большего единицы непуст, 2<к<ш=тахх емЫФО, где к(х) - порядок

устойчивости альтернативы х.

Вводится множество Р(к) - множество тех альтернатив, от которых можно достичь любой альтернативы в А не более чем за к шагов. По определению Р^ есть прямая сумма всех классов устойчивых альтернатив порядка к и меньше, Р(к)=8Р(|)+8Р(2)+...+8Р(к). Согласно определению отношения захвата альтернатива х является незахваченной, если любая альтернатива в А достижима из х за не более чем три шага. Таким образом, Р(3) - это незахваченное множество ТЛСр, Р(з)=8Р(1)+8Р(2)+8Р(3)=иСр.

Следовательно, в минимальном доминирующем множестве МО возникает следующая система подмножеств:

1) Р(1)={С\У}=МВ; если Р(|)=0, то

2) Р(2)=иС#0, непокрытое множество;

3) Рр)=иСр, незахваченное множество;

4) Р(1)сР(2)СР(3)с=... сР(т.1)СР(т)=Ж>, т=таххеМ0к(х), причем все вложения строгие согласно Теореме 3.1.

Вводится множество 8(к) - объединение всех минимальных обобщенно-устойчивых множеств, из которых можно достичь любой альтернативы, не принадлежащей данному множеству, за не более чем к шагов. Очевидно, множество Б(к) есть прямая сумма классов устойчивых множеств порядка к и меньше, 8(к)=88(1)+88(2)+...+88(к)

Между множествами, введенными с помощью понятия устойчивости, устанавливается связь, аналогичная связи, установленной для иС и М^Л^Б Теоремой 2.1. Эта связь определяется Теоремой 3.2.

Теорема 3.2 1) Р(2)с8(1)сР(3) (то есть иСсМЧУБсиСр);

2)Ук:к>1Р(к)с8(к)сР(к+2). Следствие хеБРр) => хбЗБ^; хеБР^, к>2 => (хеББ^), или хеББ^), или хеББр;)) & хйБЗд, (¡>к) или (¡<к-2).

В качестве примеров рассмотрим следующие три турнира. А={а, Ь, V, V/, х, у, г};

ц,={(а, Ь), (а, \у), (а, х), (а, у), (а, г), (Ь, у), (Ь, х), (Ь, у), (Ь, г), (V, а), (V, w), (V, х), (V, г), (\у, Ь), (у/, х), (w, у), (х, у), (х, г), (у, V),

а

(у, г), (г, \у)} (рис. 5);

Рис. 1

Цг={(а, Ь), (а, V/), (а, х), (а, у), (а, г,), (Ъ, V), (Ь, х), (Ь, у), (Ь, г), (V, а), (V, \у), (у, х), (V, г), (w, Ь), (w, х), (\у, у), (х,

2

у), (х, г), (у, V), {г, \у), (г, у)} (рис. 6);

Рис.2

Из={(а, Ь), (а, \у), (а, х), (а, у), (а, г), (Ь, у), (Ь, х), (Ь, у), (Ь, г), (у, а), (у, х), (у, г), (\у, Ь), (\у, у), (w, х), (V/, у), (х, у), (х, г), (у, у), (г, \у), (г, у)} (рис. 7).

Рис.3

Для каждого орграфа распределение альтернатив по классам альтернатив {БР(к)} и классам множеств {ЗЭ^} показано в Таблице 3.

Таблица 3. Распределение альтернатив по классам альтернатив {БР(1л1 и классам множеств {ББ^) для орграфов, изображенных на рис. 1,2.3.

Рисунок 1 Рисунок 2 Рисунок 3

ЯР® ЭРсз) ®Р(2) 8Р(3) 8Р(4) БРр) вРр)

^О) а, Ь, V У, иг а, Ь, V у, \у 88(1) а, Ь, V, w У. 2

7. г ввр,

X X вво) X

Эти примеры демонстрируют, что реализуются все три теоретически возможных варианта принадлежности к-устойчивой альтернативы к определенному классу устойчивых множеств: хе(ББ(к.2> БР^), хе(ББ(ы)> ЗР^), хе(ББ(к), БРщ). Следовательно, ситуацию Р(2)С1Б(1) нельзя обобщить на все множества (Б^)}, {Рад} и сделать утверждение Теоремы 3.2 более сильным. Очевидно, вложение Р(2)С:Б(1) (иСсМ\\'Б) - это всего лишь "граничный эффект".

Важно отметить, что РщсБщсР^+г) не означает, что имеет место либо Р(к)£5дасР(1С+1), либо Р(к+1)Е8(к)сР(к+2). Турнир (А, ц2) показывает, что возможны случаи, когда существуют пары альтернатив (х, у), одна из которых (х) принадлежит классу множеств более устойчивых и классу альтернатив менее устойчивых по сравнению с другой (у), хе(ББ(|с-2), БР^), уб(ББ(Ы)> БР(Ы))-Следовательно, несмотря на то, что можно сравнивать альтернативы по устойчивости, используя классы устойчивых альтернатив {БР^} или классы устойчивых множеств {ББщ}, эти системы классов не порождают совместного порядка. Можно считать альтернативу х более устойчивой, чем альтернатива у, когда хе(ББ(к), БРщ), уе(ББ(т), БР(П)), к<т, 1<п & (к<т или 1<п), но нельзя сравнить альтернативы хе(ББ(к.2), БР(к)) и уе(ББ(к.1), БР(Ы)).

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

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

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

В разделе 4.1 даются основные определения понятий, связанных с матрично-векторным представление множеств и отношений. Матрица К=[гц] представляет отношение р на А, если V jеА гу=1 <=> (ц ])ер и гу=0 о 0, .¡)£р. Произвольное множество альтернатив В, ВсА, может быть представлено с помощью характеристического п-компонентного (п=|А|) вектора Ь=[Ь;], определяемого следующим образом: V 1еА Ьр=1 О ¡еВ и ЬрО о 1йВ. В данном разделе устанавливается основное соотношение, используемое в дальнейшем для получения матрично-векторных представлений решений, - формула вектора множества максимальных элементов МАХ(р) данного отношения р.

Лемма 4.2. 1) Если матрица И является представлением отношения р, то вектор шах(р) множества максимальных элементов этого отношения МАХ(р) выражается формулой шах(р)=(Н + Н1г)-а; 2) если р полно, то тах(р)=(Я + Е)-а; 3) если р асимметрично, то шах(р)=К1г а. Здесь Е - это единичная матрица.

Раздел 4.2 посвящен рассмотрению свойств матричных представлений М, Т и и отношений ц, т и и=цити£, где е - это отношение идентичности, репрезентируемое матрицей Е.

В разделе 4.2 дается матрично-векторное представление таких решений, как победитель Кондорсе и ядро. По определению Сг=МАХ(р). Так как р - это асимметричная часть отношения и, то согласно Лемме 4.2 и Следствию из нее Сг=МАХ(ц)=МАХ(и) и сг=тах(ц)=тах(и)=М'г • а =ТПа=(М + Т + Е) • а.

Если булева матрица есть сумма каких-то матриц X и У, то есть, если 11=Х+У, то гу=1 о Ху=1 V уу=1. Пусть К=М+Е. Если Гу=1 для любого], тогда альтернатива 1 есть победитель Кондорсе. Следовательно, с\у=(М + Е)-а будет характеристическим вектором множества победителей Кондорсе.

В разделе 4.3 дается представление всех версий непокрытого множества

п

иС. Если взять произведение матриц 11=М-М, то элемент Гу=^]т,к -тк; не будет

к-1

равен нулю тогда и только тогда, когда существует, по крайней мере, одна альтернатива к, такая, что альтернатива 1 доминирует над альтернативой к, а альтернатива к доминирует над альтернативой]. С помощью этого наблюдения можно построить матрицы, представляющие пять версий отношения покрытия аы (ЪМ-нУ). Поскольку во всех версиях отношение покрытия асимметрично, то только непокрытые альтернативы являются максимальными элементами отношения покрытия а, то есть, иСн=МАХ(ам) (Ы=1-ьУ). Таким образом, для вычисления исм (N=1-5-V) непокрытых множеств 1/Сы (N=14-V) можно использовать Лемму 4.2. Например, исш=тах(аш)=(Т-М + М-М + М + Т+Е)-а.

В разделе 4.4 дается матрично-векторное представление незахваченного множества иСр. Схема рассуждений аналогична тем, что используются в предыдущем разделе. В итоге иср=тах((3)= (М-и-М + и- М + М- и+и)-а.

В разделе 4.5 дается матрично-векторное представление минимального

доминирующего множества МБ, минимального недоминируемого множества

к

Ми и незапертого множества 1Л\ Рассмотрим матрицы М(к)=^м'+Е и

¡-1

к

и(к)=£1Г; Ш(к)у=1 тогда и только тогда, когда есть ц-путь от альтернативы 1 до

1-1

альтернативы 3, 3=^1, длины 1: 0<1<к, также т(к)н=1 для всех 1, 1<1<п. Следовательно, Мдо есть матрица, представляющая к-транзитивное замыкание отношения р, кк(ц). Соответственно, и^ - это матрица, представляющая кк(о). Т.к. А конечно, то существует минимальный ц-путь длины большей либо равной длине любого другого минимального ц-пути в А. Длина такого пути есть ц-диаметр множества А, (1(ц). Из определения кк(р) следует, что кк(ц)^к(]^)(ц) при к<с!(ц) и к{1((1)((1)=кк(ц)=к(ц) для любого к: к>с1(ц). Также должен существовать минимальный о-путь длины большей либо равной длине любого другого минимального ц-пути в А. Длина этого пути есть и-диаметр множества А, ё(и). Аналогично, кк(и)*к<|(и)(и) при к<с!(о) и к<](и)(и)=кк(и)=к(и) для всех к: к>с!(и). Поскольку М(к) и 11(к) представляют отношения кк(ц) и кк(о), то М^ц)) и и«1(и)) суть представления отношений к(ц) и к(и), соответственно. Также М№))*М№Н) & М№))=М№>+1) и Цдауги^и)-!) & И^г^^уцу

Для того чтобы вычислить минимальное доминирующее множество МБ и объединение минимальных недоминируемых множеств Ми, необходимо воспользоваться следующей теоремой: Ми=МАХ(к(ц)), МБ=МАХ(к(и)).

Т.к. Ми=МАХ(к(ц)), то р=к(ц), а К=М№, где Согласно Лемме 4.2

для вектора множества Ми получаем: ти=(М(1)) +М(^)-а.

Т.к. ЦТ=МАХ(у), то согласно Лемме 4.2 для вектора множества иТ получаем: и1=тах(7)=(М(а)+Т)-а. Значение <1=с1(ц) определяется из М^М^-о & М(а)=М(а+1).

Т.к. МО=МАХ(к(о)), то р=к(ц), а К=и№, где с!=с1(о). Согласно Лемме 4.2 для вектора множества МО получается формула: пк^и^а. Значение с!

определяется из условия и^и^.]) & и^^и^-ц).

В разделе 4.6 дается матрично-векторное представление второй версии минимального слабоустойчивого множества: т\У8П=(М+Е)- (и • М + и) • а.

Представление для первой версии этого решения получить не удалось.

В разделе 4.7 предлагаются новые версии непокрытого и слабоустойчивого множеств и вычисляются их вектора. В частности, вектор третьей версии минимального слабоустойчивого множества вычисляется по формуле тл¥8Ш=(М-и + и)-а+&а§((М+Т)-(М-и + Е)-М), где сИа§(К) обозначает вектор, составленный из диагональных элементов матрицы 1*.

В разделе 4.8 с помощью представлений новых версий решений, введенных в предыдущем разделе, были получены матрично-векторные представления классов к-устойчивых альтернатив и к-устойчивых множеств. Из определения классов БРщ, множеств Р(ц, а также пустоты отношения равенства голосов следует, что ¡еР(к) <=> ¡еМАХ(к^(у.)), то есть, Р(к)=МАХ(КкОО).

Согласно Лемме 4.2 для вектора множества Рдо получаем: Р(к)=(Мм+Е)-а = Мм-а. Т.к. как все матрицы - булевые, то имеет место

к к 1с ==—

равенство +Е=(М+Е) . Следовательно, М(к)=£м' +Е=и и Р(к)=ик а.

|>1 1-1

Обозначим 5р(к) вектор множества БРда. По определению Рм ¡еБРдо <=> ¡еР(к) & ¡йР(Ы)- Следовательно, 5р(к)рр(к)г р^+ р^, то есть,

«Р{к)= Р00 + Р(Ы) = Мм • а + М(ы) • а= ик • а + иы • а.

Введем обозначение и(к) для отношения кк(ц), и(ц= кк()д). Также обозначим щц асимметричную часть отношения кк(ц) и тод - симметричную часть этого отношения. Из определений следует, что о(1)=о, Ц(1>=Ц, т(1)=тиЕ. Будем рассматривать отношения и(к) и р(к) как новые версии отношений оиц.

Если множество В, ВсА, является к-устойчивым, то из к-устойчивого множества следует, что любая альтернатива не принадлежащая В, будет достижима из какой-то альтернативы принадлежащей В, за один и(к)-шаг, то есть, Ур ]еА\В => 31: ¡еВ & ю^. Если порядок устойчивости В выше чем к, то 3]: ]еА\В & VI: ¡еВ => (¡, ])ги(к). Следовательно, если В есть минимальное к-устойчивое множество по отношению ц, то оно также должно быть минимальным слабоустойчивым (согласно третьей версии определения)

множеством по отношению и^. Наоборот, если В есть минимальное слабоустойчивое (согласно третьей версии определения) множество по отношению и(к), то оно также должно быть минимальным устойчивым множеством по отношению ц порядка устойчивости не ниже к.

Обозначим 8в(к) и в(к) вектора классов к-устойчивых множеств ББ^ и из сумм 8(к)=88(1)+88(2)+...+88(1С), соответственно. Обозначим MWSш(U(k)) и т\У8Ш(0(к)) объединение минимальных слабоустойчивых (согласно третьей версии определения) множеств, вычисленное для отношения и(к) на А, и его вектор, соответственно. Тогда ¡еББ^ => ¡еМ\У8ш(и(|<)) и 1бМ\У8ш(и(к)) ==> ¡еББ^), х: х<к, т.е. 88(к)сМ\У5ш(о(к)) и М\У8ш(о(к))с8(к) => 5{к)=птзш(и(к))+з(Ы).

Поскольку класс 88(1) есть не что иное, как объединение минимальных слабоустойчивых множеств (по отношению ц), то для вычисления векторов в(к) мы получаем индуктивную формулу: 8(1)=88(1)=т\У8=(М+Е)-р(2)=и-и2 - а, 8(к)==8(к.1)+т\У8Ш(и(к))=8(к-1)+ (М • и + 0) • а +diag((M + Т) • (М • и + Е) • М), где и=М(к), М=(М*)+М,к)).

Т.к. согласно Теореме 3.2 имеет место Р(к)с8(цсгР(к+2)С:МО, то итерации должны остановиться между к=ш-2 и к=т, когда в^) станет равным пк^р^. Наконец, ¡е88(к) <=> Iе8(к) & ¡г8(ы) ^зз^пБ^-=з(к)| + 8^ , т.е. -ья^.,,.

В разделе 4.9 дается точная оценка сложности вычисления решений с помощью их матрично-векторных представлений.

Раздел 4.10 посвящен компьютерной реализации этих алгоритмов.

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

1П. ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

2. Построены обобщения минимального доминирующего множества, и с их помощью выяснено, как устроена система доминирующих множеств.

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

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

4. Введены пять новых версий непокрытого множества и две новые версии минимального слабоустойчивого множества.

5. Построено представление множеств-решений в виде булевых векторов, значения которых определяются как результат последовательности арифметических операций над булевыми матрицами, представляющими отношения. В таком виде представлены почти все рассмотренные решения (кроме и одной из трех версий минимального слабоустойчивого множества) и их обобщения (классы к-устойчивых альтернатив и к-устойчивых множеств).

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

IV. СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ Работы, опубликованные автором в ведущих рецензируемых научных журналах и журналах, рекомендованных ВАК Министерства образования и науки России:

1. Алескеров Ф.Т., Субочев А.Н. Об устойчивых решениях в ординальной задаче выбора II Доклады Академии Наук. 2009. Т. 426. №3. Стр. 318-320. 0,35 пл. (вклад автора 0,28 п.л.)

2. Субочев А.Н. Доминирующие, слабоустойчивые и непокрытые множества: свойства и обобщения // Автоматика и Телемеханика. 2010. №1. 1,00 п.л.

Другие работы, опубликованные автором по теме кандидатской диссертации

3. Subochev A. Dominant, Weakly Stable, Uncovered Sets: Properties and Extensions: Working paper WP7/2008/03. Moscow: SU - Higher School of Economics. 2008.1,90 п.л.

4. Субочев А.Н. Доминирующие, слабоустойчивые и непокрытые множества: свойства и обобщения // Труды IV Международной конференции по проблемам управления. М.: ИЛУ РАН. 2009. 0,65 п.л

5. Aleskerov F., Subochev A. Matrix-vector representation of various solution concepts. Working paper WP7/2009/03. Moscow: SU - Higher School of Economics. 2009.2,09 п.л. (вклад автора 1,67 п.л.)

Лицензия ЛР №020832 от 15 октября 1993 г. Подписано в печать 20 ноября 2009г. Формат 60x84/16 Бумага офсетная. Печать офсетная. Усл. печ. л. 1,0. Тираж 100 экз. Заказ № 304

Типография издательства ГУ-ВШЭ 125319, г. Москва, Кочновский пр-д, д.З

Аннотация

Введение

Глава 1. Постановка задачи коллективного выбора. Обзор концепций ее решений

1.1 Отношение мажоритарного доминирования и связанные с ним понятия

1.2 Доминирующее, недоминируемое и незапертое множества

1.3 Непокрытое и незахваченное множества

1.4 Слабоустойчивое множество

Глава 2. Сравнительный анализ основных решений, строящихся с помощью отношения мажоритарного доминирования

Глава 3. Концепции классов k-устойчивых альтернатив и к-устойчивых множеств

3.1 к-устойчивые альтернативы

3.2 к-устойчивые множества

Глава 4. Матрично-векторное представление решений и его компьютерная реализация

4.1 Матрично-векторное представление множеств и отношений: основные определения

4.2 Отношения ц, т и и. Победитель Кондорсе и ядро

4.3 Непокрытое множество

4.4 Незахваченное множество

4.5 Минимальное доминирующее, минимальное недоминируемое и незапертое множества

4.6 Минимальное слабоустойчивое множество

4.7 Новые версии непокрытого и слабоустойчивого множеств

4.8 Классы k-устойчивых альтернатив и к-устойчивых множеств

4.9 Оценка сложности вычислений решений с помощью формул их матрично-векторного представления

4.10 Компьютерная реализация вычислений решений с помощью формул их матрично-векторного представления

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

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

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

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

1. устанавливаются взаимные соотношения между этими множествами;

2. обобщаются концепции минимального доминирующего множества, непокрытого множества, минимального слабоустойчивого множества;

3. устанавливается соотношение этих обобщений с другими решениями;

4. строится матрично-векторное представление всех рассмотренных множеств-решений, определяющее алгоритм их вычисления.

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

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

Научная новизна. В ходе решения поставленных задач получены следующие новые результаты.

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

2. Построены обобщения минимального доминирующего множества, и с их помощью выяснено, как устроена система доминирующих множеств.

3. Установлены новые соотношения между множествами-решениями.

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

5. Предложены два новых определения слабой устойчивости множеств и, соответственно, две новых версии такого решения, как объединение минимальных слабоустойчивых множеств. Предложены пять новых версий непокрытого множества.

6. Посредством представления отношения мажоритарного • доминирования и отношения равенства голосов в виде булевых матриц построено представление соответствующих множеств-решений в виде булевых векторов, значения которых определяются как результат последовательности арифметических операций над данными матрицами. В таком виде представлены почти все рассмотренные концепции решений (победитель Кондорсе, ядро, десять версий непокрытого множества, две из трех версий минимального слабоустойчивого множества, незахваченное множество, незапертое множество, минимальное недоминируемое множество и минимальное доминирующее множество) и их; обобщения (классы k-устойчивых альтернатив и к-устойчивых множеств).

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

Теоретическая и практическая значимость. Теоретическая ценность работы состоит в том, что выполнен исчерпывающий анализ и дано последовательное и единообразное описание известных множеств-решений. При этом описать удалось практически все известные решения, строящиеся с помощью отношения мажоритарного доминирования, (кроме двух). Используемое описание также позволило предложить новые версии концепций решений, ранее в литературе не рассматривавшиеся. Результаты работы использовались при обновлении программы учебной дисциплины "Методы анализа политических процессов", читаемой студентам 2 курса бакалавриата факультета прикладной политологии Государственного университета - Высшей школы экономики, и учебной дисциплины "Теория коллективного выбора", читаемой студентам 4 курса бакалавриата отделения прикладной математики и информатики факультета бизнес-информатики Государственного университета - Высшей школы экономики.

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

Полнота изложения материалов диссертации в публикациях.

Результаты диссертации были изложены в следующих публикациях:

Работы, опубликованные в* ведущих рецензируемых научных журналах и журналах, рекомендованных ВАК Министерства образования и науки России:

1. Алескеров Ф.Т., Субочев А.Н. Об устойчивых решениях в ординальной задаче выбора // Доклады Академии Наук. 2009. Т. 426. №3. С. 318-320. 0,35 п.л. (вклад автора 0,28 п.л.)

2. Субочев А.Н. Доминирующие, слабоустойчивые и непокрытые множества: свойства и обобщения // Автоматика и Телемеханика. 2010. №1. 1,00 п.л.

Другие работы, опубликованные по теме диссертации:

3. Subochev A. Dominant, Weakly Stable, Uncovered Sets: Properties and Extensions. Working paper WP7/2008/03. Moscow: State University -Higher School of Economics. 2008. 1,90 п.л.

4. Субочев А.Н. Доминирующие, слабоустойчивые и непокрытые множества: свойства и обобщения // Труды IV Международной конференции по проблемам управления. М.: ИЛУ РАН, 2009. 0,65 п.л

5. Aleskerov F., Subochev A. Matrix-vector representation of various solution concepts. Working paper WP7/2009/03. Moscow: State University -Higher School of Economics, 2009. 2,09 п.л. (вклад автора 1,67 п.л.)

Апробация работы. Основные положения и полученные результаты диссертационной работы прошли апробацию на следующих научных конференциях и семинарах:

1. IX Международная научная конференция "Модернизация экономики и глобализация", ГУ-ВШЭ, Москва, 1-3 апреля 2008 г., доклад "Концепции стабильных множеств альтернатив - равновесных решений игр, связанных с голосованием";

2. Общемосковский научный семинар "Математические методы анализа решений в экономике, бизнесе и политике" (научные руководители д.т.н. Ф.Т. Алескеров, д.т.н. В.В. Подиновский), Москва, 16 апреля 2008 г., доклад "Концепции стабильных множеств альтернатив -равновесных решений игр, связанных с голосованием";

3. Общемосковский научный семинар "Экспертные оценки и анализ данных" (научный руководитель д.т.н. Ф.Т. Алескеров), Институт проблем управления им. Трапезникова РАН, Москва, 23 апреля 2008 г., доклад "Концепции решений и их свойства";

4. Научный семинар "Математическая экономика" (научный руководитель академик РАН В.М. Полтерович), Центральный экономико-математический институт РАН, Москва, 28 октября 2008г., доклад "Множества-решения задачи коллективного выбора: сравнительный анализ";

5. Научный семинар "Теория управления организационными системами" (научный руководитель член-корреспондент РАН д.т.н. Д. А Новиков), Институт проблем управления им. Трапезникова РАН, Москва, 13 ноября 2008 г., доклад "Доминирующее, слабоустойчивое и непокрытое множества: свойства и обобщения";

6. Научный семинар отдела "Математическое моделирование экономических систем" Вычислительного центра РАН (научный руководитель академик РАН А.А. Петров), Москва, 19 ноября 2008 г., доклад "Доминирующее, слабоустойчивое и непокрытое множества: свойства и обобщения";

7. IV Международная конференция по проблемам управления, Институт проблем управления им. Трапезникова РАН, Москва, 26-30 января 2009 г., доклад "Доминирующее, слабоустойчивое и непокрытое множества: свойства и обобщения";

8. Научный семинар лаборатории теории игр и принятия решений Санкт-петербургского экономико-математического института РАН (научный руководитель д.ф.-м.н. Е.Б. Яновская, Санкт-Петербург), 27 мая 2009 г., доклад "Концепции решений задачи коллективного выбора";

9. Научный межфакультетский семинар по экономико-математическим методам Санкт-Петербургского государственного университета (научные руководители д.ф.-м.н. В.Д. Ногин и д.ф.-м.н. А.В. Прасолов), Петергоф, 28 мая 2009 г., доклад "Концепции решений в задаче коллективного выбора. Доминирующее, слабоустойчивое и непокрытое множества"; •

10. Международная конференция ADRES (Association pour le Developpement de la Recherche en Economie et Statistiques) в честь Мориса Салля, университет г. Кан (University of Caen), Кан, Франция, 11 июня 2009 г., доклад "Stable Solutions on Majority Relation", соавтор - Ф.Т. Алескеров;

11. Международная конференция 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", соавтор - Ф.Т. Алескеров;

12. Публичная лекция в университете Bilgi, Стамбул, Турция, 5 ноября 2009г. Тема лекции "Solutions on Majority Preference Relation";

13. Научный семинар кафедры алгебры механико-математического факультета Московского государственного университета, Москва, 17 ноября 2009 г., доклад "Устойчивые решения в задаче коллективного выбора и их матрично-векторное представление", соавтор - Ф.Т. Алескеров;

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения и списка литературы, включающего 72 наименований. Основная часть работы изложена на 95 страницах, содержит 7 рисунков и 4 таблицы и 1 приложение.

Заключение

В теории рационального коллективного выбора одной из основных проблемой является пустота ядра в общем случае. Ядро бывает непустым так редко, что исследователю приходится либо 1) принимать довольно жесткие предположения относительно индивидуальных предпочтений участников для того, чтобы гарантировать его непустоту,12 либо 2) искать решение, которое могло бы как-то заменить ядро. В настоящей работе был выбран второй путь.

Несколько таких решений были рассмотрены в сравнительной перспективе: Cr, UC1, UC11, UC111, UCIV, UCV, MWS1, MWS11, UCp, MU, UT и MD. В таблице 3 и таблице 4 для всех пар всех этих множеств-решений указано наличие или отсутствие отношения вложения, соответственно, в общем случае и для турниров. Символ "с=" в ячейке означает, что множество R, соответствующее строке данной ячейки, всегда является подмножеством множества С, соответствующего столбцу ячейки, RcC. Обозначение "п.п." указывает на отсутствие отношения вложения между множествами R и С. Знак ' говорит, что множества R и С совпадают.

1. Айзерман М.А., Алескеров Ф.Т. Задача Эрроу в теории группового выбора (анализ проблемы) // Автоматика и телемеханика. 1983. № 9. С. 127-151.

2. Алескеров Ф.Т., Субочев А.Н. Об устойчивых решениях в ординальной задаче выбора // Доклады Академии Наук. 2009. Т. 426. №3. С. 318-320.

3. Субочев А.Н. Доминирующие, слабоустойчивые и непокрытые множества: свойства и обобщения // Автоматика и Телемеханика. 2010. №1. С. 130-143.

4. Субочев А.Н. Доминирующие, слабоустойчивые и непокрытые множества: свойства и обобщения // Труды IV Международной конференции по проблемам управления. М.: ИЛУ РАН, 2009.

5. Aizerman М., Aleskerov F. Voting operators in the space of choice functions // Mathematical Social Sciences. 1986. V. 11. № 3. P. 201-242.

6. Aleskerov F. Arrovian Aggregation Models. Dordercht: Kluwer Academic Publishers, 1999.

7. Aleskerov F. Voting models in Arrovian framework // Social Choice Theory reexamined / Eds. Arrow K., Sen A., Suzumura K. N.Y.: St. Martin Press, 1997. V. l.P. 47-67.

8. Aleskerov F., Kurbanov E. A Degree of Manipulability of Known Social Choice Procedures // Current Trends in Economics: Theory and Applications / Eds. Alkan A., Aliprantis Ch., Yannelis N. N.Y.: Springer-Verlag, 1999. P. 1327.

9. Aleskerov F., Subochev A. Matrix-vector representation of various solution concepts. Working paper WP7/2009/03. M.: State University Higher School of Economics, 2009.

10. Aleskerov F., Vol'skiy V. Choice of the Best Variants on Binary Relations and the Extrimizational Choice. Preprints of 10th World Congress on Automatic Control. Munich, 1987. V. 5. P. 234-239.

11. Arrow К. Social Choice and Individual Values. New Haven: Yale University Press, 1963. (1st ed. 1951).

12. Banks J. Sophisticated voting outcomes and agenda control // Social Choice and Welfare. 1985. V. 1. P. 295-306.

13. Banks J., Bordes G., Le Breton M. Covering relations, closest orderings and hamiltonian bypaths in tournaments // Social Choice and Welfare. 1991. V. 8. P. 355-363.

14. Bianco W., Jeliazkov I., Sened I. The uncovered set and the limits of legislative action // Political Analysis. 2004. V. 12(3). P. 256-276.

15. Bianco W., Lynch M., Miller G., Sened I. "A Theory Waiting to Be Discovered and Used": A Reanalysis of Canonical Experiments on Majority Rule Decision-Making // Journal of Politics. 2006. V. 68. Iss. 4. P. 838-851.

16. Black D. The theory of committees and elections. Cambridge: Cambridge University Press, 1958.

17. Brandt F., Fischer F., Harrenstein P., Mair M. A computational analysis of the tournament equilibrium set // Social Choice and Welfare. 2009. (on-line publication).

18. Coughlan P., Le Breton M. A social choice function implementable via backward induction with values in the ultimate uncovered set // Review of Economic Design. 1999. V. 4. P. 153-160.

19. Cox G. The Uncovered Set and the Core // American Journal of Political Science. 1987. V. 31(2). P. 408-422.

20. Deb R. On Schwart's Rule // Journal of Economic Theory. 1977. V. 16. P. 103110.

21. De Donder Ph. Majority voting solution concepts and redistributive taxation // Social Choice and Welfare. 2000. V. 17. P. 601-627.

22. Duggan J. A systematic approach to the construction of non-empty choice sets // Social Choice and Welfare. 2007. V. 28. P. 491-506.

23. Duggan J. Uncovered sets. Mimeo. 2006.

24. Dutta В. Covering sets and a New Condorcet Choice Correspondence // Journal of Economic Theory. 1988. V. 44. P. 63-80.

25. Dutta B. On the Tournament Equilibrium Set // Social Choice and Welfare. 1990. V. 7. P. 381-383.

26. Dutta В., Jackson M., Le Breton M. The Banks Set and the Uncovered Set in Budget Allocation Problems // Social Choice and Strategic Decisions. Essays in Honor of Jeffrey S. Banks. Studies in Choice and Welfare. Berlin-Heidelberg: Springer-Verlag, 2005.

27. Dutta В., Laslier J.-F. Comparison functions and choice correspondences // Social Choice and Welfare. 1999. V. 16. P. 513-532.

28. Epstein D. Uncovering some subtleties of the uncovered set: social choice theory and distributive politics // Social Choice and Welfare. 1997. V. 15. P. 81-93.

29. Farquharson R. The theory of social choice. Princeton: Princeton University Press, 1973.

30. Feld S., Grofman В., Hartley R., Kilgour M., Miller N. The Uncovered Set in Spatial Voting Games // Theory and Decision. 1987. V. 23(2). P. 129-155.

31. Feld S., Grofman В., Miller N. The Geometry of Majority Rule // Journal of Theoretical Politics. 1989. V. 1(4). P. 379-406.

32. Ferejohn J. Spatial Theory of Elections // Political Science in History: research programs and political traditions / Eds. Farr J., Dryzek J., Leonard S. N.Y.: Cambridge University Press, 1995. P. 253-275.

33. Fishburn P. Condorcet social choice functions // SIAM Journal of Applied Mathematics. 1977. V. 33. P. 469-489.

34. Hartley R., Kilgour M. The geometry of the uncovered set // Mathematical Social Sciences. 1987. V. 14. P. 175-183.

35. Goff B, Grier K. On the (mis)measurement of legislator ideology and shirking // Public Choice. 1993. V. 76. P. 5-20.

36. Good I. A note on Condorcet sets // Public Choice. 1971. V. 10. P. 97-101.

37. Kadane J. Some equivalence classes in paired comparisons // Annals of Mathematical statistics. 1966. V. 37. P. 488-494.

38. Laffond G., Laine J. Condorcet choice and the Ostrogorski paradox // Social Choice and Welfare. 2009. V. 32. P. 317-333.

39. Laffond G., Laine J. Weak covering relations // Theory and Decision. 1994. V. 37(3). P. 245-65.

40. Laffond G., Laine J, Laslier J.-F. Composition-consistent tournament solutions and social choice functions // Social Choice and Welfare. 1996. V. 13. P. 7593.

41. Laffond G., Laslier J.-F. Slater's Winner of a Tournament may not be the Banks Set // Social Choice and Welfare. 1991. V. 8. P. 365-369.

42. Laffond G., Laslier J.-F, Le Breton M. Condorcet Choice Correspondences: A Set-Theoretical Comparison // Mathematical Social Sciences. 1995. V. 30 P. 25-35.

43. Laslier J.-F. Tournament Solutions and Majority Voting. Berlin/Heidelberg: Springer-Verlag, 1997.

44. Lombardi M. Minimal covering set solutions // Social Choice and Welfare. 2009. V. 32(4).

45. Lombardi M. Uncovered set choice rules // Social Choice and Welfare. 2008. V.31.P. 271-279.

46. McGarvey D. A theorem on the construction of voting paradoxes // Econometrica. 1953. V. 21. P. 608-610.

47. McKelvey R. Covering, dominance and institution-free properties of social choice // American Journal of Political Science. 1986. V. 30. P. 283-314.

48. Miller N. A new solution set for tournaments and majority voting: Further graph-theoretical approaches to the theory of voting // American Journal of Political Science. 1980. V. 24. P. 68-96.

49. Miller N. Graph-theoretical approaches to the theory of voting // American Journal of Political Science. 1977. V. 21. P. 769-803.

50. Miller N. Pluralism and Social Choice // American Political Science Review. 1983. V. 77. P. 734-747.

51. Miller N., Grofman В., Feld S. The structure of the Banks set // Public Choice. 1990. V. 66. P. 243-251.

52. Moulin H. Choosing from a Tournament // Social Choice and Welfare. 1986. V. 3(4). P. 271-291.53. von Neumann J., Morgenstern O. Theory of Games and Economic Behavior. Princeton: Princeton University Press, 1944.

53. Nurmi H. On the difficulty of making social choices // Theory and Decision. 1995. V. 38. No. 1.

54. Ordeshook P. Constitutional stability // Constitutional Political Economy. 1992. V. 3. No. 2.

55. Ordeshook P., Schwartz T. Agendas and The Control of Political Outcomes // The American Political Science Review. 1987. V. 81. No. 1. P. 179-199.

56. Ozkal-Sanver I., Sanver R. A new monotonicity condition for tournament solutions // Theory and Decision. 2009. (on-line publication).

57. Penn E. Alternate definitions of the uncovered set and their implications // Social Choice and Welfare. 2006. V. 27. P. 83-87.

58. Penn E. The Banks set in infinite spaces // Social Choice and Welfare. 2006. V. 27. P. 531-543.

59. Peris J., Subiza B. Condorcet choice correspondences for weak tournaments // Social Choice and Welfare. 1999. V. 16(2). P. 217-231.

60. Plott C. A Notion of Equilibrium and its Possibility under Majority Rule // American Economic Review. 1967. V. 67. Iss. 4. P. 787-806.

61. Shepsle K., Weingast B. Uncovered sets and Sophisticated Voting Outcomes with Implications for Agenda Institutions // American Journal of Political Science. 1984. V. 28(1). P. 49-74.

62. Smith J. Aggregation of Preferences with Variable Electorates // Econometrica. 1973. V. 41. Iss. 6. P. 1027-1041.

63. Schwartz Т. Collective choice, separation of issues and vote trading // The American Political Science Review. 1977. V. 71. No. 3. P. 999-1010.

64. Schwartz T. Cyclic Tournaments and Cooperative Majority Voting: A Solution // Social Choice and Welfare. 1990. V. 7. P. 19-29.

65. Schwartz T. On the Possibility of Rational Policy Evaluation // Theory and Decision. 1970. V. 1. P. 89-106.

66. Schwartz T. Parliamentary procedure: principal forms and political effects // Public Choice. 2008. V. 136. P. 353-377.

67. Schwartz T. Rationality and the Myth of the Maximum // Nous. 1972. V. 6. P. 97-117.

68. Schwartz T. The Logic of Collective Choice. N.Y.: Columbia University Press, 1986.

69. Subiza В., Peris J. Condorcet choice functions and maximal elements // Social Choice and Welfare. 2005. V. 24. P. 497-508.

70. Subochev A. Dominant, Weakly Stable, Uncovered Sets: Properties and Extensions. Working paper WP7/2008/03. Moscow: State University Higher School of Economics, 2008.

71. Ward B. Majority Rule and Allocation // Journal of Conflict Resolution. 1961. V. 5. P. 379-389.