Un matrimonio estable

“… ¿como saber que te casas con la mejor de las parejas posibles?. El problema del matrimonio estable

12973196_1006281629453558_5811220229547142515_o

Después de una parada en la que he tenido que atender otros asuntos, volvemos a la carga con el tema que me trae de cabeza desde hace unos meses.

Aquí el problema:

Consideremos los habitantes de una pequeña aldea patagónica entre los que encontramos el mismo número de hombres que de mujeres. El problema consiste en encontrar la manera de formar matrimonios estables (heterosexuales por el momento) entre los diferentes miembros del grupo. Es decir, parejas que prefieran encontrarse juntos el uno al otro antes que con otra persona del grupo. Evidentemente, cada hombre y cada mujer tiene sus propias preferencias sobre los miembros del grupo del sexo opuesto con los cuales se querría casar. Pongamos el caso de dos parejas en el que a mujer de una de las parejas preferiría al hombre de la segunda pareja y viceversa. Esa sería una configuración inestable ya que pronto las parejas ser romperían y se formaría una nueva más estable.

¿Existe “siempre” un emparejamiento que lleve a una solución estable hasta que la muerte los separe?

Pues . Existe una solución. Si no, la entrada acabaría aquí y me podría ir a dormir y lo mejor es que para encontrarla no se necesitan números ni operaciones, pero no por ello el problema deja de ser matemático.

La solución la propusieron David Gale y Lloyd Sahpley en 1962 cuado construyeron un algoritmo que prueba que el emparejamiento es siempre posible. El algoritmo funciona de la siguiente manera (nota: el papel del hombre y de la mujer se pueden invertir. No hay intención alguna de poner ni al hombre ni a la mujer por encima del otro. Pero en el algoritmo hay que escoger):

  1. Cada hombre y mujer del grupo hace una lista de preferencias del sexo opuesto.
  2. El primer día, cada mujer se propone a su primera preferencia. De esta manera habrá hombres que recibirán más de una propuesta mientras que otros no recibirán ninguna.
  3. Los hombres que tengan más de una propuesta, se quedarán con aquella que figure en lo más alto de su lista de preferencias.
  4. El segundo día, las mujeres que hayan sido rechazadas se proponen a su segunda mejor opción, sin importar que ésta ya esté comprometida.
  5. Algunos hombres recibirán nuevas peticiones mientras que otros no recibirán ninguna. En el caso que se hayan comprometido en la primera ronda, tendrán la oportunidad de cambiar de pareja si la nueva propuesta se encuentra más alto en su lista de prioridades.
  6. El proceso se repite el número de veces que sea necesario hasta que ninguna de las mujeres sea rechazada.
  7. ¡Ya lo tenemos! En este punto hemos llegado a un emparejamiento global estable.

Pongamos un ejemplo. El número de miembros del conjunto puede ser arbitrariamente grande siempre que haya la misma cantidad de hombres que de mujeres. Para conservar un ejemplo simple reducimos el caso a tres hombres: Alberto, Benito y César, y tres mujeres: Diana, Eva y Flor. La lista de preferencias de cada uno es la siguiente.

Alberto: 1) Eva, 2) Diana, 3) Flor.

Benito: 1) Eva, 2) Diana, 3) Flor.

César: 1) Diana, 2) Flor, 3) Eva.

Diana: 1) Benito, 2) Alberto, 3) César.

Eva: 1) Benito, 2) César, 3) Alberto.

Flor: 1) Alberto, 2) Benito, 3) César

El primer día las mujeres se proponen a su mejor candidato. Benito recibe dos propuestas, Alberto una y César ninguna. Benito recibe propuestas de Diana y de Eva, que se encuentran en su número 2 y 1 respectivamente, así que escoge a Eva mientras que Eva es rechazada. Alberto no rechaza la oferta de Flor que, pese a encontrarse en su tercer puesto no tiene más opciones.

El segundo día, Diana se propone a su segunda preferencia, que es Alberto. Diana se encuentra en el segundo puesto de Alberto, superando a Flor, así que sin el mínimo respeto Alberto rechaza a Flor y se queda con Diana.

El tercer día Flor se propone a su segunda mejor opción que es Benito y es también rechazada ya que ya se encuentra comprometido con Eva que figura como prioridad en la lista. Así que a Flor no lo queda más que quedarse con César formando así tres parejas estables.

El ejemplo propuesto es muy cotidiano pero el algoritmo explicado tiene un amplio abanico de aplicaciones. Un ejemplo interesante es el de los estudiantes de medicina que han hecho el examen MIR y deben escoger plaza en algún hospital entre una limitada y competida oferta.

Otro ejemplo interesante es como gestionar la relación usuario/servidor en internet. A cada usuario se le debe asignar un servidor concreto entre los cientos de servidores repartidos por el mundo. Los usuarios prefieren servidores cercanos para obtener una respuesta rápida. A su vez, los servidores prefieren usuarios que demanden una carga de información baja.

Las matemáticas no son (necesariamente) números como ha quedado claro en este problema. Igual de claro como que yo no seguí este método para encontrar a la persona que me inspiró a escribir esta entrada. Ya que ha de quedar claro que formar parejas estables a base de un algoritmo matemático puede que sea muy frío pero de lo que uno no puede dudar es que es efectivo. Pensándolo bien, conozco de uno que sí elaboró una lista de preferencias entre las chicas del instituto y hoy, bastantes años después, todavía siguen juntos. ¡Las matemáticas funcionan!

 

—————————————————————————

Para subir nota. Para los matemáticamente inclinados el algoritmo en pseudocódigo suena tal que así:

function stableMatching {
    Initialize all m ∈ M and w ∈ W to free
    whilefree man m who still has a woman w to propose to {
       w = first woman on m’s list to whom m has not yet proposed
       if w is free
         (m, w) become engaged
       else some pair (m', w) already exists
         if w prefers m to m'
            m' becomes free
           (m, w) become engaged 
         else
           (m', w) remain engaged
    }
}

Ejercicio: elabore un ejemplo en su código de programación favorito y adjúntelo en el comentario.

Anuncios

Responder

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