Matrimonio estable con indiferencia
El matrimonio estable con indiferencia es una variante del problema del matrimonio estable . Al igual que en el problema original, el objetivo es emparejar a todos los hombres con todas las mujeres, de modo que ningún par de hombres y mujeres que no estén casados entre sí deseen dejar simultáneamente a sus parejas actuales y emparejarse entre sí.
En la versión clásica del problema, cada persona debe clasificar a los miembros del sexo opuesto en estricto orden de preferencia. Sin embargo, en un escenario del mundo real, una persona puede preferir dos o más personas como pareja igualmente favorable. Tal preferencia ligada se denomina indiferencia .
A continuación se muestra una instancia en la que encuentra vínculo entre y encuentra vínculo entre .
Si se permiten listas de preferencia empatadas, el problema del matrimonio estable tendrá tres nociones de estabilidad que se analizan en las secciones siguientes.
1. Un emparejamiento se denomina débilmente estable a menos que haya una pareja que prefiera estrictamente al otro a su pareja en el emparejamiento. Robert W. Irving [1] ha ampliado el algoritmo de Gale-Shapley como se muestra a continuación para proporcionar una coincidencia débilmente estable en el tiempo donde n es el tamaño del problema de matrimonio estable. Los empates en la lista de preferencia de hombres y mujeres se rompen arbitrariamente. Las listas de preferencias se reducen a medida que avanza el algoritmo.
2. Se dice que un emparejamiento es superestable si no hay una pareja que prefiera estrictamente al otro a su pareja o sea indiferente entre ellos. Robert W. Irving [1] ha modificado el algoritmo anterior para verificar si existe tal coincidencia súper estable y si existe coincidencia de salida en el tiempo. A continuación se muestra el pseudocódigo.