Теорема о сельских больницах

Теорема о сельских больницах ( RHT ) является фундаментальной теоремой теории устойчивого паросочетания . Рассматривается проблема подбора врачей в больницы для ординатуры , где каждый врач прикрепляется к одной больнице, но в каждой больнице есть несколько должностей врачей. Общее количество должностей превышает общее количество врачей, поэтому в некоторых больницах неизбежно остаются незаполненные вакансии. Обычно сельские больницы менее востребованы, чем городские, поэтому в них часто остается много пустующих мест. Это подняло вопрос о том, можно ли изменить механизм подбора врачей в больницы, чтобы помочь этим сельским больницам. ^{[ 1 ]}

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

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

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

Теорема надежна при двустороннем сопоставлении, поскольку она применима к сопоставлениям «один-к-одному» и «многие-к-одному» и может быть распространена на сопоставление «многие-ко-многим». ^{[ 2 ]}

История

Особый случай теоремы, когда каждая больница имеет только одну позицию («стабильный брак»), был доказан учеными-компьютерщиками МакВити и Уилсоном в 1970 году. ^{[ 3 ]}

В 1980-х годах экономист Элвин Э. Рот доказал две части полной теоремы в двух соответствующих статьях. ^{[ 4 ]}^{[ 1 ]}

Доказательство особого случая

Мы докажем теорему для частного случая, когда каждая больница имеет только одну позицию. В этом случае в части 1 говорится, что все стабильные совпадения имеют один и тот же набор подходящих больниц и один и тот же набор подходящих врачей, а часть 2 тривиальна.

Полезно сначала представить себе, как выглядят различные устойчивые паросочетания (см. графики справа). Рассмотрим два разных стабильных соответствия, A и B. Рассмотрим врача d ₀ , больницы которого в A и B разные. Поскольку мы предполагаем строгие предпочтения, d0 _; предпочитает либо свою больницу в А, либо свою больницу в В предположим , что wlog предпочитает свою больницу в B, и обозначим эту больницу h ₁ . Все это суммировано зеленой стрелкой от d ₀ до h ₁ .

Теперь, поскольку сопоставление A стабильно, h ₁ обязательно предпочитает своего доктора в A перед d ₀ (в противном случае d ₀ и h ₁ дестабилизировали бы сопоставление A); обозначим этого врача через d ₂ , а предпочтение h ₁ обозначим красной стрелкой от h ₁ к d ₂ .

Аналогично, поскольку соответствие B стабильно, d ₂ предпочитает больницу в B, а не h ₁ ; обозначим эту больницу h ₃ , а предпочтение обозначим зеленой стрелкой от d ₂ до h ₃ .

Поскольку число врачей и больниц конечно, в какой-то момент красная стрелка от больницы должна попасть в точку d ₀ , замыкая направленный цикл на графике. График в правом верхнем углу показывает цикл длины 4; график в правом нижнем углу показывает цикл длиной 6. В этих циклах все врачи указывают на больницы, которые они предпочитают и которым соответствуют в B, и все больницы указывают на врачей, которые они предпочитают и которым соответствуют в A.

Теперь рассмотрим, что происходит, когда врач d ₀ не имеет совпадения в A. Теперь цикл не может замкнуться, поскольку ни одна больница не может быть сопоставлена с d ₀ в A. Также невозможно, чтобы какая-то больница h ₃ в этом цикле не соответствовала A, поскольку, если бы больница предпочитала быть непревзойденной, чем соответствовать своему врачу в B, тогда B не могла бы быть стабильной. Это значит, что у нас бесконечный цикл, чего быть не может. Следовательно, если d ₀ не имеет совпадений в A, он должен быть непревзойденным и в B.

То же самое верно и для больниц: любая больница, не имеющая аналогов в категории А, должна быть непревзойденной и в категории Б.

См. также

Ссылки

^ Jump up to: ^а ^б Рот, Элвин Э. (1 марта 1986 г.). «О распределении жителей по сельским больницам: общее достояние двусторонних совпадающих рынков». Эконометрика . 54 (2): 425–427. дои : 10.2307/1913160 . ISSN 0012-9682 . JSTOR 1913160 .
^ Клин, Флип; Языджи, Айше (01 октября 2014 г.). «Теорема о сельской больнице «многие-ко-многим» » (PDF) . Журнал математической экономики . 54 : 63–73. дои : 10.1016/j.jmateco.2014.09.003 . ISSN 0304-4068 .
^ МакВити, генеральный директор; Уилсон, Л.Б. (1 сентября 1970 г.). «Стабильное брачное задание для неравных комплектов». БИТ Численная математика . 10 (3): 295–309. дои : 10.1007/BF01934199 . ISSN 1572-9125 . S2CID 122319782 .
^ Рот, Элвин (1984). «Эволюция рынка труда для медицинских интернов и ординаторов: пример теории игр» . Журнал политической экономии . 92 (6): 991–1016. дои : 10.1086/261272 .

[Roth86-1] Jump up to: ^а ^б Рот, Элвин Э. (1 марта 1986 г.). «О распределении жителей по сельским больницам: общее достояние двусторонних совпадающих рынков». Эконометрика . 54 (2): 425–427. дои : 10.2307/1913160 . ISSN 0012-9682 . JSTOR 1913160 .

[2] Клин, Флип; Языджи, Айше (01 октября 2014 г.). «Теорема о сельской больнице «многие-ко-многим» » (PDF) . Журнал математической экономики . 54 : 63–73. дои : 10.1016/j.jmateco.2014.09.003 . ISSN 0304-4068 .

[3] МакВити, генеральный директор; Уилсон, Л.Б. (1 сентября 1970 г.). «Стабильное брачное задание для неравных комплектов». БИТ Численная математика . 10 (3): 295–309. дои : 10.1007/BF01934199 . ISSN 1572-9125 . S2CID 122319782 .

[4] Рот, Элвин (1984). «Эволюция рынка труда для медицинских интернов и ординаторов: пример теории игр» . Журнал политической экономии . 92 (6): 991–1016. дои : 10.1086/261272 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]