Автореферат (Обобщенные паросочетания при предпочтениях, не являющихся линейными порядками), страница 2

(доклад: «Обобщенные паросочетания: эффективность и неманипулируемость при предпочтениях, являющихся полупорядками»).4. 11th Meeting of Society for Social Choice and Welfare, Дели, Индия, август2012 г. (доклад: «College admissions with stable score-limits»).5.

8th Spain-Italy-Netherlands Meeting on Game Theory (SING8), Будапешт, Венгрия, июль 2012 г. (доклад: «College admissions with stable score-limits»).6. XIII Международная конференция по проблемам развития экономики и общества, Москва, апрель 2012 г. (доклад: «Обобшенные паросочетания припредпочтениях, являющихся простейшими полупорядками: устойчивость иоптимальность по Парето»).7. Семинар «Математическая экономика» ЦЭМИ РАН, декабрь 2011 г. (доклад: «Модели обобщенных паросочетаний: классические работы и новыерезультаты»).8. Совместный российско-финский семинар «Современные исследования вобласти коллективного принятия решений и общественного выбора» (JointPCRC-DeCAn Workshop), Университет Турку, Финляндия, ноябрь 2011 г.(доклад: «Matchings with preferences being simplest semiorders»).9.

Общемосковский семинар «Экспертные оценки и анализ данных», ИПУРАН, Москва, октябрь 2011 г. (доклад «Модели обобщенных паросочетанийс предпочтениями, не являющимися линейными порядками»).10. 7th Spain-Italy-Netherlands Meeting on Game Theory (SING7), Париж, Франция, июль 2011 г. (доклад: «Обобщенные паросочетания с предпочтениями, являющимися простейшими полупорядками: стабильность и эффективность по Парето»).711. XII Международная конференция по проблемам развития экономики и общества, Москва, апрель 2011 г.

(доклад: «Модель выбора вузов абитуриентами и приемной кампании в России»).Личный вклад. Автором исследованы модели обобщенных паросочетаний при предпочтениях, заданных простейшими полупорядками и интервальными порядками; сформулированы и доказаны теорема о существовании сохраняющего устойчивость линейного расширения для любого устойчивого паросочетания, а также теорема о критерии эффективности устойчивого паросочетания сточки зрения абитуриентов.Автором построен устойчивый механизм, не дающий стимулов манипулирования предпочтениями для абитуриентов, и при этом порождающий неэффективное паросочетание с меньшей вероятностью, чем классический механизмГейла-Шепли со случайным устранением безразличий в предпочтениях.Автором проанализирована российская псевдо-централизованная процедура проведения приемной кампании в государственных вузах.Автор принимал участие в:∙ исследовании модели обобщенных паросочетаний, основанных на одинаковом рассмотрении абитуриентов с одинаковыми оценками (анализ Lконцепции устойчивости, демонстрация возможности манипулирования,доказательство теоремы о преимуществе L-концепции над H-концепциейс точки зрения абитуриентов).∙ разработке программного комплекса, реализующего предложенные автором механизмы.

Автором разработана архитектура программного комплекса, модуль генерации и внешней загрузки предпочтений, модуль проверкиналичия устойчивых улучшающих циклов.Публикации. Основные результаты по теме диссертации изложены в 6печатных изданиях, 2 из которых изданы в журналах, рекомендованных ВАК, 4— в сериях препринтов и тезисах докладов.8Содержание работыВо введении обосновывается актуальность исследований, проводимых врамках данной диссертационной работы, приводится обзор научной литературыпо изучаемой проблеме, формулируется цель, ставятся задачи работы, сформулированы научная новизна и практическая значимость представляемой работы.Первая глава посвящена обзору классических результатов теории обобщенных паросочетаний.В разделе 1.1 рассмотрены классические результаты для модели обобщенных паросочетаний «один к одному».

Дано понятие устойчивого обобщенного паросочетания для модели «один к одному» и приведен предложенныйД. Гейлом и Л. Шепли механизм отложенного принятия, позволяющий построить устойчивое паросочетание. В рамках работы механизма игроки одной изгрупп делают предложения, а игроки другой группы рассматривают поступившие предложения и временно принимают наилучшее из них. Существуют двесимметричные версии данного механизма, отличающиеся тем, какая группа игроков делает предложения и за счет этого имеет преимущество. Механизм строит устойчивое паросочетание, которое является наилучшим (оптимальным поПарето) среди всех устойчивых для предлагающей группы.

