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!!!