Д. Гейл и Л. Шепли «Приём в колледж и стабильность свадеб»

Данная работа является основополагающей в теории обобщенных паросочетаний. Рассматривая задачу о женихах и невестах, Д. Гейл и Л. Шепли понимали, что свадьбы определяются не только фактом знакомства, как в [4], обычно значительную роль играют предпочтения участников относительно потенциальных партнеров. Поэтому они предложили алгоритм построения для случая, когда участники имеют предпочтения друг относительно друга и эти предпочтения задаются линейными порядками.

Введем понятие двудольного графа [4,5]: это математический объект, состоящий из множества дуг Г и объединения непересекающихся множеств вершин X и Y таких, что вершины из X могут быть соединены только с вершинами из Y и наоборот, а две вершины из X (или две вершины из Y) между собой не соединяются.

Классическое определение паросочетания формулируется следующим образом [4,5]: Если рассматривать X и Y как множества вершин двудольного графатогда паросочетанием в этом двудольном графе называется такое подмножество дуг, что никакие две дуги из П не имеют общей вершины.

Обычно принимается, что M — множество мужчин, W — множество женщин, а Г определяет факт знакомства первых со вторыми.

Обобщенное паросочетание — это взаимно-однозначное отображение множества на себя, удовлетворяющее условиям.

Первое условие означает, что если m женится на w, то w выходит замуж за m. Второе — если мужчина не остается в одиночестве, то он женится на женщине из множества W. Аналогичный смысл имеет и третье условие.

Поскольку далее рассматриваются только обобщенные паросочетания, слово «обобщенные» использоваться не будет.

В своих работах в задаче о женихах и невестах Д. Гейл и Л. Шепли рассматривали два множества.

· множество мужчин ;

· множество женщин .

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

Предпочтения, чаще всего, обозначаются символом или P, например: «x предпочтительнее, чем y» можно записать как, либо.

Предпочтения удовлетворяют условиям классической рациональности

· связности (or);

· транзитивности ();

· ацикличности ().

Бинарное отношение, которое удовлетворяет этим условиям, называется линейным порядком.

Через обозначается линейный порядок. Предпочтение мужчины на множестве W представляется в виде Аналогично для женщины определяется как.

.

В общем случае предпочтения i-ого мужчины записываются как.

а предпочтения j-ой женщины.

Все кандидаты, которые стоят в ряду предпочтений после элемента в скобках, считаются неприемлемыми. Наличие в ряду предпочтений самого кандидата, чьи предпочтения описываются, свидетельствует о том, что он пожелает остаться один, нежели быть в паре с неприемлемыми вариантами. Например, наличие в ряду.

элемента означает, что j-ая женщина предпочитает выйти замуж за одного из мужчин множества, но если такой союз невозможен, то она предпочтет остаться одна.

Паросочетание будем записывать двумя способами.

или.

.

Говорят, что паросочетание более предпочтительно для m, чем если .

Рассмотрим предпочтения мужчины вида.

и паросочетание, которое ставит этому мужчине в соответствие женщину, то есть. Так как i-ый мужчина в этом случае предпочитает остаться неженатым, паросочетание для него называется индивидуально иррациональным. Далее будут рассматриваться только индивидуально рациональные паросочетания.

Рассмотрим пример. Пусть и Пусть предпочтения участников выглядят следующим образом.

Рассмотрим паросочетание и мужчину.

Паросочетание предписывает ему жениться на женщине, при том, что наиболее предпочтительна для него женитьба на. С другой стороны, женщина в соответствии с должна выйти за, хотя мужчина для нее будет более предпочтительным вариантом. Но тогда пара может отказаться принимать условия, предписываемые паросочетанием. В этом случае говорят, что пара блокирует паросочтение. Блокирующая пара — это такая пара (m, w), что:, а. Если таких пар нет, то паросочетание называется устойчивым (стабильным).

Устойчивое паросочетание оптимально (эффективно) для женщин (мужчин), если каждой женщине (каждому мужчине) в нем, по крайней мере, не хуже, чем в любом другом устойчивом паросочетании.

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

Рассмотрим теперь паросочетание.

.

В нем нет блокирующих пар, поэтому устойчиво. Кроме того, оно оптимально для мужчин, потому что каждому мужчине в нем, по крайней мере, не хуже, чем в любом другом устойчивом паросочетании. Действительно, рассмотрим все возможные паросочетания.

Для паросочетание более предпочтительно, чем, потому что женщина, предписанная ему в паросочетании самая наилучшая в его списке предпочтений, аналогично для .

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

Устойчивое (стабильное) распределение — распределение, которое не блокируется никакой парой «выпускник-клиника», то есть, в данном распределении нет такой пары (a, h), где a — выпускник-медик, h — клиника, в которой.

.

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

Гейл и Шепли доказали ряд теорем, связанных с задачей о свадьбах и распределения в колледжах (клиниках), и построили алгоритм, позволяющий формировать искомые распределения (паросочетания) — алгоритм отложенного принятия [1].

