El Problema del Matrimonio Estable
Una exploración interactiva del algoritmo de Gale-Shapley
El Problema del Matrimonio Estable
Un concepto matemático de 1962 que resuelve cómo emparejar dos grupos de forma óptima, con aplicaciones que van desde la admisión universitaria hasta los servicios de transporte modernos.
Origen del Problema
El problema del matrimonio estable nace en 1962 con una publicación de David Gale y Lloyd S. Shapley en un artículo titulado “College Admissions and the Stability of Marriage.” En su publicación, Gale y Shapley resuelven el problema de como hacer asignar de la mejor manera posible a estudiantes dentro de un programa académico universitario. Desarrollan este concepto a través de la idea del matrimonio estable entre hombres y mujeres. (Harris, Hirst, & Mossinghoff, 2008, pp. 248–264)
Definición del Problema
Entendiendo el concepto clave de "estabilidad" en los emparejamientos.
¿Qué es un Matrimonio Estable?
Imagina una comunidad con un número igual de hombres y mujeres. Cada persona tiene una lista de preferencias, ordenando a todos los miembros del sexo opuesto. El objetivo es crear parejas (matrimonios) de tal forma que el sistema sea estable.
Un sistema de emparejamiento es estable si no existe una "pareja bloqueadora": un hombre y una mujer que no están emparejados entre sí, pero que ambos se prefieren mutuamente por encima de sus parejas actuales. Si existe una pareja así, podrían "fugarse", creando inestabilidad.
En una configuración estable, aunque alguien no esté con su primera opción, no podrá encontrar a nadie mejor que también quiera estar con él o ella. No hay posibilidad de "infidelidades" que mejoren la situación de ambas personas involucradas.
Más Allá del Matrimonio
El algoritmo no trata sobre matrimonio en el sentido literal. Es un modelo para emparejar dos conjuntos distintos de elementos (por eso se habla de grupos "heterosexuales"). Una universidad (Grupo A) busca estudiantes (Grupo B), no otras universidades. El problema se formaliza como la búsqueda de una función biyectiva entre dos conjuntos.
Imaginemos dos parejas:
- (Juan, Ana)
- (Pablo, Paula)
Si Juan prefiere a Paula sobre Ana y, al mismo tiempo, Paula prefiere a Juan sobre Pablo, entonces Juan y Paula forman una "pareja bloqueadora". Ambos tienen un incentivo para romper sus compromisos actuales y formar una nueva pareja, desestabilizando el sistema.
La configuración estable sería (Juan, Paula) y (Pablo, Ana).
El Algoritmo de Gale-Shapley
Un ritual iterativo para encontrar una configuración estable y a prueba de infidelidades.
El Ritual de Emparejamiento
Gale y Shapley no solo demostraron que siempre existe una configuración estable, sino que también nos dieron un método para encontrarla. El algoritmo funciona como un ritual de propuestas paso a paso.
- Ronda de Propuestas: Todos los hombres que no tengan pareja mandarán una propuesta de matrimonio a la mujer que esté primero en su lista de preferencias (que no los haya rechazado antes).
- Evaluación y Compromisos Provisionales: Cada mujer revisará todas las propuestas recibidas. Si está libre, aceptará al pretendiente que más le guste y rechazará a los demás. Si ya tiene una pareja provisional, la comparará con los nuevos pretendientes. Si prefiere a uno nuevo, romperá su compromiso actual para aceptar al nuevo, dejando al anterior libre.
- Terminación: El proceso se repite con los hombres que quedaron libres. El ritual termina cuando todos los hombres tienen pareja. En ese momento, todos los compromisos se vuelven definitivos.
¿Un Algoritmo Justo?
El algoritmo busca encontrar configuraciones de matrimonios estables. Esto significa que con que uno de los lados siempre esté con su mejor opción posible, es suficiente para garantizar estabilidad en el sistema.
Ventaja para el Proponente
Como lo indica el teorema 2, los hombres (el grupo que propone) siempre estarán con su mejor posibilidad. Con esta deducción es fácil darse cuenta que en este algoritmo, la mejor idea es estar del lado de los que se proponen y no de los que reciben propuestas, pues el primer lado siempre logrará estar con su mejor posibilidad, mientras que el segundo no tiene nada garantizado.
Propiedades Fundamentales
Simulación Interactiva
Observa el algoritmo de Gale-Shapley en acción. Presiona "Siguiente Paso" para recorrer el proceso de emparejamiento.
Proponentes (Hombres)
- 1.Sarah
- 2.Ana
- 3.Paula
- 1.Ana
- 2.Paula
- 3.Sarah
- 1.Sarah
- 2.Ana
- 3.Paula
Receptores (Mujeres)
- 1.Pablo
- 2.Juan
- 3.Mateo
- 1.Juan
- 2.Mateo
- 3.Pablo
- 1.Pablo
- 2.Mateo
- 3.Juan
Parejas Actuales
Aún no hay parejas.
Registro del Algoritmo
Aplicaciones Modernas
Más allá del matrimonio: cómo el algoritmo modela nuestro mundo.
El concepto de emparejamiento estable, aunque ilustrado con matrimonios, tiene un alcance mucho mayor. Se aplica a cualquier escenario que involucre emparejar elementos de un grupo con los de otro, optimizando la satisfacción y estabilidad del sistema completo.
En computación, es fundamental para las comunicaciones por internet y la asignación eficiente de recursos, como en el sistema Anchor de la Universidad de Toronto, que empareja máquinas virtuales con servidores físicos. (Xu & Li, 2011). Más recientemente, se ha vuelto clave en la economía gig, potenciando servicios de delivery y transporte. (Ravindranatha et al., 2023)
Admisión a Universidades
Aplicaciones de Trabajo
Hospitales y Residentes
Donantes y Receptores de Órganos
Asignación de Servidores
Servicios de Transporte (Uber, Lyft)
El caso de los hospitales y los residentes
Un problema clásico es el emparejamiento de médicos residentes con hospitales. Anualmente, más estudiantes de medicina buscan una residencia de los puestos que hay disponibles. El sistema tiene reglas complejas: los estudiantes tienen preferencias y los hospitales también, a menudo considerando solo un subconjunto de aplicantes.
Históricamente, el sistema favorecía a los hospitales, creando dilemas para los estudiantes que debían aceptar ofertas tempranas y no óptimas. Gracias a la implementación de un sistema basado en Gale-Shapley, ahora son los estudiantes quienes "proponen", equilibrando el sistema y garantizando que obtengan la mejor residencia posible de entre sus opciones viables. (Edison Hauptman, 2022)
Conclusiones y Reflexiones
El futuro de los algoritmos de emparejamiento.
El problema del matrimonio estable contiene una gran cantidad de implicaciones para la vida moderna. Ha ayudado a agilizar la infraestructura de internet que utilizamos todos los días, y nos permite ser lo más eficientes posibles a la hora de usar recursos tecnológicos en nuestras actividades del día a día. Incluso nos permite disfrutar de aplicaciones de cabina como Uber y Lyft. Además, ha tenido muchas implicaciones en actividades sociales como el emparejamiento de hospitales y residentes, empleados y puestos de trabajo, admisión de universidades y colegios, entre otros.
A pesar de esto, los problemas de emparejamiento estables están lejos de estar solucionados por completo. Como fue demostrado en el articulo publicado por Ravindranatha et al., nos queda un largo camino y mucho margen de mejora.
El Futuro del Emparejamiento
El algoritmo Gale-Shapley garantiza estabilidad, pero no siempre es a prueba de manipulaciones estratégicas. Con el auge del Deep Learning, han surgido modelos híbridos. Investigadores de Harvard crearon una IA que, buscando estabilidad, iguala a Gale-Shapley pero con mayor robustez a engaños. Cuando se prioriza la resistencia a mentiras, supera a otros algoritmos sin sacrificar demasiada estabilidad. (Ravindranatha et al., 2023)
Variaciones del Problema
No he abordado todas las variaciones. Una interesante es el "problema de los compañeros de cuarto" (roommates), donde no hay dos grupos distintos. Aquí, un emparejamiento estable no siempre está garantizado. Esto demuestra cómo pequeños cambios en la formulación de un problema pueden alterar drásticamente su solución, una de las bellezas de las matemáticas.
Reflexiones Finales
La existencia de estos algoritmos prueba dos cosas en mi opición. La primera es que no importa que tan absurda sea una suposición inicial, siempre vale la pena investigarla y estudiarla un poco porque puede tener grandes implicaciones para la vida de las personas. La segunda es que estamos lejos de tenerlo todo resuelto. Incluso problemas con soluciones casi perfectas y estudiadas por más de 60 años están sujetas a ser mejoradas. Siempre nacerán nuevas tecnologías y enfoques que permiten mejorar la eficiencia en procesos y actividades que damos por sentado. Siempre vale la pena seguir buscando por nuevas respuestas.
Finalmente, debo mencionar que no tomé en cuenta muchas variaciones y consideraciones de este problema. De hecho, una de las variaciones más interesantes es el de emparejamiento de roomates. Esta variación demuestra la importancia de que el emparejamiento deba ser de un grupo hacia otro para poder garantizar emparejamiento estable, cuando metemos “relaciones homosexuales” al problema, el sistema se desestabiliza y deja de garantizar soluciones estables. Es por estas cosas que las matemáticas son tan interesantes, pequeños cambios en la presentación de un problema cambian por completo su resolución.
Bibliografía
Edison Hauptman. (2022, 16 agosto). Why Queer Relationship Dynamics are Harder: The Stable Marriage Problem #SoME2 [Vídeo]. YouTube. https://www.youtube.com/watch?v=_6I9u2RVYLA
Fenoaltea, E. M., Baybusinov, I. B., Zhao, J., Zhou, L., & Zhang, Y.-C. (2021). The Stable Marriage Problem: An interdisciplinary review from the physicist’s perspective. Physics Reports, 917, 1–79. Elsevier. https://doi.org/10.1016/j.physrep.2021.03.001
Harris, J. M., Hirst, J. L., & Mossinghoff, M. J. (2008). Stable marriage. En Combinatorics and graph theory (2nd ed., pp. 248–264). Springer. https://doi.org/10.1007/978-0-387-79711-3
Lehman, E., Leighton, T., & Meyer, A. (2015). Mathematics for computer science (Spring 2015 ed.). MIT OpenCourseWare. https://ocw.mit.edu
Numberphile2. (2014, 4 septiembre). Stable Marriage Problem (the math bit) [Vídeo]. YouTube. https://www.youtube.com/watch?v=LtTV6rIxhdo
Ravindranatha, S. S., Feng, Z., Li, S., Ma, J., Kominers, S. D., & Parkes, D. C. (2023). Deep learning for two-sided matching. arXiv. https://arxiv.org/abs/2107.03427
Xu, H., & Li, B. (2011). Anchor: A stable matching framework for managing cloud resources. Technical Report, Department of Electrical and Computer Engineering, University of Toronto.