Pruébalo 7 días gratis

← Blog de citas

Gale-Shapley: el algoritmo de 1962 detrás de las citas que encajan

Qué es, cómo funciona con un ejemplo de tres y tres, qué tiene que ver con Hinge y qué te deja para tus citas.

Lloyd Shapley, economista y matemático, en una fotografía de 2012
Lloyd Shapley, coautor del algoritmo, en 2012. Foto: Bengt Nyman, CC BY 2.0, vía Wikimedia Commons.

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:

  1. Cada persona que propone se dirige a su opción favorita.
  2. 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.
  3. Quien ha sido rechazado pasa a su siguiente opción.
  4. 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:

RondaQuién propone a quiénQué pasa
1Noa → Eme · Kai → Eme · Lior → SashaEme se queda con Kai. Sasha se queda con Lior. Noa, rechazada.
2Noa → SashaSasha prefiere a Noa y rechaza a Lior.
3Lior → EmeEme ya tiene a Kai, a quien prefiere: rechaza a Lior.
4Lior → RudiRudi 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.

ProponenRecibenNoaKaiLiorEmeSashaRudi
El emparejamiento estable que sale al final.

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

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

¿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