Problema del matrimonio estable

Animación que explica el "problema del matrimonio estable".

En matemáticas, economía e informática, el problema del matrimonio estable (también problema de emparejamiento estable o SMP) 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. Una coincidencia es una biyección de los elementos de un conjunto a los elementos del otro conjunto.

Formulación

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, se trata de casar a los hombres y mujeres juntos de modo que no haya dos personas del sexo opuesto que prefieran tenerse el uno al otro más que a sus parejas actuales. Cuando no existen tales pares de personas, el conjunto de matrimonios se considera estable.

Una coincidencia no es estable si:

1.     Hay un elemento A del primer conjunto emparejado que prefiere algún elemento B dado del segundo conjunto emparejado sobre el elemento con el que A ya está emparejado, y
2.     B también prefiere A sobre el elemento con el que B ya está emparejado.

En otras palabras, una coincidencia es estable cuando no existe ninguna coincidencia (A, B) en la que ambos se prefieran entre sí a su pareja actual bajo la coincidencia.

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 habitación estables.

Aplicaciones

Los algoritmos para encontrar soluciones al problema del matrimonio estable tienen aplicaciones en una gran cantidad de situaciones del mundo real, quizás la más conocida de ellas es la asignación de estudiantes de medicina graduados a sus primeras tareas 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 asignaciones estables y la práctica del diseño de mercado".[2]​

Una aplicación importante y a gran escala del emparejamiento estable consiste en asignar usuarios a servidores en un gran servicio de Internet distribuido.[3]​ Miles de millones de usuarios acceden a páginas web, videos y otros servicios en Internet, lo que requiere que cada usuario sea emparejado 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 próximos 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 pueda 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 los servicios del mundo resuelven este gran y complejo problema de matrimonio estable entre usuarios y servidores cada pocos segundos para permitir que miles de millones de usuarios se emparejen con sus respectivos servidores que pueden proporcionar las páginas web, videos solicitados u otros servicios.

Diferentes emparejamientos estables

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 las preferencias siguientes:

A: YXZ  B: ZYX  C: XZY 

X: BAC  Y: CBA  Z: ACB

Hay tres soluciones estables para este arreglo coincidente:

• los hombres tienen 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).

Las tres son estables, porque la inestabilidad requiere que ambos participantes estén más felices con una solución alternativa. Darle a un grupo sus primeras opciones asegura que las coincidencias sean estables porque no estarían contentos con cualquier otra coincidencia propuesta. Darle a todos su segunda opción asegura que cualquier otro partido no sea del agrado de una de las partes. En general, a la familia de soluciones a cualquier caso 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 de matrimonios estables.[4]​

En un caso del problema del matrimonio estable con n hombres y n mujeres, el número promedio de emparejamientos estables es asintóticamente ${\displaystyle e^{-1}n\ln n}$.[5]​ En un caso de matrimonio estable elegido para maximizar el número de emparejamientos estables diferentes, este número es una función exponencial de n.[6]​ Contar el número de coincidencias estables en una instancia determinada es # P-completo.[7]​

Solución algorítmica

En 1962, David Gale y Lloyd Shapley demostraron que, para cualquier número igual de hombres y mujeres, siempre es posible resolver el problema y estabilizar todos los matrimonios. Presentaron un algoritmo para hacerlo.[8]​[9]​

La solución del algoritmo Gale-Shapley (también conocido como algoritmo de aceptación diferida) implica una serie de "rondas" (o " iteraciones "):

• En la primera ronda, primero a ) cada hombre no comprometido propone a la mujer que más prefiere, y luego b ) cada mujer responde "tal vez" a su pretendiente que más prefiere y "no" a todos los demás pretendientes. A continuación, se "compromete" provisionalmente con el pretendiente que más prefiere hasta ahora, y ese pretendiente también se compromete provisionalmente con ella.
• En cada ronda subsiguiente, primero a ) cada hombre no comprometido propone a la mujer más preferida 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 ella está actualmente no comprometida o si prefiere a este hombre sobre su actual pareja provisional (en este caso, rechaza a su actual pareja provisional que deja de estar comprometida). La naturaleza provisional de los compromisos preserva el derecho de una mujer ya comprometida a "cambiar" (y, en el proceso, "dejar plantada" a su hasta entonces pareja).
• Este proceso se repite hasta que todos se comprometen.

