Задача о больницах и резидентах

Ключевые слова и синонимы

Задача о поступлении в колледж; задача о поступлении в университет; задача об устойчивых поступлениях; задача об устойчивых назначениях; задача об устойчивых b-паросочетаниях

Постановка задачи

Экземпляр [math]\displaystyle{ I }[/math] задачи о больницах и резидентах (HR) [5, 6, 14] включает множество [math]\displaystyle{ R = \{ r_1, ..., r_n \} }[/math] резидентов и множество [math]\displaystyle{ H = \{ h_1, ..., h_m \} }[/math] больниц. Каждая больница [math]\displaystyle{ h_j \in H }[/math] имеет кадровый потенциал в виде целого положительного числа, обозначаемый [math]\displaystyle{ c_j }[/math]. Также каждый резидент [math]\displaystyle{ r_i \in R }[/math] имеет список предпочтений, в котором он ранжирует подмножество H в строгом порядке. Пара [math]\displaystyle{ (r_i, h_j) \in R \times H }[/math] называется приемлемой, если [math]\displaystyle{ h_j }[/math] содержится в списке предпочтений [math]\displaystyle{ r_i }[/math]; в этом случае говорят, что [math]\displaystyle{ r_i }[/math] считает [math]\displaystyle{ h_j }[/math] приемлемой. Аналогично, каждая больница [math]\displaystyle{ h_j \in H }[/math] имеет список предпочтений, в котором она располагает в строгом порядке тех резидентов, которые считают эту больницу приемлемой. Пусть имеются три любых агента [math]\displaystyle{ x, y, z \in R \cup H }[/math]; можно сказать, что x предпочитает агента y агенту z, если x находит приемлемым их обоих и y предшествует z в списке предпочтений x. Пусть [math]\displaystyle{ C = \sum_{h_j \in H} c_j }[/math].

Обозначим за A множество допустимых пар в [math]\displaystyle{ I }[/math], L = |A|. Назначение M является подмножеством A. Если [math]\displaystyle{ (r_i, h_j) \in M }[/math], то говорят, что резидент [math]\displaystyle{ r_i }[/math] назначен больнице [math]\displaystyle{ h_j }[/math], а больница [math]\displaystyle{ h_j }[/math] – резиденту [math]\displaystyle{ r_i }[/math]. Для каждого [math]\displaystyle{ q \in R \cup H }[/math] множество назначенных q в M обозначается M(q). Если [math]\displaystyle{ r_i \in R }[/math] и [math]\displaystyle{ M(r_i) = \empty }[/math], то считается, что [math]\displaystyle{ r_i }[/math] не назначен, в противном случае [math]\displaystyle{ r_i }[/math] назначен. Аналогично, любая больница [math]\displaystyle{ h_j \in H }[/math] является недоукомплектованной, полной или переукомплектованной, если [math]\displaystyle{ |M(h_j)| }[/math] меньше, равна или больше [math]\displaystyle{ c_j }[/math], соответственно.

Паросочетанием M называется назначение, такое, что [math]\displaystyle{ |M(r_i)| \le 1 }[/math] для каждого [math]\displaystyle{ r_i \in R }[/math] и [math]\displaystyle{ |M(h_j)| \le c_j }[/math] для каждого [math]\displaystyle{ h_j \in H }[/math] (т. е. ни один резидент не назначен в неподходящую больницу, каждый резидент назначен не более чем в одну больницу и ни одна больница не переукомплектована). Для удобства обозначений, если даны паросочетание M и резидент [math]\displaystyle{ r_i \in R }[/math] такой, что [math]\displaystyle{ M(r_i) \ne \empty }[/math], то в случаях, когда это не вызывает двусмысленности, обозначение [math]\displaystyle{ M(r_i) }[/math] также используется для обозначения единственного члена [math]\displaystyle{ M(r_i) }[/math].

Пара [math]\displaystyle{ (r_i, h_j) \in A \setminus M }[/math] блокирует паросочетание M (или является блокирующей парой для M), если относительно M выполняются следующие условия:

