Автореферат (1137312)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

На правах рукописиВеселова Юлия АлександровнаСтепень манипулируемости процедур агрегированияСпециальность 05.13.18 — Математическое моделирование,численные методы и комплексы программАвторефератдиссертации на соискание учёной степеникандидата физико-математических наукМосква — 2017Работа выполнена в федеральном государственном автономном образовательном учреждении высшего образования «Национальный исследовательский университет «Высшая школа экономики»Научныйдоктор технических наук,руководитель:старший научный сотрудникАлескеров Фуад ТагиевичОфициальныеВасин Александр Алексеевич,оппоненты:доктор физико-математических наук, профессор,Федеральное государственное бюджетное образовательноеучреждение высшего образования «Московскийгосударственный университет имени М.В.Ломоносова»,кафедра исследования операций факультетавычислительной математики и кибернетики, профессорПоляков Николай Львович,кандидат физико-математических наук, Федеральноегосударственное образовательное бюджетное учреждениевысшего образования «Финансовый университет приПравительстве Российской Федерации», департаментанализа данных, принятия решений и финансовыхтехнологий, старший преподавательВедущаяФедеральное государственное учреждение «Федеральныйорганизация:исследовательский центр «Информатика и управление»Российской академии наук»Защита состоится 26 января 2018 года в1300на заседании диссертационно-го совета Д 212.048.09 при Национальном исследовательском университете«Высшая школа экономики» по адресу: 101000, Москва, ул.

Мясницкая, д.20,ауд. 242.С диссертацией можно ознакомиться в библиотеке Национального исследовательского университета «Высшая школа экономики» по адресу: 101000,Москва, ул. Мясницкая, д.20 и на сaйте https://www.hse.ru/sci/diss/209518151Автореферат разослан «»20года.Ученый секретарьдиссертационного совета,доктор технических наукГостев Иван Михайлович2Общая характеристика работыАктуальность темы. В теории коллективного выбора известна проблема подверженности правил принятия коллективных решений манипулированию со стороны избирателей: участники голосования могут намеренно сообщить свои неискренние предпочтения с целью добиться более выгодногодля них результата. Если правило коллективного выбора допускает возможность манипулирования хотя бы для одного избирателя и хотя бы в однойиз множества возможных ситуаций (под ситуацией понимается распределение предпочтений среди всех избирателей, т.е.

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

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

Манипулируемость правила коллективного выбора считается отрицательным свойством, так как избиратель,манипулируя, отклоняет результат голосования от «истинного» коллективного выбора в свою пользу. Кроме того, если имеется несколько независимоманипулирующих избирателей, то результат может оказаться для них дажехуже первоначального. В то же время исключить манипулирование полностью невозможно. Теорема, доказанная независимо А. Гиббардом в 1973 г. иМ.Саттертуэйтом в 1975 г., утверждает, что любое недиктаторское правилоколлективного выбора, результат которого – единственная альтернатива, является манипулируемым, если имеется хотя бы три возможных исхода. Поэтому возникает необходимость сравнивать степень манипулируемости разныхправил.В работах Д.Келли, Ф.Т.Алескерова, Э.Курбанова, Д.С.Карабекяна,Д.Лепеллье, А.Слинько, Д.Притчарда, М.Уилсона и др.

степень манипулируемости правила рассматривается как вероятность возникновения такой си-3туации, в которой хотя бы одному избирателю будет выгодно исказить своипредпочтения при данном правиле. Расчет такого индекса зависит от выбранной в исследовании вероятностной модели, определяющей множество элементарных исходов. Наиболее часто используемые в литературе вероятностныемодели – модель независимых предпочтений (Impartial Culture Model – модель IC), описанная Г.Т.Гильбо в 1952 г., и модель независимых анонимныхпредпочтений (Impartial Anonymous Culture Model – модель IAC) (К.Кугаи Х.Нагатани, 1974 г.). Важное теоретическое значение имеет также модельнезависимых анонимных и нейтральных предпочтений, предложенная сравнительно недавно О.Эгеджиолу и А.Гиритлигиль (2013 г.).Базовая предпосылка большинства исследований – наличие полнойинформации у каждого из участников голосования о предпочтениях всехостальных избирателей, что представляется достаточно нереалистичным.

