En matemáticas , economía e informática , el problema del matrimonio estable (también problema de coincidencia estable ) es el problema de encontrar una coincidencia estable entre dos conjuntos de elementos de igual tamaño, dado un orden de preferencias para cada elemento. Una coincidencia es una biyección de los elementos de un conjunto a los elementos del otro conjunto. Una coincidencia no es estable si:
En otras palabras, una coincidencia es estable cuando no existe ninguna pareja ( A , B ) que se prefiera entre sí a su pareja actual según la coincidencia.
El problema del matrimonio estable se ha planteado de la siguiente manera:
Dados n hombres y n mujeres, donde cada persona ha clasificado a todos los miembros del sexo opuesto en orden de preferencia, casar a hombres y mujeres de manera que no haya dos personas de sexo opuesto que prefieran tenerse entre sí antes que a sus parejas actuales. . Cuando no existen tales parejas de personas, el conjunto de matrimonios se considera estable.
La existencia de dos clases que deben emparejarse (hombres y mujeres heterosexuales en este ejemplo) distingue este problema del problema de los compañeros de cuarto estables .
Los algoritmos para encontrar soluciones al problema del matrimonio estable tienen aplicaciones en una variedad de situaciones del mundo real, siendo quizás la más conocida la asignación de estudiantes de medicina graduados a sus primeras citas en el hospital. [1] En 2012, el Premio Nobel de Ciencias Económicas fue otorgado a Lloyd S. Shapley y Alvin E. Roth "por la teoría de las asignaciones estables y la práctica del diseño de mercado". [2]
Una aplicación importante y a gran escala del matrimonio estable es la asignación de usuarios a servidores en un gran servicio de Internet distribuido. [3] Miles de millones de usuarios acceden a páginas web, vídeos y otros servicios en Internet, lo que requiere que cada usuario sea asignado a uno de (potencialmente) cientos de miles de servidores en todo el mundo que ofrecen ese servicio. Un usuario prefiere servidores que sean lo suficientemente próximos como para proporcionar un tiempo de respuesta más rápido para el servicio solicitado, lo que resulta en un orden preferencial (parcial) de los servidores para cada usuario. Cada servidor prefiere atender a los usuarios que puede con un costo menor, lo que resulta en un orden preferencial (parcial) de usuarios para cada servidor. Las redes de entrega de contenido que distribuyen gran parte del contenido y servicios del mundo resuelven este gran y complejo problema de unión estable entre usuarios y servidores cada decenas de segundos para permitir que miles de millones de usuarios se conecten con sus respectivos servidores que pueden proporcionar las páginas web y videos solicitados. u otros servicios. [3]
El algoritmo Gale-Shapley para emparejamiento estable se utiliza para asignar rabinos que se gradúan del Hebrew Union College a congregaciones judías. [4]
En general, puede haber muchas coincidencias estables diferentes. Por ejemplo, supongamos que hay tres hombres (A,B,C) y tres mujeres (X,Y,Z) que tienen preferencias de:
Hay tres soluciones estables para este acuerdo coincidente:
Los tres son estables, porque la inestabilidad requiere que ambos participantes estén más contentos con un partido alternativo. Darle a un grupo sus primeras opciones garantiza que los partidos sean estables porque no estarían contentos con cualquier otro partido propuesto. Darles a todos su segunda opción garantiza que una de las partes no agradará cualquier otro partido. En general, a la familia de soluciones para cualquier instancia del problema del matrimonio estable se le puede dar la estructura de una red distributiva finita , y esta estructura conduce a algoritmos eficientes para varios problemas sobre matrimonios estables. [5]
En un caso uniformemente aleatorio del problema del matrimonio estable con n hombres y n mujeres, el número promedio de coincidencias estables es asintóticamente . [6] En un caso de matrimonio estable elegido para maximizar el número de coincidencias estables diferentes, este número es una función exponencial de n . [7] Contar el número de coincidencias estables en una instancia determinada es #P-completo . [8]
En 1962, David Gale y Lloyd Shapley demostraron que, para un número igual de hombres y mujeres, siempre es posible resolver el problema del matrimonio estable y hacer que todos los matrimonios sean estables. Presentaron un algoritmo para hacerlo. [9] [10]
El algoritmo Gale-Shapley (también conocido como algoritmo de aceptación diferida) implica una serie de "rondas" (o " iteraciones "):
Se garantiza que este algoritmo producirá un matrimonio estable para todos los participantes en el tiempo donde sea el número de hombres o mujeres. [11]
Entre todas las posibles coincidencias estables, siempre se obtiene la que es mejor para todos los hombres entre todas las coincidencias estables y la peor para todas las mujeres. [12]
Es un mecanismo veraz desde el punto de vista de los hombres (el lado proponente), es decir, ningún hombre puede conseguir una mejor combinación tergiversando sus preferencias. Además, el algoritmo GS es incluso a prueba de estrategias de grupo para los hombres, es decir, ninguna coalición de hombres puede coordinar una tergiversación de sus preferencias de modo que todos los hombres de la coalición estén estrictamente en mejor situación. [13] Sin embargo, es posible que alguna coalición tergiverse sus preferencias de modo que algunos hombres estén en mejor situación y otros conserven la misma pareja. [14] El algoritmo GS no es veraz para las mujeres (el lado de la revisión): cada mujer puede tergiversar sus preferencias y obtener una mejor coincidencia.
El teorema de los hospitales rurales se refiere a una variante más general del problema de emparejamiento estable, como el que se aplica al problema de emparejar médicos con puestos en los hospitales, que difiere en las siguientes formas de la forma básica n -to- n del problema del matrimonio estable:
En este caso, la condición de estabilidad es que ninguna pareja no emparejada se prefiera a su situación en el emparejamiento (ya sea que esa situación sea otra pareja o no sea emparejada). Con esta condición, seguirá existiendo una coincidencia estable y el algoritmo de Gale-Shapley aún podrá encontrarla.
Para este tipo de problema de emparejamiento estable, el teorema de los hospitales rurales establece que:
En el emparejamiento estable con indiferencia , algunos hombres pueden ser indiferentes entre dos o más mujeres y viceversa.
El problema de los compañeros de cuarto estables es similar al problema del matrimonio estable, pero se diferencia en que todos los participantes pertenecen a un solo grupo (en lugar de estar divididos en números iguales de "hombres" y "mujeres").
El problema de los hospitales/residentes , también conocido como el problema de admisión a la universidad , se diferencia del problema del matrimonio estable en que un hospital puede aceptar varios residentes, o una universidad puede aceptar una clase entrante de más de un estudiante. Los algoritmos para resolver el problema hospitales/residentes pueden estar orientados a los hospitales (como lo estaba el NRMP antes de 1995) [15] o a los residentes . Este problema fue resuelto, con un algoritmo, en el mismo artículo original de Gale y Shapley, en el que se resolvió el problema del matrimonio estable. [9]
El problema de hospitales/residentes con las parejas permite que el conjunto de residentes incluya parejas que deben ser asignadas juntas, ya sea al mismo hospital o a un par específico de hospitales elegidos por la pareja (por ejemplo, una pareja casada quiere asegurarse de que permanecerán juntos y no quedar atrapados en programas que están lejos unos de otros). La adición de parejas al problema de hospitales/residentes hace que el problema sea NP-completo . [dieciséis]
El problema de asignación busca encontrar una coincidencia en un gráfico bipartito ponderado que tenga el peso máximo. Las coincidencias ponderadas máximas no tienen que ser estables, pero en algunas aplicaciones una coincidencia ponderada máxima es mejor que una estable.
El problema de emparejamiento con contratos es una generalización del problema de emparejamiento, en el que los participantes pueden ser emparejados con diferentes términos de contratos. [17] Un caso especial importante de contratos es el ajuste con salarios flexibles. [18]
