Imagina que eres el Chief Economist de una nueva aplicación de citas en línea y te piden que desarrolles el algoritmo para hacer match entre las parejas.
A diferencia de Tinder, la aplicación sólo te permitirá hablar cuando el algoritmo decida que son la mejor elección de pareja. Tu tarea es definir las reglas que definen cuál es esa mejor elección.
Aunque no lo parece a simple vista, el problema es uno clásico de la economía: asignación de un recurso escaso (el tiempo para dedicar a hablar con una potencial pareja) de una manera eficiente: la idea es que cada quien hable sólo con aquellos que tienen altas probabilidades de ser su pareja.
Y no es un problema sencillo. Afortunadamente nos podemos subir a los hombros de gigantes para resolver este problema.
Un algoritmo antiguo para una tecnología nueva
En 1962, el matemático experto en teoría de juegos Loyd Shapley junto a David Gale hicieron una propuesta para solucionar este problema.
Imagina que nuestra aplicación nos permite hacer propuestas para hablar a otros usuarios y que la aplicación nos permite aceptar o rechazar las propuestas.
Por simplicidad, imaginemos que sólo hay tres proponentes y tres aceptantes de propuestas. Supongamos que el algoritmo detecta nuestras preferencias y las ordena automáticamente como parte del proceso.
Cada uno de los proponentes tiene un orden de preferencia para cada uno de los aceptantes. Por ejemplo, para A podría ser preferible hablar con X, luego estaría Z y al final Y. Para X, por otro lado le parecería mejor hablar con C, luego B y al final con A.
La siguiente tabla resume todas las preferencias. Las preferencias de A, B y C están del lado izquierdo de la coma y las de C, Y y Z están a la derecha.
Un match estable
También supongamos que nuestro objetivo es que los matches sean estables. Un match es estable cuando nadie tiene incentivos para irse con alguien más.
Digamos que C y X hicieron match. Para X no hay nadie con quien preferiría estar, pero C podría estar con Y si estuviera disponible. Si Y estuviera con B, entonces irse con A no le beneficiaría: la pareja es estable (matemáticamente hablando). En cambio si Y estuviera con A, podría cambiarse a hablar con C y C dejaría su match con X para irse con Y 💔.
Nota que estable no siempre significa que todo mundo esté con quien más le guste: sólo es necesario que nadie tenga una opción para irse que acepte su propuesta.
Es por simplicidad que aceptamos este objetivo, y probablemente tras resolver éste podamos avanzar a modelos un poco más complejos. Por lo tanto nuestra pregunta sería: ¿Es posible un arreglo de pareja en el que todo mundo tenga pareja que a la vez sea estable?
El algoritmo Gale-Shapley
El artículo se volvió famoso por ofrecer una solución a este problema. Se trata de una serie de pasos muy sencillos que garantizan que todos se quede con un match y ese match sea estable.
Este algoritmo sólo funciona si hay el mismo número de proponentes que de aceptantes.
- Los proponentes ofrecen hacer match al primer lugar de sus opciones. Dos proponentes pueden ofrecer match a la misma persona. En nuestro ejemplo de arriba, A ofrece hacer match con X, B con X también y C ofrece match a Y.
- Si alguien tiene más de una propuesta, rechazará a quien tenga en menor orden de preferencia. X tiene las propuestas de A y B, de las cuales prefiere a B. Por lo tanto debe rechazar a A.
- Los proponentes rechazados deben mandar propuesta a la siguiente persona en su lista de preferencias. Cómo A fue rechazado por X, ahora hará su propuesta a Y.
- Se repiten los pasos 2 y 3 hasta que todos tengan pareja. Las parejas resultantes serán estables. Ahora Y tiene dos propuestas. Cómo Y prefiere a C, A volverá a ser rechazado y pasará su propuesta a Z. Ahora todos tienen pareja y nadie tiene ninguna forma de cambiarse.
Listo. Tenemos tres parejas estables. Este ejemplo se puede extender de manera natural a un número cualquiera de parejas, siempre y cuando sea el mismo número de proponentes que de aceptantes. La única limitante en este sentido es que tengamos el poder computacional para hacer el número de operaciones que esto requiere.
¿Se puede manipular el algoritmo?
El algoritmo Gale-Shapley es una solución matemática que garantiza que todos tengan pareja y que ese match sea estable. Sin embargo, no es infalible y puede ser manipulado. Por ejemplo, si un proponente miente sobre sus preferencias para hacer match con alguien, podría generar inestabilidad en el match.
Lo peor es que el resultado de estas manipulaciones es muy parecido al que genera el que tiene las preferencias reales, por lo que se vuelve muy difícil de detectar.
Otras aplicaciones del algoritmo
El algoritmo de Gale-Shapley tiene múltiples aplicaciones en la economía y en la vida cotidiana. Por ejemplo, se utiliza en la asignación de plazas de residencia médica y en la asignación de colegios a estudiantes. También se puede utilizar para resolver problemas de asignación de recursos en empresas o en la asignación de tareas en equipos de trabajo, siempre y cuando se cumpla la condición de que haya el mismo número de ofertantes que de demandantes.