Кроме того, при использовании механизма предлагающие игроки не заинтересованы в манипулировании, т.е. для каждого из игроков предлагающей группы слабо доминирующейстратегией является сообщение своих истинных предпочтений.В разделе 1.2 рассмотрено расширение модели на случай «один ко многим». Введем здесь необходимые основные обозначения для модели «один комногим», поскольку они будут использованы в дальнейшей работе.Обозначим через конечное множество абитуриентов, а через – конечное множество вузов. Каждый абитуриент может быть зачислен не более, чем водин вуз. Для каждого ∈ установлена квота – это целое положительноечисло, равное максимальному числу абитуриентов ∈ , которые могут бытьзачислены в (поставлены в пару с) .Определение 1.9.

Обобщенное паросочетание – это отображение : ( ∪ ) → 2(∪)9такое, что 21. () = {} ⇔ ∈ () (если абитуриент зачислен в вуз, то вуз зачислилэтого абитуриента)2. ∀ ∈ () = {} или () = {} (абитуриент либо зачислен в вуз, либооставлен без места, т.е. поставлен в пару с самим собой)3. ∀ ∈ () ⊆ или () = {} (вуз либо зачислил подмножество абитуриентов, либо все места остались незаполненными)4. ∀ ∈ |()| ≤ (число абитуриентов, зачисленных в , не превышаетего квоты )Профиль предпочтений абитуриентов = (1 , ..., || ) состоит из бинарных отношений, каждое из которых задано на множестве ∪ {} и является линейным порядком. Это означает, что каждый абитуриент упорядочиваетвсе вузы по предпочтительности поступления.

Некоторые вузы могут оказаться менее предпочтительными, чем («опция одиночества») т.е. обучение в таком вузе недопустимо для данного абитуриента. Профиль предпочтений вузов⪰= (≻1 , ..., ≻|| ) состоит из бинарных отношений, каждое из которых заданона множестве ∪ {} и является линейным порядком. Это означает, что каждыйвуз упорядочивает абитуриентов по предпочтительности зачисления, некоторыеабитуриенты могут оказаться недопустимыми для данного вуза.Определение 1.11. Обобщенное паросочетание называется устойчивым, если оно является∙ индивидуально рациональным, т.е. ни один абитуриент не зачислен в недопустимый для себя вуз (∀ ∈ верно, что ()), а ни один вуз незачислил недопустимого абитуриента (∀ ∈ верно, что ∀ ∈ () ≻ );∙ не содержит блокирующих пар, т.е. нет таких абитуриента и вуза , которые не поставлены в пару друг с другом и удовлетворяют хотя бы одномуиз двух условий:2Обозначим через 2(∪) множество всех подможеств ∪ 10– (), ≻ , |()| < (абитуриент предпочитает вуз по сравнению с тем, куда зачислен, а вуз считает абитуриента допустимым иимеет свободное место),– () и ∃′ ∈ () : ≻ ′ (абитуриент предпочтитает вуз посравнению с тем, куда зачислен, а для вуза абитуриент предпочтительнее кого-то из уже зачисленных абитуриентов).Для классической модели «один ко многим», где предпочтения заданылинейными порядками, также применим предложенный Гейлом и Шепли механизм отложенного принятия в двух версиях – с предлагающими абитуриентамии с предлагающими вузами.Для модели «один ко многим» особый интерес представляет проблемаманипулирования.

А. Рот показал, что в любом механизме, который строитустойчивое паросочетание, вузам (т.е. игрокам, которые могут получать болееодной пары в обобщенном паросочетании) может быть выгодно искажать своипредпочтения на множестве абитуриентов. Кроме того, в работах Т. Сонмеза иЛ. Эхлерса показано, что вузы в любых механизмах, строящих устойчивое паросочетание, также могут искажать свои квоты, гарантируя себе получение болеепредпочтительного, чем при сообщении истинной квоты, набора абитуриентов.Таким образом, не существует механизма, который строил был устойчивое паросочетание и при этом был бы неманипулируем вузами.В разделе 1.3 проанализировано развитие теории обобщенных паросочетаний, связанное с анализом более широких, чем в классических моделяхГейла-Шепли, классов отношений предпочтения игроков.

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