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

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

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

«полов» (кандидаты и компании), а в рассматриваемом случае каждый участник подыскивает себе ровно одного участника противоположного пола1.

Итак, имеется множество 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. Немедленно возникают два вопроса:

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