Алгоритм отложенного принятия Гейла-Шепли для задачи о женихах и невестах:

Шаг 1. М) каждому мужчине приписывается первая в его предпочтениях женщина (если такой нет, он остается один); Ж) для каждой женщины просматриваются приписанные к ней мужчины; если они (он) для нее менее предпочтительны, чем одиночество, то она их отвергает, иначе — выбирает кандидата, который в ряду ее предпочтений стоит выше остальных;

Шаг i. М) отвергнутому на предыдущем шаге мужчине приписывается следующая в его предпочтениях женщина (если такой нет, он остается один); Ж) для каждой женщины просматриваются приписанные к ней мужчины; если они (он) для нее менее предпочтительны, чем одиночество, то она их отвергает, иначе — выбирает кандидата, который в ряду ее предпочтений стоит выше остальных;

Алгоритм конечен, так как множества мужчин и женщин конечны и на каждом шаге участникам приписываются не более одного кандидата.

Гейл и Шепли доказали, что данный алгоритм устойчив для мужчин/женщин (в задаче о женитьбах) и для выпускников (в задаче распределения в клиниках), то есть позволяет построить устойчивое и, более того, оптимальное (для одной из сторон) паросочетание. В зависимости от того, делают ли мужчины или женщины первыми выбор на каждом шаге алгоритма, получается, соответственно, оптимальное для мужчин или оптимальное для женщин паросочетание. Аналогично, в задаче о распределении выпускников по колледжам в зависимости от того, студенты или колледжи первыми делают выбор на каждом шаге алгоритма, получается, соответственно, оптимальное для студентов или оптимальное для колледжей паросочетание.

Пример использования алгоритма. Пусть Предпочтения участников имеют вид.

Построим оптимальное устойчивое паросочетание, пользуясь алгоритмом отложенного принятия.

Шаг 1. М); Ж) ;

Шаг 2. М); Ж) ;

Шаг 3. М); Ж) ;

Шаг 4. М); Ж) ;

Шаг 5. М); Ж) ;

Шаг 6. М); Ж) ;

Шаг 7. М); Ж) .

Алгоритм останавливается, так как все варианты для были рассмотрены.

Искомое устойчивое оптимальное паросочетание.

.

Рассмотрим задачу о распределении студентов по колледжам. C — множество колледжей,,; S — множество студентов,, ;- квота i-ого колледжа (количество свободных мест в колледже, на которые он набирает студентов);- предпочтения i-ого колледжа; - предпочтения j-ого студента.

Требуется найти оптимальное устойчивое паросочетание. Д. Гейл и Л. Шепли построили и обосновали алгоритм отложенного принятия, позволяющий найти решение и для этой задачи.

Алгоритм отложенного принятия Гейла-Шепли для задачи о распределении студентов по колледжам:

Шаг 1. С) каждому студенту приписывается первый в его предпочтениях колледж; К) каждый колледж приписывает из этих студентов в свой лист ожидания q лучших (или всех, если их меньше q), остальных отвергает;

Шаг i. С) отвергнутым студентам приписываются колледжи согласно их следующим предпочтениям; К) каждый колледж отбирает q лучших студентов из новых и уже приписанных к нему, остальных отвергает;

Алгоритм не останавливается до тех пор, пока каждый студент не будет на листе ожидания, либо отвергнут всеми колледжами, куда хотел попасть.

Пример использования алгоритма. Пусть имеется множество колледжей и множество студентов, квоты колледжей заданы Предпочтения участников имеют вид.

Построим оптимальное устойчивое паросочетание, пользуясь алгоритмом отложенного принятия.

Шаг 1. С); К) ;

Шаг 2. С); К) ;

Алгоритм останавливается, так как все студенты попали на листы ожидания.

Искомое устойчивое оптимальное паросочетание.

.

Возникает вопрос: можно ли свести распределение студентов по колледжам к модели свадеб? Будет ли тогда паросочетание, полученное с помощью алгоритма отложенного принятия для модели свадеб, совпадать с исходным?

А. Рот [6] показал, что ответ положительный, т. е. что распределение студентов по колледжам можно свести к модели свадеб путем рассмотрения вместо каждого колледжа c некоторой квотой копии этого колледжа с такими же предпочтениями относительно студентов, но с квотами равными единице. Пусть C — множество колледжей,,; S — множество студентов,, ;- квота i-ого колледжа.

Пусть, тогда будем рассматривать среди множества колледжей k раз (и так поступим с каждым колледжем). В итоге получим вместо m элементов множества C ()-колледжей c единичными квотами:

Таким образом, задача поиска паросочетания сводится к построению пар «один-к-одному», как в случае модели свадеб, с помощью алгоритма отложенного принятия. В результате его применения получается устойчивое оптимальное паросочетание, причем каждый студент попадет в тот же колледж, что и в исходной модели распределения студентов по колледжам.