El problema del Matrimonio Estable

Hospedado en el blog de @trebede

Llegan las fiestas navideñas y con ellas, según algunos abogados de familia, el aumento del número de divorcios. 

Entonces uno se pregunta, ¿dónde está el problema de estos matrimonios que desaparecen cuando suena la zambomba y el olor a mazapán impregna el aire? ¿No eran lo suficientemente estables?


Y es que...nos lanzamos a la aventura sin documentarnos, hombre...


El problema del Matrimonio Estable ha sido ampliamente estudiado por matemáticos, que suelen ser una gente muy formal y rigurosa para todo lo que hacen, me han dicho.


El planteamiento claśico del problema es el siguiente. Tenemos un conjunto formado por N hombres y N mujeres. Cada hombre y cada mujer, hace una lista ordenada de preferencias sobre el grupo del sexo opuesto. Se trata de hacer un emparejamiento, fomar las N parejas, de forma estable, es decir, si un hombre y una mujer (no emparejados entre ellos) preferirían  estar juntos antes que con sus actuales parejas, es un emparejamiento inestable.


En 1962,  David Gale  y Lloyd Shapley demostraron que, si el número de hombres es el mismo que el de mujeres, siempre existe una solución con matrimonios estables. La descripción del algoritmo es la siguiente:


Todos están sin pareja.


Nos fijamos en la lista de las mujeres, suele llevar gafas. Venga, ahora en serio.


Nos fijamos en la lista de las mujeres.


Mientras que haya una mujer libre, hago lo siguiente:


Le propone matrimonio al primer hombre de su lista:

• Si el hombre está libre, se casan, perdices, sushi o lo que quieran
• Si el hombre ya está casado, tuitea su mala suerte y le pregunta si la prefiere a ella antes que a su actual mujer (mirando la lista ordenada de preferencias de él):

                             -Si la prefiere a ella, se divorcia de la otra

                             -Si no, la mujer, sigue su peregrinar al siguiente de la lista.

Al final, el resultado es un conjunto de parejas estables, en el sentido que hemos definido antes. Esta solución es óptima para el conjunto de las mujeres y la peor para el conjunto de los hombres, pero para eso soy yo la que ha escrito el algoritmo, digo. Si se empieza con el conjunto de hombres, se obtiene una solución óptima para ellos.

Si os ha gustado este problema de Teoría de Grafos, os recomiendo que juguéis en el siguiente enlace a conseguir matrimonios estables en la realeza de los Naipes.

Si elegís "Exhibit Walkthrough" os cuentan sobre el problema y sus soluciones.

Si elegís "Free Experiments" podréis jugar 

Podéis elegir el número de parejas, si queréis que empiecen proponiendo los hombres o las mujeres y os muestra la solución, en el caso de que no os salga.

En cualquier caso, mi consejo es que sea el amor y no un algoritmo el que os ayude.