Устойчивые паросочетания в задачах

Задача устойчивых паросочетаний была частично сформулирована в 1962 году, когда два экономиста-математика, Дэвид Гейл и Ллойд Шепли, задались вопросом: можно ли спланировать процесс поступления в колледж (или приема на работу), который был бы саморегулируемым (self-enforcing)? Что они имели в виду?

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

Каждый кандидат упорядочивает список компаний в порядке своих предпочтений, а каждая компания — после поступления заявок — формирует свой порядок предпочтений для кандидатов, подавших заявки. На основании этих предпочтений компании обращаются с предложениями к некоторым из своих кандидатов.

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

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

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

Этот поворот заставляет Раджа отказаться от предложения CluNet и пойти в WebExodus. Лишившись практиканта, CluNet предлагает работу одному из запасных кандидатов, который мгновенно отменяет свое предыдущее согласие на предложение мегакорпорации Babelsoft. Ситуация набирает обороты и постепенно выходит из-под контроля.

С другого направления все выглядит ничуть не лучше, а то и хуже. Допустим, подруге Раджа по имени Челси было назначено отправиться в Babelsoft. Но услышав историю Раджа, она звонит в WebExodus и говорит: «Знаете, я бы предпочла провести это лето в вашей фирме, а не в Babelsoft».

Отдел кадров WebExodus охотно верит; более того, заглянув в заявку Челси, они понимают, что она перспективнее другого студента, у которого уже запланирована летняя практика. И если компания WebExodus не отличается особой деловой принципиальностью, она найдет способ отозвать свое предложение другому студенту и возьмет Челси на его место.

Такие ситуации быстро порождают хаос, и многие участники — как кандидаты, так и наниматели — могут оказаться недовольны как самим процессом, так и его результатом. Что же пошло не так? Одна из основных проблем заключается в том, что процесс не является саморегулируемым; если участникам разрешено произвольно действовать, исходя из их собственных интересов, весь процесс может быть нарушен.

Пожалуй, вы бы предпочли следующую, более устойчивую ситуацию, в которой сами личные интересы участников предотвращают отмену и перенаправление предложений. Допустим, другой студент, который должен был провести лето в CluNet, звонит в WebExodus и сообщает, что он бы предпочел поработать на них.

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

Итак, вот как выглядел вопрос, заданный Гейлом и Шепли: можно ли для имеющегося набора предпочтений по кандидатам и нанимателям распределить кандидатов по нанимателям так, чтобы для каждого нанимателя E и каждого кандидата A, который не был принят на работу к E, выполнялось по крайней мере одно из следующих двух условий?

1. Каждый из кандидатов, принятых E на работу, с его точки зрения, предпочтительнее A; или
2. С точки зрения A, его текущая ситуация предпочтительнее работы на нанимателя E.

Если этот критерий выполняется, то результат устойчив (стабилен): личные интересы сторон предотвратят закулисные дополнительные договоренности между кандидатами и нанимателями.

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

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