1. резидент [math]\displaystyle{ r_i }[/math] не назначен или предпочитает [math]\displaystyle{ M(r_i) }[/math] больницу [math]\displaystyle{ h_j }[/math];

2. больница [math]\displaystyle{ h_j }[/math]недоукомплектована или предпочитает резидента [math]\displaystyle{ r_i }[/math] хотя бы одному члену [math]\displaystyle{ M(h_j) }[/math] (или обоим).

Паросочетание M называется устойчивым, если оно не допускает ни одной блокирующей пары. Пусть дан экземпляр [math]\displaystyle{ I }[/math] из HR; задача заключается в том, чтобы найти устойчивое паросочетание в [math]\displaystyle{ I }[/math].

Основные результаты

Впервые задача HR была определена Гэйлом и Шепли [5] под названием «Задача о поступлении в колледж». В своей основополагающей статье авторы рассматривают классическую задачу о стабильных браках (SM; см. Стабильный брак и Оптимальный стабильный брак), которая является частным случаем HR, в котором [math]\displaystyle{ n = m, A = R \times H }[/math], и [math]\displaystyle{ c_j = 1 }[/math] для всех [math]\displaystyle{ h_j \in H }[/math]; в этом частном случае вместо резидентов и больниц мы имеем дело с мужчинами и женщинами, соответственно. Гэйл и Шепли показали, что каждый экземпляр [math]\displaystyle{ I }[/math] задачи HR допускает по крайней мере одно устойчивое паросочетание. Доказательство этого результата носит конструктивный характер, то есть описывается алгоритм нахождения устойчивого паросочетания в I. Этот алгоритм получил название алгоритма Гэйла-Шепли [1].

 [math]\displaystyle{ M := \empty }[/math]
 while (некоторый резидент [math]\displaystyle{ r_i }[/math] не назначен and [math]\displaystyle{ r_i }[/math] имеет непустой список) { 
   [math]\displaystyle{ h_j }[/math] := первая больница в списке [math]\displaystyle{ r_i }[/math]; 
   /* [math]\displaystyle{ r_i }[/math] подает заявку в hj */ 
   [math]\displaystyle{ M := M \cup \{ (r_i, h_j) \} }[/math]; 
   if ([math]\displaystyle{ h_j }[/math] переукомплектована) {
     [math]\displaystyle{ r_k }[/math] := худший резидент в [math]\displaystyle{ M(h_j) }[/math] согласно списку [math]\displaystyle{ h_j }[/math];
     [math]\displaystyle{ M := M \sub \{ (r_k, h_j) \}  }[/math]; 
   } 
   if ([math]\displaystyle{ h_j }[/math] полна) {
     [math]\displaystyle{ r_k }[/math] := худший резидент в [math]\displaystyle{ M(h_j) }[/math] согласно списку [math]\displaystyle{ h_j }[/math];
     for (каждого преемника [math]\displaystyle{ r_l }[/math] резидента [math]\displaystyle{ r_k }[/math] в списке [math]\displaystyle{ h_j }[/math]) 
       удалить пару [math]\displaystyle{ (r_l, h_j) }[/math]
   } 
 } 

Рисунок 1. Алгоритм Гэйла-Шепли для задачи HR

Расширенная версия алгоритма Гэйла/Шепли для задачи HR показана на рис. 1. Алгоритм включает в себя последовательность операций apply (подать заявку) и delete (удалить). На каждой итерации цикла while некоторый не назначенный резидент [math]\displaystyle{ r_i }[/math] с непустым списком предпочтений подает заявку в первую больницу [math]\displaystyle{ h_j }[/math] в его списке и становится временно назначенным в [math]\displaystyle{ h_j }[/math] (впоследствии это назначение может быть отменено). Если в результате этого назначения больница [math]\displaystyle{ h_j }[/math] становится переукомплектованной, то она отказывается от худшего из назначенных резидентов [math]\displaystyle{ r_k }[/math]. Далее, если больница [math]\displaystyle{ h_j }[/math] полна (независимо от того, была ли она переукомплектована ранее на той же итерации цикла), то для каждого резидента [math]\displaystyle{ r_l }[/math], которого [math]\displaystyle{ h_j }[/math] считает менее желательным, чем его худший резидент [math]\displaystyle{ r_k }[/math], алгоритм удаляет пару [math]\displaystyle{ (r_l, h_j) }[/math], что включает удаление [math]\displaystyle{ h_j }[/math] из списка предпочтений [math]\displaystyle{ r_l }[/math] и наоборот.

