Algoritmo de Irving

El llamado The Stable Rommates Problem o 'Problema de las Compañeras de Piso' fue resuelto mediante un algoritmo por Robert W. Irving en 1985. Cada participante ordena a sus posibles compañeras según sus preferencias. Cada chica elige una compañera y ésta acepta o no la oferta. En caso de no aceptar se entiende que rechaza a la chica que le ha hecho la propuesta. En el ejemplo de la tabla el AZUL indica la elegida, el VERDE la que acepta y el ROJO la rechazada.

• 1ª ETAPA
• Cada chica propone a su compañera favorita.
• La elegida acepta, pero si es elegida por más de una, acepta la mejor propuesta y rechaza las demás.
• Las rechazadas esperan para ser aceptadas más adelante.
• Si alguna chica es rechazada por todas no existe una solución estable.

Aunque Berta elige a Delia, ella prefiere a Clara y es rechazada. Igualmente, aunque Eva elige a Flor, ella prefiere a Delia y es rechazada.

Ahora Berta propone a Eva que acepta y Eva propone a Clara que acepta.

• 2ª ETAPA
• Todas desechan las posibles compañeras que son menos deseadas que la actualmente aceptada.

Ana rechaza a Clara y a Eva, Berta rechaza a Clara, y así sucesivamente.

Así las opciones quedan reducidas a las siguientes:

• 3ª ETAPA
• Elige una participante X que tenga al menos dos opciones.
• Busca su segunda preferencia Y.
• Sea Z la última preferencia de Y.
• Repite el proceso hasta que se llegue a X.
• Elimina las parejas (Y,Z) y sus simétricas.
• Repite el proceso hasta que todas tengan una única opción.

Los emparejamientos son: Ana y Flor, Berta y Eva, Clara y Delia.

En este caso no hay una solución estable, pues nadie quiere ir con D.