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

Задача устойчивых паросочетаний была частично сформулирована в 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.

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

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

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