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

На правах рукописиСубочев Андрей НиколаевичКОНЦЕПЦИИ РЕШЕНИЙ В ЗАДАЧЕ КОЛЛЕКТИВНОГО ВЫБОРАСпециальность 05.13.18 – "Математическое моделирование, численные методы и комплексыпрограмм"АВТОРЕФЕРАТдиссертации на соискание ученой степеникандидата физико-математических наукМосква - 2009Работа выполнена в Государственном образовательном бюджетном учреждении высшегопрофессиональногообразования«Государственныйуниверситет-Высшаяшколаэкономики» при частичной финансовой поддержке Научного фонда ГУ-ВШЭ (грант №08-040008), Российского фонда фундаментальных исследований (совместный российско-турецкийисследовательский проект, грант №09-01-91224-CT_a) и Лаборатории методов выбора ианализа решений Центра фундаментальных исследований ГУ-ВШЭ.Научный руководитель:доктор технических наук,Алескеров Фуад ТагиевичОфициальные оппоненты:доктор физико-математических наук, профессорВасин Александр Алексеевичдоктор физико-математических наукЧеботарев Павел ЮрьевичВедущая организация:Федеральное государственное образовательноеучреждение высшего профессиональногообразования"Санкт-Петербургский государственныйуниверситет"Защита состоится "__" __________ 200__г.

в ___ часов на заседании диссертационногосовета Д 212.048.09 при Государственном университете - Высшей школе экономики поадресу: 105187, г. Москва, ул. Кирпичная, д. 33/5.С диссертацией можно ознакомиться в библиотеке Государственного университета - Высшейшколы экономики по адресу: 101990, г. Москва, ул. Мясницкая, д. 20.Автореферат разослан "__" __________ 200__г.Ученый секретарь диссертационного советад.т.н., доцентВ.А.Фомичев2I. ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫВ настоящей диссертации рассматриваются основные концепции решенийв задаче коллективного выбора, связанные с отношением мажоритарногодоминирования, которое моделирует предпочтения коллектива. Сравниваютсятакие решения как ядро, минимальное доминирующее множество, непокрытоемножество, минимальное слабоустойчивое множество и другие; выявляетсясвязь между ними. Рассматривается концепция k-устойчивых альтернатив ивводится концепция k-устойчивых множеств; устанавливается их соотношениес вышеназванными решениями.

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

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

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

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

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

Т.о. в анализе также используются логико-алгебраические объекты.Научная новизна. В ходе решения поставленных задач полученыследующие новые результаты:1.Сформулированпринадлежностьлюбойкритерий,сальтернативы4помощьюкоторогоминимальномупроверяетсяслабоустойчивомумножеству. С его помощью установлено, что непокрытое множество являетсяподмножеством объединения минимальных слабоустойчивых множеств;2. Построены обобщения минимального доминирующего множества, и с ихпомощью выяснено, как устроена система доминирующих множеств.3. Установлены новые соотношения между множествами-решениями.4. Для турниров впервые введено понятие обобщенно-устойчивогомножества альтернатив. С помощью этого понятия построено обобщениеслабоустойчивого множества - класс k-устойчивых множеств.

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

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

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

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

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

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