Algoritmo de Gale-Shapley
- Propuesto por
- David Gale, Lloyd Shapley
- Año
- 1962
- Tipo
- algorithm
- Familia
- Game-theoretic
Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés
¿Qué hace?
El algoritmo de Gale-Shapley resuelve el problema del matrimonio estable: cómo emparejar dos grupos (por ejemplo, residentes médicos con hospitales, estudiantes con escuelas) de tal manera que ningún par se prefiera mutuamente a sus parejas asignadas.
Introducido por David Gale y Lloyd Shapley en 1962, el algoritmo garantiza una correspondencia estable en tiempo polinomial a través de un proceso de aceptación diferida donde un lado propone secuencialmente y el otro lado responde, revisando las opciones a medida que llegan mejores opciones.
La intuición detrás del método
Imagine emparejar médicos con hospitales. El algoritmo funciona como un juego de las sillas musicales: cada médico propone al hospital de su máxima preferencia; cada hospital acepta tentativamente al mejor médico disponible. A medida que los hospitales reciben mejores propuestas, revisan sus elecciones, pudiendo rechazar aceptaciones anteriores. Los médicos que son rechazados proponen al hospital de su siguiente preferencia. El proceso continúa hasta que ningún médico quiera proponer más y ningún hospital quiera cambiar su pareja actual. El resultado es estable: ningún par médico-hospital preferiría mutuamente estar emparejado entre sí en lugar de con sus parejas asignadas.
Historia
David Gale y Lloyd Shapley publicaron su solución al problema del matrimonio estable en 1962, demostrando que las correspondencias estables siempre existen para los mercados bilaterales. Su algoritmo generó una vasta literatura sobre teoría de emparejamiento con aplicaciones que abarcan la medicina, la educación y los mercados laborales. En 2012, Alvin Roth ganó el Premio Nobel de Economía por su trabajo experimental y teórico aplicando la teoría de emparejamiento al diseño de mercados reales, validando la importancia práctica del marco de Gale-Shapley.
Cuándo usarlo
Aplique el algoritmo de Gale-Shapley al emparejar mercados bilaterales donde la estabilidad es crucial: asignación de residentes médicos, asignación de estudiantes a escuelas, intercambio de riñones, emparejamiento en el mercado laboral o mercados de citas en línea. Úselo cuando exista el riesgo de inestabilidad en el emparejamiento (pares de bloqueo) que podría deshacer un emparejamiento después de la asignación. El algoritmo es ideal cuando un lado puede moverse primero con una ventaja estratégica.
Limitaciones y consideraciones
- No es Pareto óptimo: la correspondencia puede no maximizar el bienestar total; pueden existir pares de bloqueo que todos se beneficien del intercambio de parejas
- Vulnerabilidad estratégica: el lado proponente puede ganar al tergiversar sus preferencias, mientras que el lado respondedor es veraz
- Asimetría: los resultados dependen en gran medida de qué lado propone primero
- No maneja restricciones: difícil incorporar preferencias complejas (por ejemplo, parejas, preferencias regionales) sin modificación algorítmica
Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.
Fortalezas
- Estabilidad garantizada: no existen pares de bloqueo en la correspondencia final
- Tiempo polinomial: complejidad O(n^2), lo que lo hace eficiente para grandes poblaciones
- Implementación sencilla: fácil de ejecutar en la práctica con una recopilación transparente de preferencias
- Incentivos estratégicos: el lado proponente tiene una ventaja estratégica, prefiriendo las propuestas tempranas a las tardías
- Aplicabilidad universal: funciona para cualquier perfil de preferencias sin asumir convexidad o transitividad
Aplicaciones
- Asignación de residentes médicos: emparejar a graduados de escuelas de medicina con programas de residencia hospitalaria a través del NRMP
- Elección de escuela: asignar estudiantes a escuelas públicas basándose en preferencias y restricciones de capacidad
- Intercambio de riñones: emparejar donantes y receptores de órganos para maximizar trasplantes compatibles
- Emparejamiento en el mercado laboral: conectar a buscadores de empleo con empleadores en mercados laborales bilaterales
- Citas en línea: emparejar usuarios en plataformas de citas para mejorar la estabilidad de las correspondencias y la satisfacción del usuario
Cómo funciona
Cómo funciona
Crear listas de preferencias para todos los individuos en ambos grupos, representando su clasificación del otro lado.
En cada ronda, cada persona no emparejada del lado proponente propone a la persona de mayor rango del otro lado a la que aún no se ha propuesto.
Cada persona del lado receptor acepta tentativamente la propuesta si no está emparejada, o si el proponente tiene un rango superior al de su pareja actual, en cuyo caso revoca el compromiso anterior.
El algoritmo se detiene cuando todas las personas están emparejadas y no ocurren más propuestas, produciendo una correspondencia estable.
Errores comunes
- Asumir que la estabilidad por sí sola es suficiente para la equidad o el bienestar; las correspondencias estables pueden estar muy sesgadas hacia un lado
- Confundir estabilidad con optimalidad; una correspondencia estable no es necesariamente maximizadora del bienestar
- Pasar por alto la ventaja estratégica del lado proponente: los miembros del lado proponente tienden a emparejarse con parejas de mayor rango
- Olvidar que el algoritmo asume listas de preferencias completas; las preferencias incompletas requieren modificación
Preguntas frecuentes
¿Por qué es importante la estabilidad en el emparejamiento?
Sin estabilidad, las parejas emparejadas podrían descubrir más tarde que se prefieren mutuamente a sus parejas asignadas, creando un incentivo para romper el emparejamiento. Las correspondencias estables evitan tales pares de bloqueo, asegurando que el emparejamiento persista sin renegociación.
¿El algoritmo de Gale-Shapley produce siempre la misma correspondencia?
No. Diferentes listas de preferencias u órdenes de propuesta pueden generar diferentes correspondencias estables. Sin embargo, siempre existe una correspondencia estable 'óptima para el hombre' (la mejor para todos los proponentes) y una correspondencia estable 'óptima para la mujer' (la mejor para todos los respondedores).
¿Cómo maneja Gale-Shapley las preferencias sobre grupos (por ejemplo, parejas)?
El algoritmo estándar no maneja directamente parejas u otras restricciones. Existen extensiones como el algoritmo de parejas, pero son más complejas y pueden no garantizar la estabilidad para todos los perfiles de preferencias.
Métodos relacionados
Fuentes
Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9-15.
Abrir referencia DOICopiado.Roth, A. E. (1984). The economics of matching: Stability and incentives. Mathematics of Operations Research, 7(4), 617-628.
Abrir referencia DOICopiado.