Pareja estable

A propósito del pasado 14 de febrero.

Supongamos que tenemos n sujetos y n mujeres. Cada uno de los n hombres califica a las n mujeres de manera única de acuerdo a sus gustos: “a la chaparrita le doy un 5”, “a la actuaria un 10”, ¨aquella de ojos... un 7¨. Lo mismo hacen las mujeres con los hombres (por sencillez del problema asumimos que todos son heterosexuales!!). De tal forma que si el sujeto X califica con 10 a la mujer Y significa que es la preferida de X mientras que la calificada con 1 es la que menos interés le despierta a X. De manera similar con las mujeres.

Usando esta lista de calificaciones, que cada persona tiene, el reto es formar parejas de novios tal que evitemos infedilidades. Es decir si pepito-lupita y jorgito-marianita ,son dos parejas formadas por nuestro algoritmo, no queremos que pepito prefiera a marianita y ésta prefiera también a pepito sobre su actual pareja, ya que queremos evitar romper el corazón de lupita y de jorgito. Si evitamos este tipo de situaciones entonces decimos que las parejas son estables.

Resulta que es posible encontrar un emparejamiento estable siempre. Es más podemos encontrar una forma de encontrar parejas de tal forma que los mujeres queden lo menos insatisfechas posibles (óptimo para los mujeres ) y de manera análoga para los hombres.

La solución es sencilla y es como sigue:

Cada hombre le propone, formar pareja, a la mujer con mejor "ranking" en su lista y que además no le ha propuesto con anterioridad. La mujer en cuestión puede estar con o sin pareja; si esta libre acepta y se forma una posible pareja; si no esta libre entonces la mujer debe decidir con quien quedarse de acuerdo a su lista de preferencia. El algoritmo acaba cuando ya no hay hombres buscando pareja.

Este algoritmo es "claramente" óptimo para los hombres. La forma de hacerlo óptimo para las mujeres es haciendo que ellas hagan las propuestas... Total se puede probar que el algoritmo es correcto y óptimo si alguien quiere ver las pruebas y la solución formal puede revisar este libro. Se observa que los 4 se "emparejan" con los 4 los 10 con los 10 etc, etc.

Fin a los problemas de encontrar pareja estable.