Una de las cosas que se nos viene
a la mente si escuchamos la palabra Nash es la teoría de juegos (o también la
película Una mente brillante); el profesor Nash desarrolló dicha teoría
especialmente en juegos no-cooperativos como el Dilema del prisionero,
donde el juego se basa en las acciones y reacciones de dos personas mantenidas
en forma separada. En este caso vamos a ver una variante de este supuesto: los
juegos cooperativos.
El profesor Lloyd S. Sharpley trabajó
precisamente en esta parte de la teoría de juegos, donde los participantes no
estaban separados y podían cooperar para llegar a la mejor decisión para todos.
Junto con el fallecido David Gale, desarrollan el algoritmo Gale – Sharpley con
el cual analizan el problema de los matrimonios estables, en donde se
establecía la mejor combinación de parejas entre una multitud de hombres y
mujeres expresando sus preferencias.
El planteamiento del problema (en
términos heurísticos) es el siguiente:
Tenemos un conjunto formado por N
hombres y N mujeres. Cada uno de ellos hace una lista de preferencias sobre el
grupo del sexo opuesto. Finalmente, se trata de hacer un emparejamiento en donde
en cada pareja, tanto el hombre como la mujer no preferirían estar con otras
personas que con sus actuales parejas, es decir, un emparejamiento estable.
Gale y Sharpley demuestran 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:
- En un comienzo todos están sin parejas.
- Para no caer en lo tradicional, vamos a suponer
que la mujer es la que propone matrimonio.
- Le propone matrimonio al primer hombre de su
lista y ocurre que:
o
Si el hombre está libre, se casan.
o
Si el hombre ya está emparejado le pregunta si
la prefiere a ella antes que a su pareja actual:
§
Si la prefiere a ella, el hombre se divorcia
§
Si no, entonces la mujer sigue y le propone
matrimonio al segundo de su lista.
Finalmente el resultado va a ser
un conjunto de parejas estables, aunque en este caso va a ser la solución
óptima para el conjunto de mujeres y la peor para el conjunto de hombres. Si, en
caso contrario, los hombres son los que proponen matrimonio, se obtiene la
solución óptima para ellos.
Si te gustó el problema del
matrimonio estable puedes jugar en el siguiente
enlace emparejando naipes.
Nota extra:
Cabe resaltar que Alvin E. Roth, quien
junto con Lloyd ganaron el premio Nobel en el 2012, realizaron aplicaciones de
este algoritmo y de sus teorías a problemas reales de asignación - justamente
por lo cual fueron acreedores al Nobel - como por ejemplo la de los graduados
médicos a puestos de trabajo equilibrando las preferencias de los médicos y las
condiciones de los hospitales que los contratan, teniendo en cuenta las
preferencias de las parejas de los médicos que muchas veces también son
médicos. También han trabajado para revolucionar el sistema de escuelas públicas
de New York y Boston, el sistema de admisión de las universidades
norteamericanas y el sistema de donación de órganos.
