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 tal manera que ninguna pareja de hombre y mujer que no estén casados ​​entre sí desee simultáneamente abandonar 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 la vida real, una persona puede preferir a dos o más personas como pareja igualmente deseable. Esta preferencia empatada se denomina indiferencia .

A continuación se muestra un ejemplo de este tipo donde${\displaystyle m_{2}}$es indiferente entre${\displaystyle w_{3}\&w_{1}}$y${\displaystyle w_{2}}$es indiferente entre${\displaystyle m_{1}\&m_{2}}$.

${\displaystyle m_{1}[\ w_{2}\ w_{1}\ w_{3}\ ]\ \ \ \ \ \ w_{1}[\ m_{3}\ m_{2}\ m_{1}\ ]}$

${\displaystyle m_{2}[\left(w_{3}\ w_{1}\right)w_{2}]\ \ \ \ \ \ w_{2}[\left(m_{1}\ m_{2}\right)m_{3}]}$

${\displaystyle m_{3}[\ w_{1}\ w_{2}\ w_{3}\ ]\ \ \ \ \ \ w_{3}[\ m_{2}\ m_{3}\ m_{1}\ ]}$

Si se permiten las listas de preferencias 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 en la que cada miembro prefiera estrictamente al otro antes que a su pareja en el emparejamiento. Robert W. Irving ^{[ 1 ]} extendió el algoritmo de Gale-Shapley como se muestra a continuación para proporcionar un emparejamiento débilmente estable de este tipo. ${\displaystyle O(n^{2})}$tiempo, donde n es el tamaño del problema del matrimonio estable. Los empates en las listas de preferencias de hombres y mujeres se resuelven arbitrariamente. Las listas de preferencias se reducen a medida que avanza el algoritmo.

Asignar a cada persona la libertad de elección ;mientras ( algún hombre m es libre ) hacercomenzarw : = primera mujer en la lista de m ;m propone matrimonio a w y se compromete con ella ;si ( algún hombre m está comprometido con w ) entonces​asignar m ' para que sea libre ;para cada ( sucesor m '' de m en la lista de w ) hacereliminar el par ( m '' , w )fin ;generar los pares comprometidos , que forman un emparejamiento estable

2. Un emparejamiento se denomina superestable si no existe ninguna pareja en la que cada miembro prefiera estrictamente al otro antes que a su pareja o sea indiferente entre ellos. Robert W. Irving ^{[ 1 ]} ha modificado el algoritmo anterior para comprobar si existe tal emparejamiento superestable y genera emparejamientos en${\displaystyle O(n^{2})}$tiempo si existe. A continuación se muestra el pseudocódigo .

asignar a cada persona la libertad ;repetirmientras ( algún hombre m es libre ) hacerpara cada ( mujer w al frente de la lista m ) hacer​​comenzarm propone matrimonio a w y se compromete con ella ;para cada ( sucesor estricto m ' de m en la lista de w ) hacercomenzarsi ( m ' está comprometido ) con w entoncesromper el compromiso ;eliminar el par ( m ' , w )finfinpara cada ( mujer w que está comprometida múltiplemente ) hacercomenzarromper todos los compromisos que involucren w ;para cada ( hombre m al final de la lista de w ) hacer​eliminar el par ( m , w )fin ;hasta que ( la lista de algún hombre esté vacía ) o ( todos estén ocupados );si todos están involucrados entoncesLa relación de compromiso es una coincidencia súper estable .demásno existe emparejamiento súper estable​

3. Un emparejamiento es fuertemente estable si no existe una pareja x, y tal que x prefiera estrictamente a y antes que a su pareja, e y prefiera estrictamente a x antes que a su pareja o sea indiferente entre ellos. Robert W. Irving ^{[ 1 ]} proporcionó el algoritmo que verifica si existe tal emparejamiento fuertemente estable y lo muestra si existe. El algoritmo calcula el emparejamiento perfecto entre conjuntos de hombres y mujeres, encontrando así el conjunto crítico de hombres que están comprometidos con varias mujeres. Dado que tales compromisos nunca son estables, todos esos pares se eliminan y la secuencia de propuestas se repetirá hasta que 1) la lista de preferencias de algún hombre quede vacía (en cuyo caso no existe un emparejamiento fuertemente estable) o 2) se obtenga un emparejamiento fuertemente estable. A continuación se muestra el pseudocódigo para encontrar emparejamientos fuertemente estables. Se ejecuta en${\displaystyle O(n^{4})}$tiempo que se explica en el Lema 4.6 de . ^{[ 1 ]}

Asignar a cada persona la libertad de elección ;repetirmientras ( algún hombre m es libre ) hacerpara cada ( mujer w al frente de la lista m ) hacer​​comenzarm propone matrimonio a w y se compromete con ella ;para cada ( sucesor estricto m ' de m en la lista de w ) hacercomenzarsi ( m ' está comprometido ) con w entoncesromper el compromiso ;eliminar el par ( m ' . w )finfinsi ( la relación de compromiso no contiene una coincidencia perfecta ) entoncescomenzarencontrar el conjunto crítico Z de hombres ;para cada ( mujer w que está comprometida con un hombre en Z ) hacercomenzarromper todos los compromisos que involucren w ;para cada hombre m al final de la lista de w hacer​eliminar el par ( m , w )fin ;fin ;hasta que ( la lista de algún hombre esté vacía ) o ( todos estén ocupados );si todos están involucrados entoncesLa relación de compromiso es una coincidencia súper estable .demásno existe emparejamiento fuertemente estable

En muchos problemas, puede haber varios emparejamientos estables diferentes. El conjunto de emparejamientos estables tiene una estructura especial. David F. Manlove ^{[ 2 ]} demostró que tanto el conjunto de emparejamientos estables fuertes como el conjunto de emparejamientos súper estables forman un retículo distributivo .