Algoritmo de Gale-Shapley

En matemáticas , economía e informática , el algoritmo de Gale-Shapley (también conocido como algoritmo de aceptación diferida , ^{[ 1 ]} algoritmo de propuesta y rechazo , ^{[ 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 ya se utilizaba en 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 previa) ganaron el Premio Nobel de Economía de 2012 por un trabajo que incluía este algoritmo.

El problema de emparejamiento estable busca emparejar un número igual de participantes de dos tipos, utilizando las preferencias de cada participante. El emparejamiento debe ser estable: ningún par de participantes emparejados debe preferirse mutuamente a su pareja asignada. En cada ronda del algoritmo de Gale-Shapley, los participantes no emparejados de un tipo proponen un emparejamiento al siguiente participante en su lista de preferencias. Cada propuesta se acepta si el receptor la prefiere a su pareja actual. El procedimiento resultante es un mecanismo veraz desde el punto de vista de los participantes que proponen, quienes reciben el emparejamiento que más prefieren, de acuerdo con la estabilidad. Por el contrario, los receptores de las propuestas reciben el emparejamiento que menos prefieren. El algoritmo puede implementarse para ejecutarse en un tiempo cuadrático con respecto al número de participantes y lineal con respecto al tamaño de la entrada al algoritmo.

El problema del emparejamiento estable, y el algoritmo de Gale-Shapley que lo resuelve, tienen numerosas aplicaciones prácticas, como la asignación de plazas de residencia a estudiantes de medicina estadounidenses y de plazas de ingreso a universidades francesas. Para más información, consulte el apartado Aplicaciones del problema del matrimonio estable  .

El problema de emparejamiento estable, en su forma más básica, toma como entrada un número igual de participantes de dos tipos ( por ejemplo, n solicitantes de empleo y n empleadores), y un ordenamiento 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 ningún par ( A , B ) en el que ambos participantes se prefieran mutuamente a sus parejas emparejadas. Si existe tal par, el emparejamiento no es estable, en el sentido de que los miembros de este par preferirían abandonar el sistema y emparejarse entre sí, lo que posiblemente dejaría a otros participantes sin emparejar. Siempre existe un emparejamiento estable, y el problema algorítmico que resuelve el algoritmo de Gale-Shapley es encontrarlo. ^{[ 3 ]}

El problema del emparejamiento estable también se ha denominado problema del matrimonio estable , utilizando la 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, ni siquiera 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 todas las parejas sean estables. Presentaron un algoritmo para lograrlo. ^{[ 6 ] [ 7 ]} En 1984, Alvin E. Roth observó que esencialmente el mismo algoritmo ya se había estado utilizando en la práctica desde principios de la década de 1950, como el "algoritmo de 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 ]}

• En cada ronda, uno o más empleadores con puestos de trabajo vacantes hacen una oferta de empleo al candidato que prefieren, de entre aquellos a los que aún no les han hecho una oferta.
• Cada solicitante que recibe una oferta la evalúa en función de su puesto actual (si lo tiene). Si el solicitante aún no está empleado, o si recibe una oferta de un empleador que le resulta más atractiva que la actual, acepta la mejor oferta y se incorpora al nuevo empleador (lo que podría dejar vacante el puesto en su anterior empresa). De lo contrario, rechaza la nueva oferta.
• Este proceso se repite hasta que todos los empleadores hayan cubierto sus puestos o hayan agotado sus listas de solicitantes.

Puede haber muchas coincidencias estables para el mismo sistema de preferencias. Esto plantea la pregunta: ¿qué coincidencia devuelve 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 versión inversa del algoritmo, cada ronda consiste en que los solicitantes desempleados envían una única solicitud de empleo a su empleador preferido, y este la acepta (posiblemente despidiendo a un empleado existente para ello) o la rechaza. Esto produce una asignación que es la mejor para todos los solicitantes y la peor para todos los empleadores entre todas las asignaciones estables. Estas dos asignaciones son los elementos superior e inferior de la red de asignaciones estables . ^{[ 12 ]}

En ambas versiones del algoritmo, un grupo de participantes propone emparejamientos y el otro grupo decide si acepta o rechaza cada propuesta. El emparejamiento siempre es mejor para el grupo que hace las propuestas y peor para el grupo que decide cómo gestionarlas. ^{[ 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 coincidencia tergiversando sus preferencias. Además, el algoritmo de Gale-Shapley es incluso inmune a la estrategia de grupo para los proponentes; es decir, ninguna coalición de proponentes puede coordinar una tergiversación de sus preferencias de tal manera que todos los proponentes de la coalición se vean estrictamente beneficiados. ^{[ 13 ]} Sin embargo, es posible que alguna coalición tergiverse sus preferencias de tal manera que algunos proponentes se vean beneficiados y los demás conserven al mismo socio. ^{[ 14 ]}

El algoritmo de Gale-Shapley no es veraz para los participantes que no proponen. Cada uno puede tergiversar sus preferencias y obtener una mejor coincidencia. ^{[ 15 ]} Una forma particular de manipulación es la truncación : presentar solo las alternativas superiores, lo que implica que las alternativas inferiores no son aceptables en absoluto. Con información completa, basta con considerar tergiversaciones en forma de estrategias de truncamiento. Sin embargo, una tergiversación exitosa requiere conocer las preferencias de los demás 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 vea la coincidencia final, no puede deducir una estrategia que garantice un mejor resultado en retrospectiva. Esto convierte al algoritmo de Gale-Shapley en un mecanismo de veracidad sin arrepentimiento . Además, en el algoritmo de Gale-Shapley, decir la verdad es la única estrategia que garantiza la ausencia de arrepentimiento. El algoritmo de Gale-Shapley es el único mecanismo sin arrepentimiento en la clase de mecanismos de coincidencia cuantil-estables. ^{[ 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 facultades . En este problema, cada universidad o facultad 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 provoca que algunos estudiantes queden sin emparejar o que algunas cuotas queden 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 antes que admitir a ese estudiante, y si un estudiante omite una universidad de su lista, significa que preferiría no ser admitido antes que ir a esa universidad. Sin embargo, es posible definir emparejamientos estables para este problema más general, demostrar que siempre existen emparejamientos estables y aplicar el mismo algoritmo para encontrar uno. ^{[ 6 ]}

Una variante del algoritmo de Gale-Shapley, implementada mediante un protocolo real en lugar de cálculos informáticos, se utiliza para coordinar las admisiones a la educación superior en Francia desde 2018, a través del sistema Parcoursup . En este proceso, durante el verano previo al inicio del curso, los solicitantes reciben ofertas de admisión y deben elegir en cada ronda 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 de la asignación estable. Tiene la ventaja de que los estudiantes no necesitan comprometerse con sus preferencias al inicio del proceso, sino que pueden determinarlas a medida que avanza el algoritmo, basándose en comparaciones directas entre las ofertas recibidas. Es importante que este proceso realice un número reducido de rondas de propuestas, de modo que finalice antes del inicio del curso, pero aunque en teoría se pueden realizar muchas rondas, en la práctica no suelen darse. ^{[ 17 ]} Se ha demostrado teóricamente que, si el algoritmo de Gale-Shapley necesita terminarse antes de tiempo, después de un pequeño número de rondas en las que cada posición vacante hace una nueva oferta, aun así produce emparejamientos que tienen una alta proporción de participantes emparejados con respecto a pares inestables. ^{[ 18 ]}

El algoritmo de Gale-Shapley posee una fuente natural de paralelismo que lo hace adecuado para hardware paralelo, como CPU multinúcleo y unidades de procesamiento gráfico (GPU). En cada ronda, todos los empleadores con puestos vacantes pueden avanzar de forma independiente en sus listas de preferencias y realizar ofertas simultáneamente. Una implementación paralela puede asignar hilos a empleadores independientes para que se realicen múltiples ofertas al mismo tiempo. Cuando varios empleadores realizan ofertas al mismo solicitante, se utilizan primitivas de sincronización para resolver las ofertas en competencia, asegurando que solo el empleador preferido del solicitante sea aceptado provisionalmente, mientras que los empleadores rechazados continúan con sus siguientes opciones. ^{[ 19 ] [ 20 ]}

Para reducir la sobrecarga de sincronización, es ventajoso evitar devolver repetidamente a los empleadores rechazados al conjunto compartido de empleadores con puestos vacantes, ya que las actualizaciones simultáneas de este conjunto requieren sincronización. En cambio, un empleador rechazado pasa inmediatamente al siguiente solicitante en su lista de preferencias. Si un solicitante acepta una nueva oferta, el empleador desplazado también continúa desde su siguiente preferencia. ^{[ 19 ] [ 20 ]}

Otras técnicas de optimización incluyen estructuras de datos con conciencia de localidad, que combinan la matriz de preferencias del empleador con la matriz de clasificación del solicitante para reducir los accesos aleatorios a la memoria y mejorar la eficiencia de la caché, y primitivas de sincronización avanzadas, que resuelven la contención entre ofertas simultáneas de manera más eficiente. Los enfoques heterogéneos mejoran aún más el rendimiento al usar la GPU para etapas altamente paralelas y cambiar a la CPU cuando quedan pocos empleadores sin emparejar, evitando la subutilización de la GPU durante el trabajo mayoritariamente secuencial. ^{[ 20 ]}

Shapley y Roth recibieron el Premio Nobel de Economía de 2012 «por la teoría de las asignaciones estables y la práctica del diseño de mercados ». Gale había fallecido en 2008, por lo que no cumplía los requisitos para recibir el premio. ^{[ 21 ]}

• Subasta de aceptación diferida
• Problema de compañeros de piso estables
• Problema del restaurante Kolkata Paise