Cómo funciona, en detalle
Cada cual parte con una dotación: su misión actual, su despacho, su franja. El número de personas y de bienes debe por tanto ser igual.
Cada cual señala el bien que prefiere. Se siguen las flechas: acaban siempre formando al menos un ciclo, eventualmente un bucle sobre sí mismo cuando alguien ya tiene lo que prefiere.
Los ciclos se ejecutan: cada cual recibe lo que señalaba. Las personas servidas salen con su bien y se vuelve a empezar con las demás, hasta agotarlas.
Tres propiedades demostradas: el resultado es Pareto-eficiente, individualmente racional (nadie sale con algo peor que su dotación) y el mecanismo es no manipulable.
Un ejemplo con cifras
Tres personas, cada una con una franja, cada una queriendo otra.
| Persona | Franja actual | Franja deseada | Obtiene |
|---|---|---|---|
| Chloé | Lunes | Martes | Martes |
| Ali | Martes | Lunes | Lunes |
| Bruno | Miércoles | Miércoles | Miércoles |
- Chloé señala la franja de Ali, Ali señala la de Chloé: es un ciclo de longitud 2.
- El ciclo se ejecuta: ambos intercambian y salen satisfechos.
- Bruno señala su propia franja: bucle sobre sí mismo, la conserva.
Dos intercambios, ningún perdedor. Es la garantía central del método: nunca se puede salir peor de lo que se entró.
De dónde viene
Lloyd Shapley y Herbert Scarf publican en 1974, en el Journal of Mathematical Economics, el artículo fundador sobre el « housing market ». Atribuyen el algoritmo de los ciclos de intercambio más altos a David Gale y demuestran que produce siempre una asignación en el núcleo del mercado.
Atila Abdulkadiroğlu y Tayfun Sönmez lo extienden en 1999 a situaciones mixtas, donde algunos ocupantes ya están instalados y otros llegan: el caso concreto de las residencias universitarias estadounidenses.
Su aplicación más espectacular es médica: los programas de intercambio de riñones entre parejas donante-receptor incompatibles, formalizados por Roth, Sönmez y Ünver a principios de los años 2000, reposan en esta mecánica de ciclos. Alvin Roth y Lloyd Shapley reciben el Nobel de Economía 2012 por el conjunto de estos trabajos.
Dónde se usa
- Intercambiar turnos de guardia, disponibilidades o días de vacaciones.
- Reasignar despachos, material o plazas de aparcamiento ya ocupados.
- Permutar misiones o carteras de clientes dentro de un equipo.
- Intercambios de riñones entre parejas incompatibles: la aplicación que valió un Nobel.
Límites y trampas
- Nadie acaba peor que al principio
- Clasificar con sinceridad siempre es lo mejor
- Se realizan todos los intercambios donde todos ganan
- Cada uno necesita una posesión inicial
- Exactamente tantas cosas como personas
- El resultado depende mucho de las dotaciones
Preguntas frecuentes
¿Puedo perder respecto a mi situación actual?
No, nunca, y está demostrado: la racionalidad individual es una propiedad probada del algoritmo. Si ningún intercambio le conviene, conserva su dotación: es el bucle sobre sí mismo.
¿Me interesa declarar un orden de preferencias falso?
No. El mecanismo es no manipulable: mentir no puede mejorar su resultado y puede hacerle perder un ciclo que le convenía.
¿Y si nadie quiere intercambiar?
Todo el mundo señala su propio bien, todos los ciclos son bucles y nada se mueve. El resultado es válido: dice que el reparto actual ya es óptimo.