Věta o venkovských nemocnicích - Rural hospitals theorem

The věta o venkovských nemocnicích (RHT) je základní teorém v teorii stabilní shoda Uvažuje o problému párování lékaři na nemocnice pro pobyt, kde je každý lékař přiřazen k jedné nemocnici, ale každá nemocnice má několik pozic pro lékaře. Celkový počet pozic je větší než celkový počet lékařů, takže některé nemocnice nevyhnutelně zůstávají s neobsazenými pozicemi. Obvykle, venkovské nemocnice jsou méně vyhledávané než městské nemocnice, takže často zůstávají na mnoha prázdných pozicích. To vyvolalo otázku, zda lze změnit mechanismus používaný k přiřazování lékařů k nemocnicím, aby se těmto venkovským nemocnicím pomohlo.[1]

The věta o venkovských nemocnicích odpovídá na tuto otázku negativně za předpokladu, že všechny preference jsou přísné (tj. žádný lékař není lhostejný mezi dvěma nemocnicemi a žádná nemocnice není lhostejná mezi dvěma lékaři). Věta má dvě části:

  1. Sada přiřazených lékařů a počet obsazených pozic v každé nemocnici jsou stejné ve všech stabilních shodách.
  2. Každá nemocnice, která má nějaké prázdné pozice ve stabilním párování, přijímá přesně stejnou sadu lékařů Všechno stabilní párování.

Jinými slovy: změna mechanismu párování (pokud vytvoří stabilní párování) venkovským nemocnicím nijak nepomůže: nedostanou více lékařů ani lepší lékaře.

Věta je robustní v oboustranném porovnávání, protože platí pro párování párů a mnoho-k-jednomu a lze ji rozšířit na párování párů.[2]

Dějiny

Zvláštní případ věty, kdy má každá nemocnice pouze jednu pozici („stabilní manželství“), prokázali počítačoví vědci McVitie a Wilson v roce 1970.[3]

V 80. letech ekonom Alvin E. Roth prokázal dvě části úplné věty ve dvou příslušných dokumentech.[4][1]

Důkaz zvláštního případu

Cyklus délky 4 ve stabilním porovnávacím grafu

Prokážeme teorému pro speciální případ, kdy má každá nemocnice pouze jednu pozici. V tomto případě část 1 říká, že všechny stabilní párování mají stejnou sadu spárovaných nemocnic a stejnou sadu spárovaných lékařů a část 2 je triviální.

Je užitečné si nejprve představit, jak vypadají různé stabilní shody (viz grafy vpravo). Zvažte dvě různé stabilní shody, A a B. Zvažte lékaře d0 jejichž nemocnice v A a B se liší. Protože předpokládáme přísné preference, d0 dává přednost buď své nemocnici v A, nebo své nemocnici v B; Předpokládejme, že w.l.o.g. že dává přednost své nemocnici v B a tuto nemocnici označuje h1. To vše shrnuje zelená šipka od d0 na h1.

Cyklus délky 6

Nyní, protože shoda A je stabilní, h1 nutně preferuje svého lékaře v A před d0 (v opačném případě d0 a h1 by stabilizoval odpovídající A); označte tohoto lékaře d2a označují preference h1 červenou šipkou od h1 na d2.

Podobně, protože shoda B je stabilní, d2 dává přednost své nemocnici v B před h1; označte tuto nemocnici h3a preferenci označíme zelenou šipkou od d2 na h3.

Protože počet lékařů a nemocnic je konečný, v určitém okamžiku musí červená šipka z nemocnice přistát d0, uzavření směrovaného cyklu v grafu. Graf vpravo nahoře ukazuje cyklus délky 4; graf vpravo dole ukazuje cyklus délky 6. V těchto cyklech poukazují všichni lékaři na nemocnice, které upřednostňují a jsou přizpůsobeny v B, a všechny nemocnice ukazují na lékaře, kterým dávají přednost a jsou přizpůsobeny v A.

Nekonečný cyklus

Nyní zvažte, co se stane, když lékař d0 v A nemá obdoby. Nyní se cyklus nemůže uzavřít, protože nelze přiřadit žádnou nemocnici d0 v A. Je také nemožné, aby nějaká nemocnice h3 v tomto cyklu je v A bezkonkurenční, protože pokud by nemocnice dávala přednost bezkonkurenčnímu porovnání s lékařem v B, pak by B nemohla být stabilní. To znamená, že máme nekonečný cyklus, který nemůže být. Proto, pokud d0 je bezkonkurenční v A, musí být bezkonkurenční také v B.

Totéž platí pro nemocnice: jakákoli nemocnice, která nemá obdoby v A, musí být neporovnatelná také v B.

Viz také

Reference

  1. ^ A b Roth, Alvin E. (01.03.1986). „O přidělování obyvatel do venkovských nemocnic: obecný majetek dvoustranných odpovídajících trhů“. Econometrica. 54 (2): 425–427. doi:10.2307/1913160. ISSN  0012-9682. JSTOR  1913160.
  2. ^ Klijn, Flip; Yazıcı, Ayşe (01.10.2014). „Věta o venkovských nemocnicích od mnoha k mnoha'" (PDF). Journal of Mathematical Economics. 54: 63–73. doi:10.1016 / j.jmateco.2014.09.003. ISSN  0304-4068.
  3. ^ McVitie, D. G .; Wilson, L. B. (01.09.1970). "Stabilní přiřazení manželství pro nerovné sady". BIT Numerická matematika. 10 (3): 295–309. doi:10.1007 / BF01934199. ISSN  1572-9125. S2CID  122319782.
  4. ^ Roth, Alvin (1984). „Vývoj trhu práce pro lékařské stážisty a obyvatele: případová studie z teorie her“. Journal of Political Economy. 92 (6): 991–1016. doi:10.1086/261272.