Cómo funciona, en detalle
Dos grupos distintos se clasifican mutuamente. El lado 1 propone, el lado 2 dispone, y cada entrada del lado 2 puede tener una capacidad de varias plazas.
Cada proponente solicita su primera opción. Cada receptor retiene provisionalmente a los mejores candidatos dentro de su capacidad y descarta a los demás. Nada es definitivo: ese es todo el sentido de la aceptación DIFERIDA.
Los candidatos descartados proponen a su siguiente opción, lo que puede desplazar a un candidato retenido provisionalmente, que vuelve a proponer. Se para cuando nadie tiene ya ninguna propuesta que hacer.
El resultado es estable: ninguna pareja candidato-formación se preferiría mutuamente a su asignación. Además es ÓPTIMO para el lado que propone: entre todos los emparejamientos estables, cada proponente obtiene el mejor posible.
Un ejemplo con cifras
Tres candidatos, tres formaciones de una plaza cada una, clasificaciones cruzadas.
| Candidato | Deseos | Formación | Clasificación |
|---|---|---|---|
| Chloé | A, B, C | A | Ali, Chloé, Bruno |
| Ali | A, C, B | B | Chloé, Bruno, Ali |
| Bruno | B, A, C | C | Bruno, Chloé, Ali |
- Vuelta 1: Chloé y Ali proponen a A, Bruno a B. A prefiere a Ali y descarta a Chloé; B retiene a Bruno.
- Vuelta 2: Chloé propone a B. B prefiere a Chloé antes que a Bruno y permuta: Bruno queda desplazado.
- Vuelta 3: Bruno propone a A, que conserva a Ali; luego a C, que le acepta. Fin: Ali→A, Chloé→B, Bruno→C.
Bruno fue retenido y luego desplazado: es la mecánica del diferido y la razón por la que los resultados de Parcoursup se mueven durante semanas. El resultado final es estable.
De dónde viene
David Gale y Lloyd Shapley publican en 1962 « College Admissions and the Stability of Marriage » en el American Mathematical Monthly. Demuestran que un emparejamiento estable entre dos grupos existe SIEMPRE y dan un algoritmo simple para construirlo: la aceptación diferida.
Golpe de efecto histórico: el National Resident Matching Program, que asigna desde 1952 a los residentes médicos estadounidenses a los hospitales, ya usaba un algoritmo equivalente, descubierto empíricamente diez años antes de su teorización. Alvin Roth lo demuestra en 1984 y dirige su refundición de 1998 para tratar el caso de las parejas.
Roth y Shapley reciben el Nobel de Economía 2012 por la teoría de las asignaciones estables y el diseño de mercados. En Francia, Parcoursup aplica este principio desde 2018, en sustitución de APB, con un contestador automático que hace las veces de aceptación diferida.
Dónde se usa
- Parcoursup y las asignaciones postbachillerato francesas.
- Residencia médica estadounidense (NRMP) desde 1952.
- Asignación de alumnos a centros en Nueva York y Boston, refundida por Roth y sus colegas.
- Programas de mentoría, prácticas y atribución de proyectos entre dos poblaciones distintas.
Límites y trampas
- Siempre un emparejamiento estable
- Gestiona capacidades (varias plazas por entrada del lado 2)
- Clasificar con sinceridad es óptimo para el lado 1
- Favorece estructuralmente al lado que propone
- El lado 2 puede clasificar de forma táctica
- Quedan sin asignar si faltan plazas
Preguntas frecuentes
¿Por qué cambia mi asignación sobre la marcha?
Porque la aceptación es diferida: se le reserva una plaza provisionalmente y un candidato mejor clasificado puede desplazarle, igual que usted puede desplazar a otro en otro sitio. El proceso solo se fija al final, y eso es lo que garantiza la estabilidad del resultado.
¿Me interesa clasificar tácticamente mis deseos?
Si está del lado que propone — los candidatos, en Parcoursup — no: clasificar sinceramente es demostradamente óptimo. Poner primero un deseo que juzga « realista » en vez del que realmente quiere solo puede perjudicarle.
¿Qué quiere decir « estable »?
Que ninguna pareja candidato-formación se preferiría mutuamente a lo que obtuvo. Sin esa propiedad, se cerrarían acuerdos paralelos fuera del dispositivo: exactamente lo que ocurría en Estados Unidos antes de 1952.
¿Qué diferencia hay con el turno de elección?
El turno de elección solo hace clasificar a un lado: las opciones no opinan. Aquí ambos lados se clasifican y la asignación debe satisfacer a los dos, de ahí la noción de estabilidad, que no tiene sentido en un turno de elección.
Fuentes
Las referencias primarias en las que se apoya esta ficha.
- Gale, David et Shapley, Lloyd S., College Admissions and the Stability of Marriage, The American Mathematical Monthly, 69(1), 9-15, 1962. DOI ↗
- Dubins, Lester E. et Freedman, David A., Machiavelli and the Gale-Shapley Algorithm, The American Mathematical Monthly, 88(7), 485-494, 1981. DOI ↗
- Roth, Alvin E., The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory, Journal of Political Economy, 92(6), 991-1016, 1984. DOI ↗
- Roth, Alvin E. et Peranson, Elliott, The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design, American Economic Review, 89(4), 748-780, 1999. DOI ↗
- Comité du prix de sciences économiques de l'Académie royale des sciences de Suède, Stable allocations and the practice of market design (Scientific Background, prix de sciences économiques en mémoire d'Alfred Nobel), Nobelprize.org, document « Advanced information », 15 octobre 2012, 2012. ↗