Вработах В.Конитцера и др. (2011 г.), А.Рейнхуд и У.Эндрисса (2012 г.) быларассмотрена задача манипулирования при неполной информации: избирателям недоступна информация о предпочтениях всех остальных участниковголосования, но известны результаты опроса всех избирателей, представленные в некотором агрегированном виде, так называемая функция публичнойинформации.Ключевым вопросом в изучении задачи манипулирования являетсяпостроение адекватной математической модели.

Соответственно, результатыисследования во многом зависят от постановки задачи и исходных предположений. В связи с этим актуальными задачами исследования являются:1) Построение математической модели, описывающей реальные ситуации принятия коллективных решений, и получение новой информации освойствах применяемых на практике процедур. В рамках этой задачи представляет интерес получение значений степени манипулируемости при неполной информации.2) Определение того, как зависит степень манипулируемости от исходных предположений, в частности, от типа публичной информации и используемой вероятностной модели.Целью данной работы является исследование степени манипулируемости процедур агрегирования в условиях неполной информации, а также вразличных вероятностных моделях.Для достижения поставленной цели были решены следующие задачи:1. Сделан обзор литературы по методам оценки степени манипулируемости процедур агрегирования: теоретическим результатам, вычислениювероятности манипулирования и вычислительной сложности манипулирования результатом голосования.42.

Сформулирована задача определения вероятности индивидуального манипулирования при неполной информации. Показано, при каких условиях вероятности манипулирования при полной и неполной информацииравны.3. Показано, что вероятность манипулирования нельзя рассматривать какосновной индекс манипулируемости в случае неполной информации.

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

Разработан комплекс программ для точного вычисления индексов манипулируемости и проведена серия вычислительных экспериментов для 6правил коллективного выбора, 8 типов функции публичной информациии 3 методов расширения предпочтений.6. Проведено сравнение вероятностных моделей, используемых для статистического анализа свойств правил коллективного принятия решений.Исследована максимальная разность вероятностных показателей в моделях IC, IAC и IANC.

Вычислены индексы манипулируемости для четырех правил в модели IANC для числа избирателей от 3 до 30.Объектом исследования являются процедуры принятия коллективныхрешений, а также вероятностные модели колллективного выбора.Предметом исследования является манипулируемость процедур принятия коллективных решений и свойства вероятностных моделей.Методологическую основу исследованиясоставляютметодысовре-менной прикладной алгебры, математической логики, теории вероятностей,теории выбора и принятия решений, комбинаторики, метод статистическихиспытаний. В вычислительных экспериментах применялось компьютернооемоделирование.Научная новизна:1. Впервые получены теоретические результаты о вероятности манипулирования в случае, когда избирателям доступна не вся информация опредпочтениях других участников голосования.2.

Предложены к рассмотрению новые индексы манипулируемости для случая с неполной информацией.53. Впервые исследовано влияние степени информативности функции публичной информации на манипулируемость правил.4. Получены новые данные о том, при каких типах публичной информациии для каких правил степень манипулируемости равна или почти равнанулю.5. Впервые рассмотрена задача определения максимально возможной разности индексов в вероятностных моделях.6. Впервые получены оценки максимальной разности вероятностей в такихчасто используемых моделях, как IC и IAC, а также IAC и IANC, IC иIANC.7. Впервые получены значения вероятности манипулирования в моделиIANC.Теоретическая значимость. В диссертационной работе впервые исследована степень манипулируемости в случае неполной информации, предложены три индекса манипулируемости, показано, почему индекс вероятностиманипулирования нельзя рассматривать как основной.

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов диссертации