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

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

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

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

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

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

История

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

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

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

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

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

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

Цикл длины 6

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

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

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

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

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

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

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

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

  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.