Así se garantiza que este algoritmo producirá un matrimonio estable para todos los participantes a tiempo ${\displaystyle O(n^{2})}$ dónde ${\displaystyle n}$ es el número de hombres o mujeres.[10]​

Entre todos los posibles emparejamientos estables diferentes, siempre se obtiene el que es mejor para todos los hombres y el peor para todas las mujeres. Es un mecanismo veraz desde el punto de vista de los hombres (el lado proponente). Es decir, ningún hombre puede conseguir una mejor coincidencia para sí mismo al tergiversar sus preferencias. Además, el algoritmo GS es incluso una prueba de estrategia grupal para los hombres, es decir, ninguna coalición de hombres puede coordinar una tergiversación de sus preferencias de manera que todos los hombres de la coalición estén en mejor situación.[11]​ Sin embargo, es posible que alguna coalición distorsione sus preferencias de modo que algunos hombres estén en mejor situación y los otros mantengan la misma pareja.[12]​ Por otro lado 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.

Teorema de los hospitales rurales

El teorema de los hospitales rurales se refiere a una variante del problema de emparejamiento estable, como la que se aplica en el problema de emparejar médicos con puestos en hospitales, que se diferencia en las siguientes formas de la forma básica del problema del matrimonio estable:

• Cada participante solo 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 la coincidencia resultante no coincida con todos los participantes.

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 vacíos en algún emparejamiento estable, recibe exactamente el mismo grupo de médicos en todos los emparejamientos estables.

Problemas relacionados

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 habitación estables es similar al problema del matrimonio estable, pero se diferencia en que todos los participantes son de un solo grupo (en lugar de dividirse en números iguales de "hombres" y "mujeres").

El problema de los hospitales / residentes, también conocido como el problema de las admisiones universitarias, se diferencia del problema del matrimonio estable en que un hospital puede admitir a varios residentes o una universidad puede admitir a más de un estudiante. Los algoritmos para resolver el problema de los hospitales / residentes pueden estar orientados al hospital (como lo era el NRMP antes de 1995)[13]​ o al residente . Este problema se resolvió, con un algoritmo, en el mismo artículo original de Gale y Shapley, en el que se solucionó el problema del matrimonio estable.[8]​

El problema de los 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 se quedarán juntos y no quedar atrapados en hospitales que están lejos unos de otros). La adición de parejas al problema de los hospitales / residentes hace que el problema sea NP-completo.[14]​

El problema de asignación busca encontrar una correspondencia en un gráfico bipartito ponderado que tenga el peso máximo. Estas coincidencias ponderadas máximas no tienen por qué 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 emparejarse con diferentes tipos de contratos.[15]​ Un caso especial importante de emparejamiento con contratos es el de los salarios flexibles.[16]​

Véase también

• Emparejamiento (teoría de grafos): emparejamiento entre diferentes vértices del gráfico; generalmente no está relacionado con el orden de preferencias.

Referencias

