El teorema de los hospitales rurales ( RHT ) es un teorema fundamental en la teoría del emparejamiento estable . Considera el problema de emparejar médicos con hospitales para la residencia , donde cada médico se empareja con un solo hospital pero cada hospital tiene varios puestos para médicos. El número total de puestos es mayor que el número total de médicos, por lo que algunos hospitales inevitablemente permanecen con puestos vacantes. Por lo general, los hospitales rurales son menos solicitados que los hospitales urbanos, por lo que a menudo permanecen con muchos puestos vacantes. Esto planteó la cuestión de si el mecanismo utilizado para emparejar médicos con hospitales se puede cambiar para ayudar a estos hospitales rurales. [1]
El teorema de los hospitales rurales responde a esta pregunta de forma negativa, suponiendo que todas las preferencias son estrictas (es decir, ningún médico es indiferente entre dos hospitales y ningún hospital es indiferente entre dos médicos). El teorema tiene dos partes:
En otras palabras: cambiar el mecanismo de emparejamiento (siempre que produzca emparejamientos estables) no ayudará de ninguna manera a los hospitales rurales: no recibirán más médicos ni mejores médicos.
El teorema es robusto en el emparejamiento bilateral, ya que se aplica a emparejamientos uno a uno y muchos a uno, y puede extenderse a emparejamientos muchos a muchos. [2]
Un caso especial del teorema donde cada hospital tiene sólo una posición ("matrimonio estable") fue demostrado por los científicos informáticos McVitie y Wilson en 1970. [3]
En la década de 1980, el economista Alvin E. Roth demostró las dos partes del teorema completo en dos artículos respectivos. [4] [1]
Probaremos el teorema para el caso especial en el que cada hospital tiene solo un puesto. En este caso, la Parte 1 dice que todos los emparejamientos estables tienen el mismo conjunto de hospitales emparejados y el mismo conjunto de médicos emparejados, y la Parte 2 es trivial.
Es útil visualizar primero cómo se ven los diferentes emparejamientos estables (consulte los gráficos de la derecha). Considere dos emparejamientos estables diferentes, A y B. Considere un médico d 0 cuyos hospitales en A y B son diferentes. Como suponemos preferencias estrictas, d 0 prefiere su hospital en A o su hospital en B; supongamos wlog que prefiere su hospital en B y denotemos este hospital por h 1 . Todo esto se resume con la flecha verde de d 0 a h 1 .
Ahora bien, dado que la coincidencia A es estable, h 1 necesariamente prefiere a su médico en A sobre d 0 (de lo contrario, d 0 y h 1 desestabilizarían la coincidencia A); denotemos a este médico con d 2 y denotemos la preferencia de h 1 con una flecha roja desde h 1 hasta d 2 .
De manera similar, dado que la coincidencia B es estable, d 2 prefiere su hospital en B sobre h 1 ; denote este hospital como h 3 , y denote la preferencia con una flecha verde desde d 2 a h 3 .
Como el número de médicos y hospitales es finito, en algún momento la flecha roja de un hospital debe caer en d 0 , cerrando un ciclo dirigido en el gráfico. El gráfico de la parte superior derecha muestra un ciclo de longitud 4; el gráfico de la parte inferior derecha muestra un ciclo de longitud 6. En estos ciclos, todos los médicos señalan los hospitales que prefieren y con los que están emparejados en B, y todos los hospitales señalan los médicos que prefieren y con los que están emparejados en A.
Ahora, pensemos en lo que ocurre cuando el médico d 0 no tiene pareja en A. Ahora bien, el ciclo no puede cerrarse, ya que ningún hospital puede tener pareja con d 0 en A. También es imposible que algún hospital h 3 en este ciclo no tenga pareja en A, ya que si el hospital prefiriera no tener pareja que tener pareja con su médico en B, entonces B no podría haber sido estable. Esto significa que tenemos un ciclo infinito, lo cual no puede serlo. Por lo tanto, si d 0 no tiene pareja en A, tampoco debe tener pareja en B.
Lo mismo ocurre con los hospitales: cualquier hospital que no tenga emparejamiento en A, debe no tener emparejamiento en B también.