Imagina que tienes que emparejar a tres personas con otras tres, y que cada una tiene su lista de preferencias. ¿Existe una forma de hacerlo en la que nadie tenga motivos para romper el emparejamiento? Esa pregunta la resolvieron dos matemáticos en 1962, y su idea llega hoy a algunas apps de citas, como Hinge.
De qué va el algoritmo de Gale-Shapley
David Gale y Lloyd Shapley publicaron en enero de 1962, en la revista American Mathematical Monthly, el artículo «College Admissions and the Stability of Marriage» (algo así como «Admisiones universitarias y la estabilidad del matrimonio»). Lo plantearon con dos ejemplos del mismo problema: universidades que admiten alumnos y un grupo de hombres y mujeres que quieren casarse. Puedes leer el artículo original aquí.
La palabra clave es estable. Un emparejamiento es estable cuando no existe ninguna pareja de personas (una de cada lado) que se prefieran mutuamente antes que a sus parejas actuales. Si existiera esa pareja, tendría un motivo para romper el acuerdo. Gale y Shapley demostraron dos cosas: que siempre hay al menos un emparejamiento estable y que se puede encontrar con un procedimiento sencillo. Ese procedimiento es el algoritmo de Gale-Shapley, también llamado de «aceptación diferida».
En 2012, el Premio Nobel de Economía fue para Lloyd Shapley y Alvin Roth «por la teoría de asignaciones estables y la práctica del diseño de mercados». La Real Academia de Ciencias de Suecia explica que el algoritmo sirve de base para reformas que asignan médicos a hospitales, alumnos a colegios y órganos donados a pacientes. Lo dice la nota oficial del Nobel.
Cómo funciona, en pocas líneas
Hay un grupo que propone y otro que recibe. El procedimiento sigue estas reglas:
- Cada persona que propone se dirige a su opción favorita.
- Quien recibe se queda, de momento, con la mejor propuesta que tiene sobre la mesa y rechaza al resto. No da nada por cerrado todavía.
- Quien ha sido rechazado pasa a su siguiente opción.
- Se repite hasta que nadie tenga opciones pendientes. Entonces, cada persona que recibe se queda con quien tenía en espera.
Ejemplo paso a paso: tres y tres
Usamos nombres inventados. Noa, Kai y Lior proponen; Eme, Sasha y Rudi reciben. Así ordenan cada una su lista, de la mejor a la peor opción:
- Noa: Eme, Sasha, Rudi
- Kai: Eme, Rudi, Sasha
- Lior: Sasha, Eme, Rudi
- Eme: Kai, Noa, Lior
- Sasha: Noa, Lior, Kai
- Rudi: Lior, Kai, Noa
| Ronda | Quién propone a quién | Qué pasa |
|---|---|---|
| 1 | Noa → Eme · Kai → Eme · Lior → Sasha | Eme se queda con Kai. Sasha se queda con Lior. Noa, rechazada. |
| 2 | Noa → Sasha | Sasha prefiere a Noa y rechaza a Lior. |
| 3 | Lior → Eme | Eme ya tiene a Kai, a quien prefiere: rechaza a Lior. |
| 4 | Lior → Rudi | Rudi no tenía propuestas y se queda con Lior. Fin. |
Cada ronda, contada con palabras: en la ronda 1, Noa y Kai proponen a Eme y Lior propone a Sasha. Eme prefiere a Kai antes que a Noa: se queda con Kai y rechaza a Noa. Sasha se queda con Lior, de momento. En la ronda 2, Noa pasa a su siguiente opción, Sasha, que prefiere a Noa antes que a Lior. En la ronda 3, Lior propone a Eme, que ya tiene a Kai y lo rechaza. En la ronda 4, Lior propone a Rudi, que no tiene ninguna propuesta y se queda con él.
Resultado: Kai con Eme, Noa con Sasha y Lior con Rudi.
Comprobamos la estabilidad. Lior preferiría a Sasha o a Eme antes que a Rudi, pero ni Sasha ni Eme prefieren a Lior frente a la persona que ya tienen. Noa preferiría a Eme, pero Eme prefiere a Kai. Ninguna pareja tiene motivos para romper.
Por qué el lado que propone sale ganando
El algoritmo no trata a los dos lados por igual. Gale y Shapley demostraron que el resultado es el mejor posible para quien propone, entre todos los emparejamientos estables. El artículo lo dice en su sección 3: cuando proponen los hombres, el resultado es óptimo para ellos, y cuando proponen las mujeres, lo es para ellas. Como ambos métodos no siempre dan lo mismo, quien propone tiene ventaja. El Nobel también recoge esta idea: el diseño de un método puede beneficiar sistemáticamente a un lado del mercado frente al otro.
Un matiz importante: lo que se demuestra es que quien propone obtiene su mejor opción estable. No dice nada sobre lo que consigue quien recibe, que puede quedar peor de lo que habría sido con el procedimiento inverso.
Y las apps de citas, ¿qué tienen que ver?
En 2018, Hinge presentó su función «Most Compatible», que cada día sugiere a una persona que el sistema cree que te elegiría a ti también. Según la cobertura de la época, la función combina aprendizaje automático con el algoritmo de Gale-Shapley. Engadget lo contó el 12 de julio de 2018. Según esa misma información, la app se basa sobre todo en tu comportamiento: cuanto más reaccionas a fotos y partes de los perfiles, mejores son las sugerencias.
No hay datos públicos que permitan saber con exactitud cómo funciona hoy ese sistema dentro de la app ni si otras apps usan el mismo método. Lo que sí podemos decir es que la idea de fondo, con la lógica de preferencias ordenadas y rechazos que pasan a la siguiente opción, encaja con el modelo de Gale y Shapley.
Aprendizajes prácticos, sin promesas
- Tu lista importa. Un algoritmo solo trabaja con lo que le das. Si tu perfil y tus filtros no reflejan lo que de verdad buscas, el resultado también será confuso. Piensa qué es lo que de verdad quieres antes de ajustar filtros.
- Un «no» no es una medida de tu valor. En el ejemplo, Noa y Lior fueron rechazados y siguieron con su siguiente opción. Esa persona tenía otras prioridades, nada más.
- Dar el primer paso tiene peso. En el modelo, quien propone llega antes a su opción favorita. En una app, escribir o dar «me gusta» a quien te interesa es proponer. Si no responde, pasa a la siguiente opción en lugar de quedarte esperando.
- Estable no es lo mismo que feliz. El modelo garantiza que nadie quiera romper un emparejamiento por preferir a otra persona concreta. No dice nada de si la pareja se va a entender, de los horarios ni de la química.
Si quieres seguir leyendo sobre el tema, te pueden interesar cómo escribir el primer mensaje en las apps de citas, las diferencias entre Tinder, Hinge y Bumble, cómo elegir las fotos de perfil y cómo escribir la bio.
CelestIA es un copiloto de citas con IA para Tinder, Hinge y Bumble, con un precio de 14,99 €/mes y 7 días gratis. No estamos afiliados a ninguna de estas apps, y ninguna de ellas ha participado en este artículo. Nada de lo que hemos contado garantiza que vayas a encontrar pareja.
Fuentes
- Gale, D. y Shapley, L. S., «College Admissions and the Stability of Marriage», American Mathematical Monthly, vol. 69, n.º 1, enero de 1962 (copia del PDF).
- NobelPrize.org, «The Prize in Economic Sciences 2012», nota de prensa, 15 de octubre de 2012 (enlace).
- Fingas, J., «Hinge uses AI to suggest a 'most compatible' date every day», Engadget, 12 de julio de 2018 (enlace).
- Foto de portada: Bengt Nyman, «Lloyd Shapley 2 2012», Wikimedia Commons, CC BY 2.0.
¿Y si no te apetece escribir?
CelestIA escribe, sigue la charla y te deja la cita cerrada. 14,99 €/mes + IVA · 7 días gratis.
Pruébalo 7 días gratis