Algoritmo para problema de “Casamiento Estable”

Aunque el problema es conocido como “casamiento estable” (y se soluciona pensando en esta idea), su utilidad es muy amplia y se puede aplicar a una basta gama de problemas actuales. Este problema fue estudiado por primera vez hace ya unos 50 años por Gale y Shapley, con el fin de seleccionar de la manera más óptima y justa a candidatos que postulan a las diferentes universidades. Parece bastante simple la idea, pero veamos un ejemplo que más o menos ilustra las complicaciones del problema: Supongamos que existen n empresas y n candidatos para trabajar (si, nadie quedará sin empleo esta vez), cada empresa necesita tan sólo 1 empleado y vamos a suponer que todos los candidatos postulan a todas las empresas. Además, supondremos que cada candidato tiene sus preferencias de trabajo (ordenadas estrictamente de forma creciente, es decir, para cada par de empresas todo candidato prefiere claramente una de las 2!) y de la misma forma, cada empresa tiene sus preferencias respecto a los candidatos. Veamos que podría ocurrir en una situación más concreta,

  1. Felipe acepta la oferta de trabajo hecha por Yahoo;
  2. Google le hace una oferta de trabajo a Felipe (considerando que él prefiere trabajar en Google);
  3. Felipe cancela el acuerdo con Yahoo y acepta la oferta hecha por Google;
  4. Yahoo le ofrece una oferta de trabajo a Manuel;
  5. Manuel ya había aceptado la oferta de Submarine (considerando que Manuel prefiere trabajar en Yahoo);
  6. Manuel cancela el acuerdo con Submarine y acepta la oferta hecho por Yahoo;

Es fácil ver que la situación puede generar un caos y podría ocurrir que las empresas y candidatos queden insatisfechos con el resultado final. Para representar esta situación de manera más clara, y trabajar sobre esto, hablaremos de casamientos (matchings) entre hombres y mujeres. Analicemos esta situación que llamaremos problema de casamiento. Sea n\in\mathbb N y considere

  1. M=\{m_1,m_2,\ldots,m_n\} el conjunto ordenado de n hombres;
  2. W=\{w_1,w_2,\ldots,w_n\} el conjunto ordenado de n mujeres;
  3. Suponga que todo mundo se quiere casar con alguien del sexo apuesto;

Diremos que un subconjunto S\subset M\times W es un casamiento si cada miembro de M y cada miembro de W aparecen en exactamente un par ordenado de S (esta condición es conocida también como casamiento perfecto o perfect matching). Dado un casamiento en este contexto, estableceremos preferencias para cada hombre y cada mujer que serán representadas por un vector p\in\{1,2,\ldots,n\}^{n} que tiene todas sus coordenadas diferentes!, por ejemplo, si un hombre m_j posee una preferencia p_j=(n,n-1,\ldots,2,1), quiere decir que m_j prefiere a la mujer w_n por sobre todas, luego a la mujer w_{n-1}, y asi sucesivamente hasta llegar a su peor opción, la mujer w_1 (Ojo! Estamos suponiendo nuevamente que no hay “empates” en las preferencias). Es claro que, si el vector p fuera la preferencia de una mujer, entonces éste específica un orden de preferecias masculinas. La pregunta que nos haremos ahora será será bastante amplia: Dado un casamiento S, ¿qué puede salir mal?. Pensemos en la siguiente situación 2\times 2: S=\{(m_1,w_1),(m_2,w_2)\} tal que las preferecias de m_1 y w_2 en cada caso vienen dadas por:

  1. m_1 tiene por vector preferencia a (2,1) (que denotaremos por m_1\leftrightarrow(2,1));
  2. w_2\leftrightarrow(1,2);

