Cómo funciona, en detalle
Cada cual clasifica a TODOS los demás participantes. Solo hay un grupo, así que ninguna asimetría entre proponentes y receptores.
Primera fase: cada cual propone al mejor clasificado que aún no le ha rechazado; las propuestas que mejoran se aceptan provisionalmente, las peores se rechazan. Se obtiene una tabla reducida.
Segunda fase: se detectan y suprimen las rotaciones — cadenas de preferencias cíclicas que impiden la estabilidad — hasta que cada cual no tenga más que un compañero, o hasta que la tabla se vacíe, lo que prueba la ausencia de solución.
El emparejamiento obtenido es estable: ninguna pareja de personas no emparejadas entre sí se prefiere mutuamente a su compañero actual.
Un ejemplo con cifras
Cuatro personas a emparejar, cada una habiendo clasificado a las otras tres.
| Persona | 1º | 2º | 3º |
|---|---|---|---|
| Chloé | Ali | Bruno | Dana |
| Ali | Chloé | Dana | Bruno |
| Bruno | Dana | Chloé | Ali |
| Dana | Bruno | Ali | Chloé |
- Chloé y Ali se colocan mutuamente en primer lugar: la pareja se impone.
- Bruno y Dana hacen lo mismo: segunda pareja.
- Ninguna pareja exterior se prefiere mutuamente: el emparejamiento es estable.
Aquí las preferencias encajan perfectamente. Modifique una sola clasificación y el emparejamiento estable puede desaparecer por completo: es la fragilidad propia de este problema.
De dónde viene
El problema lo plantean en 1962 David Gale y Lloyd Shapley, al final de su artículo fundador sobre el matrimonio estable: ¿y si, en vez de dos grupos distintos, todo el mundo perteneciera al mismo conjunto? Señalan que su algoritmo no se aplica y dejan la cuestión abierta.
Demuestran de paso que un emparejamiento estable puede sencillamente NO EXISTIR, diferencia esencial con el matrimonio estable, donde siempre existe alguno.
Robert Irving publica en 1985 el primer algoritmo en tiempo polinómico: determina si existe una solución estable y la construye en su caso, en dos fases, la segunda de las cuales elimina metódicamente « rotaciones ».
Dónde se usa
- Constituir parejas de trabajo, de revisión o de pair programming.
- Atribuir compañeros de piso o de habitación.
- Emparejar compañeros de entrenamiento o de torneo.
- Organizar mentoría entre iguales, sin jerarquía entre los dos papeles.
Límites y trampas
- Ninguna pareja quiere «fugarse» junta
- Basado en las preferencias de ambos lados
- Detecta honestamente los casos imposibles
- No siempre existe un emparejamiento estable
- Exige un número par
- Clasificar a todos puede llevar tiempo
Preguntas frecuentes
¿Qué pasa si no existe ninguna solución estable?
La herramienta lo dice claramente. Es información real sobre el grupo: las preferencias forman un ciclo irreductible. Le toca ajustar: emparejar por afinidad declarada o aceptar una inestabilidad asumida.
¿Qué diferencia hay con Gale-Shapley de dos grupos?
Gale-Shapley supone dos conjuntos distintos que se clasifican mutuamente (candidatos y formaciones) y garantiza siempre una solución. Aquí todo el mundo está en el mismo conjunto, no hay lado favorecido, pero desaparece la garantía de existencia.
¿Qué significa exactamente « estable »?
Que no existe ninguna pareja de personas que, sin estar emparejadas entre sí, se prefirieran mutuamente a su compañero actual. Tal pareja abandonaría el dispositivo: es precisamente lo que la estabilidad impide.