Problema de matrimonio estable

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:

A: YXZ B: ZYX C: XZY  

X: BAC Y: CBA Z: ACB

Hay tres soluciones estables para esta disposición coincidente:

• los hombres obtienen su primera opción y las mujeres la tercera (AY, BZ, CX);
• Todos los participantes obtienen su segunda opción - (AX, BY, CZ);
• Las mujeres tienen su primera opción y los hombres la tercera (AZ, BX, CY).

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]${\displaystyle e^{-1}n\ln n}$

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 "):

• En la primera ronda, a ) cada hombre no comprometido le propone matrimonio a la mujer que más le gusta y, a continuación, b ) cada mujer responde "tal vez" al pretendiente que más le gusta y "no" a todos los demás pretendientes. A continuación, queda "prometida" provisionalmente con el pretendiente que más le gusta hasta el momento, y ese pretendiente también queda comprometido provisionalmente con ella.
• En cada ronda subsiguiente, primero a ) cada hombre no comprometido le propone matrimonio a la mujer que más le gusta y a la que aún no le ha propuesto matrimonio (independientemente de si la mujer ya está comprometida), y luego b ) cada mujer responde "tal vez" si actualmente no está comprometida o si prefiere a este hombre sobre su pareja provisional actual (en este caso, rechaza a su pareja provisional actual que se desvincula). La naturaleza provisional de los compromisos preserva el derecho de una mujer ya comprometida a "cambiar de posición" (y, en el proceso, a "dejar plantada" a su pareja hasta entonces).
• Este proceso se repite hasta que todos estén involucrados.

Este algoritmo garantiza producir un matrimonio estable para todos los participantes en el tiempo donde es el número de hombres o mujeres. ^[11]${\displaystyle O(n^{2})}$${\estilo de visualización n}$

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:

• Cada participante sólo puede estar dispuesto a ser emparejado con un subconjunto de los participantes del otro lado del emparejamiento.
• Los participantes de un lado del emparejamiento (los hospitales) pueden tener una capacidad numérica, especificando el número de médicos que están dispuestos a contratar.
• Es posible que el número total de participantes de un lado no sea igual a la capacidad total con la que se los emparejará en el otro lado.
• Es posible que el resultado resultante no coincida con todos los participantes.

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:

• El conjunto de médicos asignados y el número de puestos ocupados en cada hospital son los mismos en todos los emparejamientos estables.
• Cualquier hospital que tenga algunos puestos vacantes en algún emparejamiento estable, recibe exactamente el mismo conjunto de médicos en todos los emparejamientos estables.

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]

• Coincidencia (teoría de grafos) : coincidencia entre diferentes vértices del grafo; generalmente no relacionada con el orden de preferencias.
• Emparejamiento sin envidia : una relajación del emparejamiento estable para problemas de emparejamiento de varios a uno
• Coincidencia de arcoíris para gráficos de colores de borde
• Politopo coincidente estable
• Red de emparejamientos estables
• Problema de la secretaria (también llamado problema matrimonial ): decidir cuándo parar para obtener la mejor recompensa en una secuencia de opciones

• Kleinberg, J. y Tardos, E. (2005) Algorithm Design , Capítulo 1, págs. 1–12. Véase el sitio web complementario para el texto [1] Archivado el 14 de mayo de 2011 en Wayback Machine .
• Knuth, DE (1996). Matrimonio estable y su relación con otros problemas combinatorios: una introducción al análisis matemático de algoritmos . Actas y notas de conferencias de CRM. Traducción al inglés. American Mathematical Society.
• Pittel, B. (1992). "Sobre las soluciones probables de un problema de matrimonio estable". Anales de probabilidad aplicada . 2 (2): 358–401. doi : 10.1214/aoap/1177005708 . JSTOR  2959755.
• Roth, AE (1984). "La evolución del mercado laboral de médicos internos y residentes: un estudio de caso en teoría de juegos" (PDF) . Revista de Economía Política . 92 (6): 991–1016. doi :10.1086/261272. S2CID  1360205.
• Roth, AE; Sotomayor, MAO (1990). Emparejamiento bilateral: un estudio sobre modelado y análisis de teoría de juegos . Cambridge University Press .
• Shoham, Yoav; Leyton-Brown, Kevin (2009). Sistemas multiagente: fundamentos algorítmicos, lógicos y de teoría de juegos. Nueva York: Cambridge University Press . ISBN 978-0-521-89943-7.Consulte la Sección 10.6.4; descargable gratuitamente en línea.
• Schummer, J.; Vohra, RV (2007). «Diseño de mecanismos sin dinero» (PDF) . En Nisán, Noam; Jardín áspero, Tim; Tardós, Eva; Vazirani, Vijay (eds.). Teoría algorítmica de juegos . págs. 255–262. ISBN 978-0521872829.
• Gusfield, D.; Irving, RW (1989). El problema del matrimonio estable: estructura y algoritmos. MIT Press . ISBN 0-262-07118-5.

• Demostración interactiva en flash del problema del matrimonio estable
• https://web.archive.org/web/20080512150525/http://kuznets.fas.harvard.edu/~aroth/alroth.html#NRMP
• http://www.dcs.gla.ac.uk/research/algorithms/stable/EGSapplet/EGS.html
• Notas de la conferencia sobre el problema del matrimonio estable