Поскольку вышеописанный алгоритм предполагает подачу резидентами заявок в больницы, он стал известен как алгоритм Гэйла-Шепли, ориентированный на резидентов, или алгоритм RGS [6, раздел 1.6.3]. Алгоритм RGS завершается нахождением устойчивого паросочетания для заданного экземпляра задачи HR [5, 6, теорема 1.6.2]. При подходящем выборе структур данных (расширяя те, что были описаны в работе [6, раздел алгоритм RGS может быть реализован за время O(L). Он позволяет получить устойчивое паросочетание, которое одновременно является наилучшим для всех резидентов [5,6, теорема 1.6.2]. Эти наблюдения можно обобщить следующим образом.

Теорема 1. Для заданного экземпляра задачи HR алгоритм RGS за время O(L) строит уникальное устойчивое паросочетание, в котором каждый назначенный резидент получает лучшую больницу, которую он мог бы получить в любом устойчивом паросочетании, в то время как каждый не назначенный резидент не назначен в каждом устойчивом паросочетании.

Аналог алгоритма RGS, носящий название ориентированного на больницы алгоритма Гэйла-Шепли, или сокращенно HGS-алгоритм [6, раздел 1.6.2], позволяет получить единственное устойчивое паросочетание, которое аналогичным образом удовлетворяет свойству оптимальности для больниц [6, теорема 1.6.1]. Хотя для заданного экземпляра [math]\displaystyle{ I }[/math] задачи HR может существовать несколько устойчивых паросочетаний, для всех устойчивых паросочетаний в [math]\displaystyle{ I }[/math] сохраняются некоторые ключевые структурные свойства, касающиеся неназначенных резидентов и недоукомплектованных больниц.

Теорема 2. Для заданного экземпляра задачи HR:

• во всех устойчивых паросочетаниях назначаются одни и те же резиденты;

• во всех устойчивых паросочетаниях каждой больнице назначается одно и то же количество резидентов;

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

Эти результаты известны под общим названием «Теорема о сельских больницах» (подробнее см. в [6, раздел 1.6.4]. Кроме того, множество устойчивых паросочетаний в [math]\displaystyle{ I }[/math] образует дистрибутивную решетку при естественном отношении доминирования [6, раздел 1.6.5].

Применение

Практические приложения задачи HR широко распространены. В первую очередь они возникают в контексте централизованных автоматизированных схем подбора кандидатов на должности (например, студентов-медиков в больницы, выпускников школ в университеты, учеников начальных школ в средние школы). Возможно, самым известным примером такой схемы является Национальная программа подбора резидентов (National Resident Matching Program, NRMP) в США [16], которая ежегодно распределяет около 31 000 студентов-медиков (называемых резидентами) на их первые должности в больницах, учитывая предпочтения резидентов по отношению к больницам и наоборот, а также кадровый потенциал больниц. Аналоги программы NRMP существуют и в других странах, включая Канаду [17], Шотландию [18] и Японию [19]. Эти схемы подбора в основном используют расширения алгоритма RGS для задачи HR.

Централизованные схемы подбора, в значительной степени основанные на алгоритме HR, встречаются и в других практических контекстах, например, при распределении на педагогическую практику в Нью-Йорке [1], наборе преподавателей во Франции [3] и приеме в университеты в Испании [12].

Расширения задачи HR

Одно из ключевых расширений HR, имеющее большое практическое значение, возникает в том случае, когда экземпляр задачи может включать в себя набор пар, каждая из которых представляет совместный список предпочтений по парам больниц (например, для того, чтобы члены данной пары могли быть расположены географически близко друг к другу). Расширение HR, в котором могут участвовать пары, обозначается HRC; определение стабильности в HRC является естественным расширением определения стабильности в HR (формальное определение HRC см. в [6, раздел 1.6.6]). Известно, что экземпляр задачи HRC не обязательно может выдавать устойчивое паросочетание (см. [6, раздел 1.6.6] и [14, раздел 5.4.3]). Более того, проблема решения вопроса о том, допускает ли экземпляр HRC устойчивое паросочетание, является NP-полной [13].

HR можно рассматривать как обобщение задачи SM вида «от многих к одному». Дальнейшим обобщением SM является задача нахождения устойчивого паросочетания в модели «от многих к многим», в которой резиденты и больницы могут получать множественные назначения с учетом ограничений на кадровый потенциал. В этом случае резиденты и больницы чаще всего называются работниками и фирмами соответственно. Существуют две основные вариации задачи нахождения устойчивого паросочетания «от многих к многим», в которых либо (1) работники ранжируют приемлемые фирмы в порядке предпочтения и наоборот, либо (2) работники ранжируют приемлемые подмножества фирм в порядке предпочтения и наоборот. Предыдущие работы, относящиеся к обеим моделям, рассмотрены в [4].

Другие варианты задачи HR возникают в случаях, если списки предпочтений включают связи. Это расширение также очень важно с практической точки зрения, поскольку может быть нереалистично ожидать, что популярная больница расположит большое количество претендентов в строгом порядке, особенно если она не учитывает группы претендентов. Расширение задачи HR, в котором списки предпочтений могут включать связи, обозначается HRT. В этом контексте возникают три естественных определения устойчивости, так называемые слабая устойчивость, сильная устойчивость и сверхустойчивость (формальные определения этих понятий см. в [8]). Известно, что слабоустойчивые паросочетания в экземпляре [math]\displaystyle{ I }[/math] задачи HRT могут иметь различные размеры, и проблема нахождения слабоустойчивого паросочетания максимальной мощности является NP-полной (подробнее об этом см. Устойчивое бракосочетание со связями и неполными списками). С другой стороны, в отличие от случая слабой устойчивости, сверхустойчивое паросочетание не обязательно должно существовать в I, хотя существует алгоритм с временем выполнения O(L) для поиска такого паросочетания в случае, если таковое существует. Аналогичные результаты имеют место и в случае сильной устойчивости – в этом случае алгоритм с временем выполнения [math]\displaystyle{ O(L^2) }[/math] [8] был улучшен алгоритмом с временем выполнения O(CL) [10] и распространен на случай «от многих к многим» [11]. Кроме того, аналоги теоремы о сельских больницах справедливы для HRT при каждом из критериев сверхустойчивости и сильной устойчивости [7, 15].

Дальнейшее обобщение задачи HR возникает в случае, когда каждая больница может быть разделена на несколько отделений, каждое из которых имеет свой кадровый потенциал, а резиденты ранжируют отдельные отделения в порядке предпочтения. Этот вариант моделируется задачей распределения студентов по проектам [2]. Наконец, задача об устойчивых объектах [9] является недвухсторонним расширением HR, в котором существует единственный набор агентов, каждый из которых имеет собственную емкость (кадровый потенциал) и ранжирует подмножество других в порядке предпочтения.

Открытые вопросы

Было сформулировано несколько приближенных алгоритмов поиска слабоустойчивого паросочетания максимальной мощности для экземпляра HRT, в котором каждая больница имеет кадровый потенциал 1 (подробнее об этом см. Устойчивое бракосочетание со связями и неполными списками). Остается открытым вопрос о расширении этих алгоритмов или о формулировании эффективных эвристик для случая HRT с произвольными значениями кадрового потенциала. Эта задача особенно актуальна с практической точки зрения, поскольку, как уже отмечалось в разделе «Применение», больницы могут захотеть включить связи в свои списки предпочтений. В этом случае слабая устойчивость является наиболее часто используемым критерием устойчивости, поскольку гарантируется существование такого паросочетания. Попытка обеспечить совпадение для как можно большего числа резидентов мотивирует на поиск больших слабоустойчивых паросочетаний.

Ссылка на код

Реализации алгоритмов RGS и HGS для задачи HR на языке Ada можно найти по следующему адресу: http://www.dcs.gla.ac.uk/research/algorithms/stable.

См. также

• Оптимальное устойчивое бракосочетание
• Ранжированное паросочетание
• Устойчивое бракосочетание
• Устойчивое бракосочетание и дискретный выпуклый анализ
• Устойчивое бракосочетание со связями и неполными списками
• Задача об устойчивом разбиении

Литература

1. Abdulkadiroglu, A., Pathak, P.A., Roth, A.E.: The New York City high school match. Am. Economic. Rev. 95(2), 364-367 (2006)

2. Abraham, D.J., Irving, R.W., Manlove, D.F.: Two algorithms for the Student-Project allocation problem. J. Discret. Algorithms 5(1),73-90(2007)

3. BaTou, M., Balinski, M.: Student admissions and faculty recruitment. Theor. Comput. Sci. 322(2), 245-265 (2004)

4. Bansal, V., Agrawal, A., Malhotra, V.S.: Stable marriages with multiple partners: efficient search for an optimal solution. In: Proceedings of ICALP '03: the 30th International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 2719, pp. 527-542. Springer, Berlin (2003)

5. Gale, D., Shapley, L.S.: College admissions and the stability of marriage. Am. Math. Month. 69,9-15 (1962)

6. Gusfield, D., Irving, R.W.: The Stable Marriage Problem: Structure and Algorithms. MIT Press, Cambridge (1989)

7. Irving, R.W., Manlove, D.F., Scott, S.: The Hospitals/Residents problem with Ties. In: Proceedings of SWAT 2000: the 7th Scandinavian Workshop on Algorithm Theory. Lecture Notes in Computer Science, vol. 1851, pp. 259-271. Springer, Berlin (2000)

8. Irving, R.W., Manlove, D.F., Scott, S.: Strong stability in the Hospitals/Residents problem. In: Proceedings of STACS 2003: the 20th Annual Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 2607, pp. 439-450. Springer, Berlin (2003)

9. Irving, R.W., Scott, S.: The stable fixtures problem - a many-to-many extension of stable roommates. Discret. Appl. Math. 155, 2118-2129(2007)

10. Kavitha, T., Mehlhorn, K., Michail, D., Paluch, K.: Strongly stable matchings in time O(nm) and extension to the Hospitals-Residents problem. In: Proceedings of STACS 2004: the 21st International Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 2996, pp. 222-233. Springer, Berlin (2004)

11. Malhotra, V.S.: On the stability of multiple partner stable marriages with ties. In: Proceedings of ESA '04: the 12th Annual European Symposium on Algorithms. Lecture Notes in Computer Science, vol. 3221, pp. 508-519. Springer, Berlin (2004)

12. Romero-Medina, A.: Implementation of stable solutions in a restricted matching market. Rev. Economic. Des. 3(2), 137-147 (1998)

13. Ronn, E.: NP-complete stable matching problems. J. Algorithms 11, 285-304 (1990)

14. Roth, A.E., Sotomayor, M.A.O.: Two-sided matching: a study in game-theoretic modeling and analysis. Econometric Society Monographs, vol. 18. Cambridge University Press, Cambridge, UK (1990)

15. Scott, S.: A study of stable marriage problems with ties. Ph.D. thesis, University of Glasgow, Dept. Comput. Sci. (2005)

16. http://www.nrmp.org/(National Resident Matching Program website)

17. http://www.carms.ca (Canadian Resident Matching Service website)

18. http://www.nes.scot.nhs.uk/sfas/(Scottish Foundation Allocation Scheme website)

19. http://www.jrmp.jp (Japan Resident Matching Program website)