Задача

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

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

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

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Задача:

  1. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  2. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  3. Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
  4. ЗАДАЧА
  5. ЗАДАЧА: РЕШЕНИЕ
  6. Основные задачи.
  7. в) Задачи
  8. в) Задачи
  9. ПСИХОАНАЛИЗ: ЗАДАЧА
  10. ЗАДАЧА ДВИГАТЕЛЬНАЯ
  11. Основные задачи
  12. Правило решаемой психологической задачи.
  13. Задачи и упражнения
  14. Терапевтическая задача
  15. 3. Задачи и функции социологии