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

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