1. Stable Matching Algorithms
2. «The Prize in Economic Sciences 2012». Nobelprize.org. Consultado el 9 de septiembre de 2013. 
3. Bruce Maggs and Ramesh Sitaraman (2015). «Algorithmic nuggets in content delivery». ACM SIGCOMM Computer Communication Review 45 (3). Archivado desde el original el 12 de julio de 2023. Consultado el 6 de noviembre de 2020. 
4. Gusfield, Dan (1987). «Three fast algorithms for four problems in stable marriage». SIAM Journal on Computing 16 (1): 111-128. doi:10.1137/0216010. 
5. Pittel, Boris (1989). «The average number of stable matchings». SIAM Journal on Discrete Mathematics 2 (4): 530-549. doi:10.1137/0402048. 
6. Karlin, Anna R; Gharan, Shayan Oveis; Weber, Robbie. «A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings». Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. STOC 2018 (Association for Computing Machinery) 2018: 920-925. ISBN 9781450355599. doi:10.1145/3188745.3188848. 
7. Irving, Robert W.; Leather, Paul (1986). «The complexity of counting stable marriages». SIAM Journal on Computing 15 (3): 655-667. doi:10.1137/0215048. 
8. Gale, D.; Shapley, L. S. (1962). «College Admissions and the Stability of Marriage». American Mathematical Monthly 69 (1): 9-14. doi:10.2307/2312726. Archivado desde el original el 25 de septiembre de 2017. Consultado el 6 de noviembre de 2020. 
9. Harry Mairson: "The Stable Marriage Problem", The Brandeis Review 12, 1992 (online).
10. Iwama, K; Miyazaki, S (2008). «A Survey of the Stable Marriage Problem and Its Variants». International Conference on Informatics Education and Research for Knowledge-Circulating Society (icks 2008): 131-136. doi:10.1109/ICKS.2008.7. Consultado el 14 de enero de 2021. 
11. Dubins, L. E.; Freedman, D. A. (1981). «Machiavelli and the Gale–Shapley algorithm». American Mathematical Monthly 88 (7): 485-494. doi:10.2307/2321753. 
12. Huang, Chien-Chung (2006). «Cheating by Men in the Gale-Shapley Stable Matching Algorithm». ESA 2006. ESA 2006. Lecture Notes in Computer Science, vol 4168. Springer, Berlin, Heidelberg. doi:10.1007/11841036_39. Consultado el 14 de enero de 2021. 
13. Robinson, Sara (April 2003). «Are Medical Students Meeting Their (Best Possible) Match?». SIAM News (3): 36. Archivado desde el original el 18 de noviembre de 2016. Consultado el 2 de enero de 2018. 
14. Gusfield, D.; Irving, R. W. (1989). The Stable Marriage Problem: Structure and Algorithms. MIT Press. p. 54. ISBN 0-262-07118-5. 
15. Hatfield, John William; Milgrom, Paul (2005). «Matching with Contracts». American Economic Review 95 (4): 913-935. doi:10.1257/0002828054825466. 
16. Crawford, Vincent; Knoer, Elsie Marie (1981). «Job Matching with Heterogeneous Firms and Workers». Econometrica 49 (2): 437-450. doi:10.2307/1913320. 

Bibliografía

• Kleinberg, J. y Tardos, E. (2005) Algorithm Design, Capítulo 1, págs. 1-12. Consulte el sitio web complementario para el texto [1] Archivado el 14 de mayo de 2011 en Wayback Machine. .
• Knuth, D. E. (1996). Stable Marriage and Its Relation to Other Combinatorial Problems: An Introduction to the Mathematical Analysis of Algorithms. CRM Proceedings and Lecture Notes. English translation. American Mathematical Society. 
• Pittel, B. (1992). «On likely solutions of a stable marriage problem». The Annals of Applied Probability 2 (2): 358-401. doi:10.1214/aoap/1177005708. 
• Roth, A. E. (1984). «The evolution of the labor market for medical interns and residents: A case study in game theory». Journal of Political Economy 92 (6): 991-1016. doi:10.1086/261272. 
• Roth, A. E.; Sotomayor, M. A. O. (1990). Two-sided matching: A study in game-theoretic modeling and analysis. Cambridge University Press. 
• Shoham, Yoav; Leyton-Brown, Kevin (2009). Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. New York: Cambridge University Press. ISBN 978-0-521-89943-7. 
• Schummer, J.; Vohra, R. V. (2007). «Mechanism design without money». En Nisan, Noam; Roughgarden, Tim; Tardos, eds. Algorithmic Game Theory. pp. 255-262. ISBN 978-0521872829. 

• Datos: Q620702