En matemáticas , economía y ciencias de la computación , el algoritmo de Gale-Shapley (también conocido como algoritmo de aceptación diferida , [1] algoritmo de proponer y rechazar , [2] o algoritmo de Boston Pool [1] ) es un algoritmo para encontrar una solución al problema de emparejamiento estable . Recibe su nombre de David Gale y Lloyd Shapley , quienes lo publicaron en 1962, aunque se había utilizado para el Programa Nacional de Emparejamiento de Residentes desde principios de la década de 1950. Shapley y Alvin E. Roth (quien señaló su aplicación anterior) ganaron el Premio Nobel de Economía de 2012 por el trabajo que incluía este algoritmo.
El problema de emparejamiento estable busca emparejar cantidades iguales de participantes de dos tipos, utilizando las preferencias de cada participante. El emparejamiento debe ser estable: ningún par de participantes debe preferir al otro antes que a su pareja asignada. En cada ronda del algoritmo Gale-Shapley, los participantes no emparejados de un tipo proponen una pareja al siguiente participante en su lista de preferencias. Cada propuesta es aceptada si su receptor la prefiere a su pareja actual. El procedimiento resultante es un mecanismo veraz desde el punto de vista de los participantes proponentes, quienes reciben su pareja preferida consistente con la estabilidad. Por el contrario, los receptores de las propuestas reciben su pareja menos preferida. El algoritmo puede implementarse para ejecutarse en un tiempo cuadrático en el número de participantes y lineal en el tamaño de la entrada al algoritmo.
El problema del emparejamiento estable y el algoritmo de Gale-Shapley que lo resuelve tienen amplias aplicaciones en el mundo real, como la vinculación de estudiantes de medicina estadounidenses con residencias y de aspirantes a universidades francesas con escuelas. Para obtener más información, consulte Problema del matrimonio estable § Aplicaciones .
El problema de emparejamiento estable, en su forma más básica, toma como entrada cantidades iguales de dos tipos de participantes ( n solicitantes de empleo y n empleadores, por ejemplo) y un orden para cada participante que indica su preferencia sobre con quién emparejarse entre los participantes del otro tipo. Un emparejamiento empareja a cada participante de un tipo con un participante del otro tipo. Un emparejamiento no es estable si:
En otras palabras, un emparejamiento es estable cuando no existe un par ( A , B ) en el que ambos participantes se prefieran entre sí antes que a sus parejas emparejadas. Si existe dicho par, el emparejamiento no es estable, en el sentido de que los miembros de este par preferirían abandonar el sistema y ser emparejados entre sí, posiblemente dejando a otros participantes sin emparejamiento. Siempre existe un emparejamiento estable, y el problema algorítmico que resuelve el algoritmo de Gale-Shapley es encontrar uno. [3]
El problema del emparejamiento estable también se ha denominado el problema del matrimonio estable , utilizando una metáfora del matrimonio entre hombres y mujeres, y muchas fuentes describen el algoritmo de Gale-Shapley en términos de propuestas de matrimonio . Sin embargo, esta metáfora ha sido criticada por ser sexista y poco realista: los pasos del algoritmo no reflejan con precisión el comportamiento humano típico o incluso estereotipado. [4] [5]
En 1962, David Gale y Lloyd Shapley demostraron que, para cualquier número igual de participantes de cada tipo, siempre es posible encontrar un emparejamiento en el que todos los pares sean estables. Presentaron un algoritmo para lograrlo. [6] [7] En 1984, Alvin E. Roth observó que, esencialmente, el mismo algoritmo ya se había utilizado en la práctica desde principios de la década de 1950, como el "algoritmo Boston Pool" utilizado por el Programa Nacional de Emparejamiento de Residentes . [1] [8]
El algoritmo de Gale-Shapley implica una serie de "rondas" (o " iteraciones "). En términos de solicitantes de empleo y empleadores, se puede expresar de la siguiente manera: [9]
Para implementar el algoritmo de manera eficiente, cada empleador debe poder encontrar rápidamente a su próximo postulante y cada postulante debe poder comparar empleadores rápidamente. Una forma de hacer esto es numerar a cada postulante y empleador de 1 a , donde es el número de empleadores y postulantes, y almacenar las siguientes estructuras de datos : [10]
La creación de estas estructuras de datos lleva tiempo. Con ellas es posible encontrar un empleador con un puesto vacante, hacer una oferta de ese empleador a su próximo solicitante, determinar si la oferta es aceptada y actualizar todas las estructuras de datos para reflejar los resultados de estos pasos, en un tiempo constante por oferta. Una vez que el algoritmo termina, la coincidencia resultante se puede leer de la matriz de empleadores para cada solicitante. Puede haber ofertas antes de que cada empleador se quede sin ofertas para hacer, por lo que el tiempo total es . [10]
Aunque este límite de tiempo es cuadrático en el número de participantes, puede considerarse como un tiempo lineal cuando se mide en términos del tamaño de la entrada, dos matrices de preferencias de tamaño . [11]
Este algoritmo garantiza que:
Puede haber muchas coincidencias estables para el mismo sistema de preferencias. Esto plantea la pregunta: ¿qué coincidencia arroja el algoritmo de Gale-Shapley? ¿Es la mejor para los solicitantes, para los empleadores o una intermedia? Resulta que el algoritmo de Gale-Shapley en el que los empleadores hacen ofertas a los solicitantes siempre produce la misma coincidencia estable (independientemente del orden en que se hagan las ofertas de trabajo), y su elección es la coincidencia estable que es la mejor para todos los empleadores y la peor para todos los solicitantes entre todas las coincidencias estables. [9]
En una forma inversa del algoritmo, cada ronda consiste en que los solicitantes desempleados escriban una única solicitud de empleo a su empleador preferido, y el empleador acepte la solicitud (posiblemente despidiendo a un empleado existente para hacerlo) o la rechace. Esto produce una correspondencia que es mejor para todos los solicitantes y peor para todos los empleadores entre todas las correspondencias estables. Estas dos correspondencias son los elementos superior e inferior de la red de correspondencias estables . [12]
En ambas formas del algoritmo, un grupo de participantes propone propuestas y el otro grupo decide si acepta o rechaza cada propuesta. La mejor opción para el grupo que hace las propuestas es siempre la peor para el grupo que decide cómo manejar cada propuesta. [12]
El algoritmo de Gale-Shapley es un mecanismo veraz desde el punto de vista del proponente. Esto significa que ningún proponente puede obtener una mejor correspondencia tergiversando sus preferencias. Además, el algoritmo de Gale-Shapley es incluso una prueba de estrategia de grupo para los proponentes, es decir, ninguna coalición de proponentes puede coordinar una tergiversación de sus preferencias de modo que todos los proponentes de la coalición estén estrictamente en mejor situación. [13] Sin embargo, es posible que alguna coalición tergiverse sus preferencias de modo que algunos proponentes estén en mejor situación y los demás mantengan el mismo socio. [14]
El algoritmo de Gale-Shapley no es veraz para los participantes que no proponen. Cada uno puede ser capaz de tergiversar sus preferencias y obtener una mejor coincidencia. [15] Una forma particular de manipulación es el truncamiento : presentar solo las alternativas superiores, lo que implica que las alternativas inferiores no son aceptables en absoluto. Con información completa, es suficiente considerar tergiversaciones de la forma de las estrategias de truncamiento. Sin embargo, la tergiversación exitosa requiere el conocimiento de las preferencias de los otros agentes; sin dicho conocimiento, la tergiversación puede dar a un agente una peor asignación. Además, incluso después de que un agente ve la coincidencia final, no puede deducir una estrategia que garantice un mejor resultado en retrospectiva. Esto hace que el algoritmo de Gale-Shapley sea un mecanismo de decir la verdad sin arrepentimiento . Además, en el algoritmo de Gale-Shapley, decir la verdad es la única estrategia que garantiza que no haya arrepentimiento. El algoritmo de Gale-Shapley es el único mecanismo sin arrepentimiento en la clase de mecanismos de coincidencia estables en cuanto a cuantiles. [16]
En su trabajo original sobre el problema, Gale y Shapley consideraron una forma más general del problema de emparejamiento estable, adecuada para la admisión a universidades y colegios . En este problema, cada universidad o colegio puede tener su propia cuota , un número objetivo de estudiantes a admitir, y el número de estudiantes que solicitan admisión puede diferir de la suma de las cuotas, lo que necesariamente hace que algunos estudiantes permanezcan sin emparejamiento o que algunas cuotas permanezcan sin cubrir. Además, las listas de preferencias pueden estar incompletas: si una universidad omite a un estudiante de su lista, significa que preferiría dejar su cuota sin cubrir que admitir a ese estudiante, y si un estudiante omite una universidad de su lista, significa que preferiría permanecer sin ser admitido que ir a esa universidad. Sin embargo, es posible definir emparejamientos estables para este problema más general, para demostrar que siempre existen emparejamientos estables y para aplicar el mismo algoritmo para encontrar uno. [6]
Desde 2018, en Francia se utiliza una variante del algoritmo Gale-Shapley, ejecutado mediante un protocolo del mundo real en lugar de calcularse en computadoras, para coordinar las admisiones a la educación superior mediante el sistema Parcoursup . En este proceso, durante el verano anterior al inicio de las clases, los solicitantes reciben ofertas de admisión y deben elegir en cada ronda del proceso si aceptan alguna nueva oferta (y, en caso afirmativo, rechazar cualquier oferta anterior que hayan aceptado). El método se complica por restricciones adicionales que hacen que el problema que resuelve no sea exactamente el problema de emparejamiento estable. Tiene la ventaja de que los estudiantes no necesitan comprometerse con sus preferencias al inicio del proceso, sino que pueden determinar sus propias preferencias a medida que avanza el algoritmo, sobre la base de comparaciones directas entre las ofertas que han recibido. Es importante que este proceso realice un pequeño número de rondas de propuestas, de modo que finalice antes de la fecha de inicio de las escuelas, pero aunque en teoría puede haber un gran número de rondas, en la práctica tienden a no ocurrir. [17] Se ha demostrado teóricamente que, si el algoritmo Gale-Shapley necesita ser terminado anticipadamente, después de una pequeña cantidad de rondas en las que cada posición vacante hace una nueva oferta, de todas formas produce emparejamientos que tienen una alta proporción de participantes emparejados con respecto a pares inestables. [18]
Shapley y Roth recibieron el Premio Nobel de Economía en 2012 "por la teoría de las asignaciones estables y la práctica del diseño de mercado ". Gale había fallecido en 2008, por lo que no podía optar al premio. [19]
