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

Рассмотрено расширение классической модели обобщенных паросочетаний Гейла–Шепли. Модель описывает двусторонний рынок: с одной стороны – вузы, каждый из которых имеет ограничение по числу зачисляемых студентов; с другой стороны – абитуриенты, каждый из которых может получить одно место в вузе. И абитуриенты, и вузы высказывают предпочтения относительно желаемого распределения. Предполагается, что каждый абитуриент выстраивает линейный порядок на множестве желаемых вузов, а каждый вуз имеет предпочтения, являющиеся простейшими полупорядками. Для данной модификации показано, что всегда существует устойчивое паросочетание. Кроме того, сформулированы необходимое и достаточное условия оптимальности по Парето устойчивого паросочетания.

Статья представлена к публикации членом редколлегии: Ю. С. Попков