En palabras simples, tenemos que m_1 prefiere a w_2 que a w_1, y que w_2 prefiere a m_1 que a m_2. Graficado el casamiento S (como grafo) tenemos que
conflicto inestabilidad
Informalmente, podemos decir que el grafo tiene una cierta “tendencia” a cambiar, puesto que m_1 y w_2 se prefieren mutuamente y no estan “casados”. Al par ordenado (m_1,w_2), en un caso así, se le llama inestabilidad (o conflicto) y ampliamos esta definición para un caso general. Y finalmente, dado un casamiento S decimos que es un casamiento estable si no tiene inestabilidades. Para fijar ideas, supongamos que tenemos la siguiente configuración: M=\{m_1,m_2\}, W=\{w_1,w_2\} y

  1. m_1\leftrightarrow (1,2);
  2. m_2\leftrightarrow (1,2);
  3. w_1\leftrightarrow (1,2);
  4. w_2\leftrightarrow (1,2);

De esta forma, tenemos que el casamiento S_1=\{(m_1,w_1),(m_2,w_2)\} es estable, mientras que el casamiento S_2=\{(m_1,w_2),(m_2,w_1)\} no lo es, pues tiene la inestabilidad (m_1,w_1) (Ojo! (m_1,w_1)\not\in S_2). Lo interesante de este problema es que, dada una configuración inicial con cualquier lista de preferencias, entonces existe un casamiento estable para esa configuración y esto viene implicitamente en el algoritmo que usaremos para solucionar el problema de casamiento estable:

  1. Inicialmente todo m\in M y w\in W estan libres o “solteros”;
  2. Mientras exista un hombre m libre que no le haya propuesto casamiento a todas las mujeres:
    1. Escoger un tal hombre m;
    2. Sea w la mujer de más alto rango en la lista de preferencia de m, a la que m aún no ha propuesto casamiento;
    3. Si w esta libre:
      1. (m,w) estan ahora comprometidos;
    4. Por el contrario, si w esta comprometida con m':
      1. Si w prefiere a m' antes que a m:
        1. m queda libre;
      2. En caso contrario, si w prefiere a m antes que a m':
        1. (m,w) estan ahora comprometidos;
        2. m' queda libre;
  3. Retorna el conjunto S de pares comprometidos;

Analisis del Algoritmo

Analizaremos el algoritmo con las siguientes observaciones:

  1. Una mujer w permanece comprometida desde el momento en que reciba le primer propuesta. La secuencia de parejas con los cuáles ella se va comprometiendo se tornan cada vez mejores (desde el punto de vista de preferencias de w);
  2. La secuencia de parejas a las cuáles un hombre m propone matrimonio se tornan cada vez peor;
  3. El algoritmo termina a lo máximo en n^2 iteraciones del ciclo “mientras”;
  4. Se un hombre m esta soltero en algún momento de la ejecución del algoritmo, entonces hay una mujer a la cuál m no le ha propuesto matrimonio;
  5. El conjunto S retornado por el algoritmo es un casamiento (perfecto);
  6. El conjunto S retornado por el algoritmo es un casamiento estable;

La observación que si merece una demostración es la última, pues no es claro que tal conjunto S retornado por el algoritmo sea un casamiento estable. Suponga que existe la inestabilidad (m,w'), donde

  1. (m,w),(m',w')\in S;
  2. m prefiere a w' por sobre w;
  3. w' prefiere a m por sobre m';

Por como funciona el algoritmo podemos afirmar que la última propuesta hecha por m fue a w, entonces nos hacemos la siguiente pregunta: ¿m le propone matrimonio a w' antes que a w durante la ejecución del algoritmo?

  1. Supongamos que no lo hizo. Esto significa w esta antes que w' en la lista de preferencias de m, pero esto no puede ser ya que estamos suponiendo lo contrario;
  2. Supongamos que si lo hizo. Entonces, dada la situación final, m fue rechazado por w' en favor de otro hombre m'', tal que w' lo prefiere antes que a m. Como m' es la pareja final de w', entonces existen 2 casos:
    1. Caso 1: m''=m'. Pero esto significa que w' prefiere a m' por sobre a m y estamos suponiendo lo contrario;
    2. Caso 2: w' prefiere a su pareja final m' por sobre a m''. Pero esto significa nuevamente, por un argumento de transitividad, que w' prefiere a m' por sobre a m, lo que nos vuelve a llevar a una contradicción.

Concluimos entonces que S es un casamiento estable.

Anuncios

Si te gustó el post, por favor dejanos tu comentario!!

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s