En matemáticas , economía y ciencias de la computación , el problema del matrimonio estable (también llamado problema de emparejamiento estable ) es el problema de encontrar un emparejamiento estable entre dos conjuntos de elementos de igual tamaño dado un orden de preferencias para cada elemento. Un emparejamiento es una biyección de los elementos de un conjunto a los elementos del otro conjunto. Un emparejamiento no es estable si:
En otras palabras, un emparejamiento es estable cuando no existe ningún par ( A , B ) en el que ambos se prefieran entre sí antes que a su pareja actual en el emparejamiento.
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 los hombres y mujeres juntos de tal manera que no haya dos personas de sexo opuesto que prefieran tenerse entre sí en lugar de a sus parejas actuales. Cuando no hay tales pares de personas, el conjunto de matrimonios se considera estable.
La existencia de dos clases que deben emparejarse entre sí (hombres y mujeres heterosexuales en este ejemplo) distingue este problema del problema de los compañeros de habitación 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 a sus primeras citas en el hospital. [1] En 2012, el Premio Nobel de Economía fue otorgado a Lloyd S. Shapley y Alvin E. Roth "por la teoría de 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 distribuido de Internet. [3] Miles de millones de usuarios acceden a páginas web, vídeos y otros servicios en Internet, lo que requiere que cada usuario se empareje con uno de los (potencialmente) cientos de miles de servidores en todo el mundo que ofrecen ese servicio. Un usuario prefiere servidores que estén lo suficientemente cerca 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 servir a los usuarios que puede con un menor costo, lo que resulta en un orden preferencial (parcial) de usuarios para cada servidor. Las redes de distribución de contenido que distribuyen gran parte del contenido y los servicios del mundo resuelven este gran y complejo problema de matrimonio estable entre usuarios y servidores cada decenas de segundos para permitir que miles de millones de usuarios se emparejen con sus respectivos servidores que pueden proporcionar las páginas web, vídeos u otros servicios solicitados. [3]
El algoritmo Gale-Shapley para correspondencia estable se utiliza para asignar rabinos que se gradúan del Hebrew Union College a congregaciones judías. [4]
En general, puede haber muchas combinaciones estables diferentes. Por ejemplo, supongamos que hay tres hombres (A, B, C) y tres mujeres (X, Y, Z) que tienen preferencias por:
Hay tres soluciones estables para esta disposición coincidente:
Los tres son estables, porque la inestabilidad requiere que ambos participantes estén más contentos con una pareja alternativa. Dar a un grupo sus primeras opciones garantiza que las parejas sean estables porque no estarían contentos con cualquier otra pareja propuesta. Dar a todos su segunda opción garantiza que cualquier otra pareja no le agradaría a una de las partes. 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 una instancia uniformemente aleatoria del problema del matrimonio estable con n hombres y n mujeres, el número promedio de emparejamientos estables es asintóticamente . [6] En una instancia de matrimonio estable elegida para maximizar el número de emparejamientos estables diferentes, este número es una función exponencial de n . [7] Contar el número de emparejamientos estables en una instancia dada es #P-completo . [8]
En 1962, David Gale y Lloyd Shapley demostraron que, para cualquier 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 lograrlo. [9] [10]
El algoritmo Gale-Shapley (también conocido como algoritmo de aceptación diferida) implica una serie de "rondas" (o " iteraciones "):
Este algoritmo garantiza producir un matrimonio estable para todos los participantes en el tiempo donde es el número de hombres o mujeres. [11]
Entre todos los emparejamientos estables posibles, siempre se obtiene el que es mejor para todos los hombres y el 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 obtener una mejor coincidencia para sí mismo tergiversando sus preferencias. Además, el algoritmo GS es incluso a prueba de estrategia 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 los demás hombres conserven la misma pareja. [14] El algoritmo GS no es veraz para las mujeres (el lado revisor): cada mujer puede ser capaz de 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 la que se aplica al problema de emparejar médicos con puestos en hospitales, que difiere de la forma básica n -a- n del problema del matrimonio estable en los siguientes aspectos:
En este caso, la condición de estabilidad es que ninguna pareja no emparejada se prefiera entre sí a su situación en el emparejamiento (ya sea que esa situación sea otra pareja o que no haya pareja). Con esta condición, seguirá existiendo un emparejamiento estable y se podrá encontrar mediante el algoritmo de Gale-Shapley.
Para este tipo de problema de emparejamiento estable, el teorema de los hospitales rurales establece que:
En una relación estable con indiferencia , algunos hombres podrían ser indiferentes entre dos o más mujeres y viceversa.
El problema de los compañeros de habitación estables es similar al problema del matrimonio estable, pero se diferencia en que todos los participantes pertenecen a un único 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 las admisiones universitarias– difiere del problema del matrimonio estable en que un hospital puede aceptar varios residentes, o una universidad puede aceptar una clase de ingreso de más de un estudiante. Los algoritmos para resolver el problema de los hospitales/residentes pueden estar orientados a los hospitales (como lo era 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 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 se quedarán atrapados en programas que están muy lejos uno del otro). La adición de parejas al problema de hospitales/residentes hace que el problema sea NP-completo . [16]
El problema de asignación busca encontrar una correspondencia en un gráfico bipartito ponderado que tenga el peso máximo. Las correspondencias con ponderación máxima no tienen por qué ser estables, pero en algunas aplicaciones una correspondencia con ponderación 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 emparejamiento con salarios flexibles. [18]
