jueves, 12 de octubre de 2017

Algoritmo de Gale-Shapley

El llamado The Stable Marriage Problem o 'Problema de las Parejas Estables' fue planteado y resuelto mediante un algoritmo por David Gale y Lloyd Shapley en 1962. Su aplicación más conocida es la asignación de estudiantes de medicina recién graduados a los hospitales correspondientes.

Cada chico ordena a sus posibles compañeras según sus preferencias y viceversa. En el ejemplo de la tabla el VERDE indica si forman pareja y el ROJO si no pueden ser pareja por el rechazo de la chica.
  • Cada chico invita a bailar a su primera opción.
  • Cada chica evalúa las propuestas, escoge la mejor y desecha las demás.
  • Cada chico rechazado invita a bailar a su segunda opción, aunque en ese momento esté con otro.
  • Se itera el proceso hasta que todas las chicas tengan una única invitación.
Todos eligen a su chica preferida, pero como Julia prefiere a Mateo, rechaza a Pedro.
Diego elige a Laura que prefiere seguir con Jorge y rechaza a Diego.
Diego elige a Elena que estaba con Pedro y lo deja porque prefiere a Diego.
Esto obliga a Pedro a elegir a Laura que acepta renunciando a Jorge.
Finalmente Jorge elige a Paula que acepta y las parejas estables son:
(Diego,Elena), (Jorge,Paula), (Mateo,Julia) y (Pedro,Laura).

¡¡¡ Siempre hay un emparejamiento estable!!!