Формулировка задачи

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

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

По крайней мере на начальной стадии будет полезно устранить эти сложности и перейти к «упрощенной» постановке задачи: каждый из n кандидатов подает заявки в каждую из n компаний, а каждая компания хочет принять на работу одного кандидата. Вскоре вы увидите, что при этом сохраняются фундаментальные аспекты задачи; в частности, наше решение упрощенной версии можно будет напрямую расширить для более общего случая.

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

Итак, имеется множество M = {m1, …, mn} из n мужчин и множество W = {w1,

..., wn} из n женщин. Пусть запись M × W обозначает множество всех возможных упорядоченных пар в форме (m, w), где m Ѯ M и w Ѯ W. Паросочетание1 S представляет собой множество упорядоченных пар, каждая из которых входит в M × W, обладающее тем свойством, что каждый элемент M и каждый элемент W встречается не более чем в одной паре в S. Идеальным паросочетанием S’ называется паросочетание, при котором каждый элемент M и каждый элемент W встречается ровно в одной паре из S’.

Мы еще не раз в книге вернемся к концепциям паросочетаний и идеальных паросочетаний; они естественным образом возникают при моделировании широкого диапазона алгоритмических задач. На текущий момент термин «идеальное паросочетание» соответствует способу формирования пар из мужчин и женщин таким способом, чтобы каждый оказался с кем-то в паре и никто не был включен более чем в одну пару — ни одиночество, ни полигамия.

Теперь в эту схему можно добавить понятие предпочтений. Каждый мужчина m Ѯ M формирует оценки всех женщин; мы говорим, что m предпочитает w женщине w’, если m присваивает w более высокую оценку, чем w’. Мы будем называть упорядоченную систему оценок m его списком предпочтений. «Ничьи» в оценках запрещены. Аналогичным образом каждая женщина назначает оценки всем мужчинам.

Какие могут возникнуть проблемы с имеющимся идеальным паросочетанием S? В контексте исходной задачи с нанимателями и кандидатами возможна следующая неприятная ситуация: в S присутствуют две пары (m, w) и (m’, w’ ), обладающие таким свойством, что m предпочитает w’ женщине w, а w’ предпочитает m мужчине m’.

В таком случае ничто не помешает m и w’ бросить своих партнеров и создать новую пару; такой набор пар не является саморегулируемым. В нашей терминологии такая пара (m, w’ ) является неустойчивой по отношению к S: пара (m, w’ ) не принадлежит S, но каждый из участников m и w’ предпочитает другого своему текущему партнеру в S.

Итак, нашей целью является создание паросочетания без неустойчивых пар. Паросочетание S называется устойчивым, если оно (1) идеально и (2) не содержит неустойчивости в отношении S. Немедленно возникают два вопроса:

• Существует ли устойчивое паросочетание для каждого набора списков предпочтений?
• Можно ли эффективно построить устойчивое паросочетание для имеющегося списка предпочтений (если оно существует)?