Algoritmo de Gale-Shapley
En matemáticas , economía e informática , el algoritmo Gale-Shapley (también conocido como algoritmo de aceptación diferida o algoritmo de propuesta y rechazo ) es un algoritmo para encontrar una solución al problema de emparejamiento estable , llamado así por David Gale y Lloyd Shapley quien lo había descrito como la solución tanto del problema de admisión a la universidad como del matrimonio estable . Se necesita tiempo polinomial y el tiempo es lineal en el tamaño de la entrada al algoritmo. Es unmecanismo veraz desde el punto de vista de los proponentes, para quienes la solución siempre será óptima.
El problema de emparejamiento estable, en su forma más básica, toma como entrada un número igual de dos tipos de participantes ( n hombres y n mujeres, o n estudiantes de medicina y n pasantías, por ejemplo), y un orden para cada participante dando su preferencia por con quién ser emparejado entre los participantes del otro tipo. Siempre existe una coincidencia estable, y el problema algorítmico resuelto por el algoritmo Gale-Shapley es encontrar una. Una coincidencia no es estable si:
En otras palabras, una coincidencia es estable cuando no hay coincidencia ( A , B ) donde ambos participantes prefieren a otra persona a su pareja actual.
En 1962, David Gale y Lloyd Shapley demostraron que, para cualquier número igual de hombres y mujeres, siempre es posible resolver el SMP y estabilizar todos los matrimonios. Presentaron un algoritmo para hacerlo. [1] [2] En 1984, Alvin E. Roth observó que esencialmente el mismo algoritmo ya había estado en uso práctico desde principios de la década de 1950, en el Programa Nacional de Emparejamiento de Residentes . [3]
La complejidad del tiempo de ejecución de este algoritmo es dónde está el número de hombres o mujeres. [4] Dado que las listas de preferencias de entrada también tienen un tamaño proporcional a , el tiempo de ejecución es lineal en el tamaño de entrada.
La existencia de diferentes emparejamientos estables plantea la pregunta: ¿qué emparejamiento devuelve el algoritmo Gale-Shapley? ¿Es el emparejamiento mejor para hombres, para mujeres o el intermedio? En el ejemplo anterior, el algoritmo converge en una sola ronda en la solución óptima para hombres porque cada mujer recibe exactamente una propuesta y, por lo tanto, elige esa propuesta, asegurando que cada hombre tenga una oferta aceptada, finalizando el emparejamiento.
