Диссертация (1137447), страница 2
Текст из файла (страница 2)
Впервые предложены верхняя и нижняя оценки возможных граничных оценок для классического механизма Гейла-Шепли со случайным устранением безразличий.6. Выполненооригинальноеисследованиероссийскогопсевдо-централизованного механизма организации приемной кампании ипоказаны источники неэффективности получаемого распределенияабитуриентов по вузам.Методы исследования Теория принятия решшений, кооперативныеигры с нетрансферабельной полезностью, оптимизационные модели,теория бинарных отношений, теория экономических механизмов.Апробация работы.
Основные результаты работы докладывалисьна следующих семинарах и конференциях:1. The 24-th Stony Brook Game Festival of the Game Theory Society,Стони Брук, США, июль 2013 г. (доклад «Matchings with intervalorder preferences: stability and Pareto-efficiency»).82. Семинар Matching in Practice, Université Libre de Bruxelles, Брюссель, Бельгия, май 2013 г.(доклад: «Efficiency vs strategy-proofnessfor matching with interval order preferences»).3. Общемосковский семинар «Экспертные оценки и анализ данных»,ИПУ РАН, Москва, март 2013 г. (доклад: «Обобщенные паросочетания: эффективность и неманипулируемость при предпочтениях,являющихся полупорядками»).4. 11th Meeting of Society for Social Choice and Welfare, Дели, Индия, август 2012 г.
(доклад: «College admissions with stable scorelimits»).5. 8th Spain-Italy-Netherlands Meeting on Game Theory (SING8), Будапешт, Венгрия, июль 2012 г. (доклад: «College admissions withstable score-limits»).6. XIII Международная конференция по проблемам развития экономики и общества, Москва, апрель 2012 г. (доклад: «Обобшенныепаросочетания при предпочтениях, являющихся простейшими полупорядками: устойчивость и оптимальность по Парето»).7. Семинар «Математическая экономика» ЦЭМИ РАН, декабрь 2011г. (доклад: «Модели обобщенных паросочетаний: классические работы и новые результаты»).8. Совместный российско-финский семинар «Современные исследования в области коллективного принятия решений и общественного выбора» (Joint PCRC-DeCAn Workshop), Университет Турку,Финляндия, ноябрь 2011 г.
(доклад: «Matchings with preferencesbeing simplest semiorders»).99. Общемосковский семинар «Экспертные оценки и анализ данных»,ИПУ РАН, Москва, октябрь 2011 г. (доклад «Модели обобщенных паросочетаний с предпочтениями, не являющимися линейными порядками»).10. 7th Spain-Italy-Netherlands Meeting on Game Theory (SING7), Париж, Франция, июль 2011 г. (доклад: «Обобщенные паросочетания с предпочтениями, являющимися простейшими полупорядками: стабильность и эффективность по Парето»).11. XII Международная конференция по проблемам развития экономики и общества, Москва, апрель 2011 г. (доклад: «Модель выбора вузов абитуриентами и приемной кампании в России»).Личный вклад.
Автором исследованы модели обобщенных паросочетаний при предпочтениях, основанных на пороговых функциях, –простейших полупорядках, полупорядках и интервальных порядках.Автором сформулированы и доказаны теорема о существовании сохраняющего устойчивость линейного расширения для любого устойчивого паросочетания, а также теорема о критерии эффективностиустойчивого паросочетания с точки зрения абитуриентов.Автором построен устойчивый механизм, не дающий стимулов манипулирования предпочтениями для абитуриентов, и при этом порождающий неэффективное паросочетание с меньшей вероятностью, чемклассический механизм Гейла-Шепли со случайным устранением безразличий в предпочтениях.Автором проанализирована российская псевдо-централизованнаяпроцедура проведения приемной кампании в государственных вузах.Автор принимал участие в:10∙ разработке программного комплекса, реализующего предложенныеавтором механизмы. Автором разработана архитектура программного комплекса, модуль генерации и внешней загрузки предпочтений, модуль проверки наличия устойчивых улучшающих циклов.∙ исследовании модели обобщенных паросочетаний, основанныхна одинаковом рассмотрении абитуринтов с равными оценками(анализ L-концепции устойчивости, демонстрация возможностиманипулирования, доказательство теоремы о преимуществе Lконцепции над H-концепцией с точки зрения абитуриентов).Публикации.
Основные результаты по теме диссертации изложеныв 6 печатных изданиях, 2 из которых изданы в журналах, рекомендованных ВАК:1. Кисельгоф С.Г. Обобщенные паросочетания при предпочтениях,являющихся простейшими полупорядками: стабильность и оптимальность по Парето // Автоматика и телемеханика. 2014.
№6.С. 103-114.2. Кисельгоф С.Г. Моделирование приемной кампании: вузы различного качества и абитуриенты с квадратичной функцией полезности// Проблемы управления. 2012. № 5. С. 33-40.а также:3. Biro P., Kiselgof S. G. College admissions with stable score - limits /Working papers by Hungarian Academy of Sciences. Series MT-DP«Discussion Papers of Hungarian Academy of Sciences». 2013. No.6114. Кисельгоф С.Г. Модель выбора вузов абитуриентами приемнойкампании в России // В кн.: XII Международная научная конференция по проблемам развития экономики и общества. В четырехкнигах. Книга 2. / Отв. ред.: Е.
Г. Ясин. . Кн. 2. М.:Издательскийдом НИУ ВШЭ, 2012. С. 422-430.5. Kiselgof S. Matchings with Simplest Semiorder Preference Relations,in: Game Theory and Management. Collected abstracts of paperspresented on the Fifth International Conference Game Theoryand Management / Ed. by L. A.
Petrosyan,N. A. Zenkevich.St. Petersburg: Graduate School of Management, St. PetersburgUniversity, 2011. P. 119-121.6. Кисельгоф С.Г. Выбор вузов абитуриентами с квадратичной функцией полезности / Препринты. М.:Высшая школа экономики. Серия WP7 «Математические методы анализа решений в экономике,бизнесе и политике». 2011. № 01.Объем и структура работы. Диссертация состоит из введения,трех глав, заключения и одного приложения. Полный объем диссертации составляет 185 страниц с 5 рисунками и 11 таблицами. Списоклитературы содержит 62 наименования.12Глава 1Обобщенные паросочетания:классические результатыЭта глава представляет собой обзор классических результатов теории обобщенных паросочетаний, на которых основано оригинальноеисследование настоящей диссертации.1.1Обобщенные паросочетания один к одному, или задача освадьбах1.1.1Устойчивое паросочетание: существование и механизм построенияРассмотрим неориентированный двудольный граф = ( ∪ , ),где и – конечные и непересекающиеся между собой подмножества вершин графа, а – множество ребер, соединяющих вершиныграфа.
В двудольном графе ребро может связывать только вершины,принадлежащие разным подмножествам. У каждого ребра ∈ естьдве концевые вершины ∈ и ∈ , таким образом, = {, }.Вершина инцидентна ребру , если является одним из его концов.13Определение 1.1. Паросочетанием в двудольном графе называетсяподмножество ребер ∈ , такое что любая вершина ∈ ∪ инцидентна не более чем одному ребру.Классической задачей математического моделирования является задача поиска паросочетания максимальной мощности в заданном графе. Традиционно в литературе [1, 3] эта задача называется задачейо назначении на работы или задачей о свадьбах. Для удобства дальнейшего изложения будет называть подмножество вершин графа множеством мужчин, а подмножество – множеством женщин.
Если ребро = {, } входит в паросочетание , будем говорить, чтомужчина и женщина поставлены в пару друг с другом.Гейл и Шепли [2] предложили рассмотреть расширение классической модели. Пусть теперь необходимо не просто найти паросочетание максимальной мощности, но найти такое паросочетание, котороеучитывает предпочтения вершин (или, точнее, соответствующих вершинам рациональных агентов). Предпочтения будут описываться бинарными отношениями.Будем говорить, что на множестве задано бинарное отношение , если ⊆ × .
Если пара (, ) ∈ , будем также обозначатьэто как .Если же (, ) ∈/ , обозначим это как .Определение 1.2. Линейным порядком [13] называется бинарное отношение , заданное на некотором множестве и обладающее свойствами:∙ связности, т.е. ∀, ∈ , если ̸= , то или , или ;∙ транзитивности, т.е. ∀, , ∈ если , , то ;14∙ асимметричности, т.е. ∀, если , то .Фактически задание на множестве отношения предпочтения, являющегося линейным порядком означает, что все элементы этого множества упорядочены от наиболее предпочтительного до наименее предпочтительного.
В [2] предпочтения каждой вершины (мужчины) ∈ описываются бинарным отношением , которое задано на множестве ∪ и является линейным порядком. Иначе говоря, мужчинаупорядочивает по предпочтительности всех женщин и опцию «остаться в одиночестве». Аналогично, отношение предпочтения каждойвершины ∈ задано на множестве ∪ и является линейным порядком. Совокупность всех отношений предпочтения будем называтьпрофилем предпочтений и обозначать . Будем говорить, что ()допустим(а) для (), если (соответственно, ). Ребра в графе связывают вершины и , только если они являютсядопустимыми друг для друга.Определение 1.3.
Обобщенное паросочетание [2,13] – это взаимнооднозначное отображение : ∪ −→ ∪ такое, что:∙ ∀ ∈ если () = , то () = , и, аналогично, ∀ ∈ если () = , то () = ;∙ ∀ ∈ () = или () = , и, аналогично, ∀ ∈ () = или () = Обобщенное паросочетание соответствует паросочетанию в графе в следующем смысле: если () = , то ребро = {, } ∈ .11Вдальнейшем для краткости будем опускать определение «обобщенное» при упоминании обобщенного паросочетания.15Как же при построении паросочетания учесть предпочтения сторон?Гейл и Шепли предложили подход, основанный на поиске устойчивогопаросочетания (stable matching).
Основная идея их подхода заключается в следующем: никакая одна вершина (соответствующий ей рациональный агент) или пара вершин из разных множеств (мужчинаи женщина) не должны иметь стимула отказаться от предложеннного паросочетания с выгодой для себя при условии, что все остальныевершины остаются в паросочетании. Итак, дадим формальное определение устойчивого паросочетания.Определение 1.4. Обобщенное паросочетание устойчиво, если оноудовлетворяет требованиям:1. индивидуальной рациональности: ∀ ∈ ∪ таких, что () ̸= верно, что () , то есть для каждого игрока, который получилпару в паросочетании , полученный партнер () является допустимым;2.
попарной устойчивости: не существует ∈ и ∈ таких,что (одновременно) () и (), т.е. не существует такой пары, что каждый предпочитает другого по сравнению с полученным согласно партнером.Дадим еще одно определение.Определение 1.5. Пара , называется блокирующей паросочетание , если ее присутствие нарушает устойчивость паросочетания всоответствии с пунктом 2 определения устойчивого паросочетания.В [2] доказано, что устойчивое паросочетание всегда существует.Более того, в [2] предложено конструктивное доказательство этого16утверждения в форме механизма, позволяющего построить устойчивое паросочетание для заданного профиля предпочтений мужчин иженщин.Механизм, позволяющий найти устойчивое паросочетание, называется механизмом отложенного принятия (англ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
