Теорема о сельских больницах - Rural hospitals theorem

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

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

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

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

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

История

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

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

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

Цикл длины 4 в графе стабильных паросочетаний

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

Полезно сначала визуализировать, как выглядят различные стабильные сопоставления (см. Графики справа). Рассмотрим два разных стабильных соответствия: A и B. Рассмотрим врача. d₀ чьи больницы в A и B разные. Поскольку мы предполагаем строгие предпочтения, d₀ предпочитает либо свою больницу в А, либо свою больницу в Б; предположим w.l.o.g. что он предпочитает свою больницу в B, и обозначает эту больницу час₁. Обо всем этом свидетельствует зеленая стрелка от d₀ к час₁.

Цикл длины 6

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

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

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

Бесконечный цикл

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

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

Смотрите также

использованная литература

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

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

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

[3] McVitie, D.G .; Уилсон, Л. Б. (1970-09-01). «Стабильное назначение брака для неравных пар». BIT вычислительная математика. 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]