El 29 de septiembre de 2026, un hilo en X sobre la app de citas del gobierno de Singapur se viralizó con casi 500.000 reproducciones: FirstDate, el piloto para funcionarios públicos de 21 a 35 años, corre sobre el algoritmo Gale-Shapley, un procedimiento matemático de 1962 que también reparte médicos residentes entre hospitales y organiza cadenas de intercambio de riñones entre desconocidos.
La aplicación es apenas la anécdota: lo que importa es el mecanismo matemático detrás, premiado con el Nobel de Economía en 2012 y todavía activo en decisiones con mucho más peso que una cita.
TL;DR
- Gale-Shapley empareja dos grupos según preferencias y asegura que ningún par prefiera abandonar su asignación.- El NRMP (National Resident Matching Program) usa una variante del algoritmo para asignar médicos a hospitales en Estados Unidos.- Las cadenas de riñones usan la misma lógica de matching estable entre donantes y receptores.- Quien propone en cada ronda obtiene su mejor resultado posible; quien recibe, el peor entre los estables.- Como máximo n² rondas de propuestas y rechazos bastan para terminar sin ciclos infinitos.
¿Qué es el algoritmo Gale-Shapley?
El algoritmo Gale-Shapley es un procedimiento de teoría de juegos que empareja a los miembros de dos grupos (por ejemplo, estudiantes y universidades) según listas de preferencias propias, garantizando que el resultado sea estable: ningún par de participantes preferiría abandonar su asignación actual para emparejarse entre sí en su lugar.
En inglés también se lo conoce como deferred acceptance (algoritmo de aceptación diferida), porque ningún receptor rechaza en forma definitiva hasta el final del proceso: retiene la mejor oferta que recibió hasta ese momento y la descarta solo si llega una mejor. David Gale y Lloyd Shapley lo plantearon para resolver la admisión universitaria y el problema del matrimonio estable entre dos grupos del mismo tamaño. Pero la estructura matemática no depende del contexto, y por eso hoy sirve para empleos, trasplantes y hasta citas estatales.
Por qué importa
David Gale y Lloyd Shapley publicaron el método en 1962 en College Admissions and the Stability of Marriage, un paper de apenas ocho páginas. Demostraba algo que hasta entonces nadie había probado formalmente: que siempre existe al menos un matching estable para dos grupos con preferencias completas, y que un procedimiento simple de propuestas y rechazos lo encuentra en un número finito de pasos.
Cincuenta años después, el Premio Nobel de Ciencias Económicas 2012 reconoció esa teoría, compartida entre Lloyd Shapley y Alvin Roth. Shapley había construido la matemática pura; Roth pasó las siguientes tres décadas llevándola a instituciones reales, desde la asignación de médicos hasta los intercambios de riñones. El comité del Nobel describió el trabajo como un ejemplo de diseño de mercados: usar la teoría para construirlos, no solo para describirlos.
📌 Nota: al recibir el Nobel, Lloyd Shapley bromeó diciendo que nunca había tomado un curso de economía: se consideraba matemático puro, y el algoritmo que lleva su nombre nació como un ejercicio de teoría de juegos, no de política pública.
Cómo funciona el algoritmo Gale-Shapley
El procedimiento corre en rondas. En cada ronda, todo proponente que sigue libre le ofrece al receptor mejor ubicado en su lista que todavía no lo haya rechazado. Cada receptor mira las ofertas que recibió hasta ese momento, incluida la que ya tenía retenida, y se queda con la que más le convenga según su propia lista, rechazando a todas las demás. Un proponente rechazado tacha a ese receptor de su lista y, en la próxima ronda, prueba con el siguiente.
La clave está en que el rechazo no es definitivo hasta el final. Un receptor puede soltar a quien tenía retenido si llega una oferta mejor, pero nunca empeora su situación ronda a ronda. El proceso termina cuando ya nadie hace nuevas ofertas, es decir, cuando cada proponente fue aceptado o agotó su lista completa. El siguiente diagrama resume ese ciclo:
flowchart TD
A["Cada proponente arma su lista de preferencias"] --> B["Proponente libre ofrece al primero de su lista no descartado"]
B --> C{"Receptor ya tiene una oferta retenida?"}
C -->|"No"| D["Receptor retiene la oferta"]
C -->|"Si, pero prefiere la nueva"| E["Receptor cambia de oferta retenida"]
C -->|"Si, y prefiere la que tiene"| F["Receptor rechaza la oferta nueva"]
D --> G{"Quedan proponentes libres?"}
E --> G
F --> G
G -->|"Si"| B
G -->|"No"| H["Las ofertas retenidas son el matching final"]
Para verlo con un caso concreto: un médico puede proponer primero al hospital que más quiere, ser rechazado si ese hospital ya retiene a alguien mejor rankeado, y pasar al siguiente de su lista en la ronda siguiente. El diagrama de secuencia muestra esa negociación entre un proponente y dos receptores:
sequenceDiagram
participant Dr as Dr. Ruiz
participant A as Hospital A
participant B as Hospital B
Dr->>A: propone en la ronda 1
A-->>Dr: retiene la oferta
Note over Dr,A: Hospital A no tiene otra oferta mejor
Dr->>B: en otra simulacion, propone a Hospital B primero
B-->>Dr: rechaza, ya retiene una oferta mejor
Dr->>A: pasa al siguiente de su lista
Ejemplos prácticos en código
El algoritmo se puede programar en menos de veinte líneas. La siguiente implementación en Python recibe las listas de preferencias de ambos lados y devuelve el matching estable que resulta cuando el primer grupo propone:
def gale_shapley(proposer_prefs, receiver_prefs):
free_proposers = list(proposer_prefs.keys())
next_proposal = {p: 0 for p in proposer_prefs}
current_match = {}
while free_proposers:
p = free_proposers.pop(0)
prefs = proposer_prefs[p]
r = prefs[next_proposal[p]]
next_proposal[p] += 1
if r not in current_match:
current_match[r] = p
else:
rival = current_match[r]
if receiver_prefs[r].index(p) El paper original de Gale y Shapley se publicó en 1962 en apenas ocho páginas.
## Comparativa con alternativas
MecanismoQué resuelveQué garantizaEjemplo realGale-Shapley (aceptación diferida)Matching uno a uno entre dos grupos con preferencias ordenadasEstabilidad, y optimalidad para quien proponeNRMP, FirstDateTop Trading CyclesIntercambio de bienes indivisibles entre pares incompatiblesEficiencia de Pareto; no siempre estabilidad bilateralCadenas de intercambio de riñonesMecanismo de Boston (aceptación inmediata)Asignación de cupos escolaresRápido de correr; manipulable si una familia declara mal sus preferenciasSistemas de elección escolar previos a 2003Asignación aleatoria (random serial dictatorship)Repartir bienes sin preferencias reveladas por ambos ladosSimplicidad; no optimiza nada más allá del orden del sorteoSorteos de vivienda universitariaEl National Kidney Registry coordina cadenas que a veces arrancan con un donante altruista.
## Errores comunes y buenas prácticas
El error más común es asumir que un matching estable reparte las ventajas por igual. No es así: el algoritmo no reparte ventajas al azar, sino sistemáticamente a favor de quien propone, que siempre termina con su mejor resultado posible entre todos los matchings estables disponibles. Quien recibe las ofertas, en cambio, se queda con el peor resultado estable que le podía tocar. Por eso en el matching de residencias importa mucho si proponen los hospitales o los aplicantes: el NRMP cambió el lado que propone en los años 90 precisamente por esta asimetría.
Otro error es asumir que conviene mentir sobre las preferencias para manipular el sistema. Para el lado que propone, decir la verdad es la estrategia dominante: no existe ninguna lista falsa que mejore el resultado. El lado que recibe las ofertas, en cambio, a veces sí puede beneficiarse ocultando preferencias, aunque en la práctica detectar cuándo conviene hacerlo es difícil y casi ningún sistema real permite declarar información parcial.
El algoritmo tal como lo plantearon Gale y Shapley asume listas completas y sin empates. En la vida real eso casi nunca pasa: un hospital no conoce a todos los aplicantes, y dos candidatos pueden parecerle exactamente iguales. Las implementaciones reales, el NRMP incluido, usan variantes con listas parciales y reglas de desempate, y ahí la garantía de optimalidad para el proponente ya no es tan limpia como en el modelo original.
> **⚠️ Ojo:** un matching estable no es lo mismo que un matching socialmente óptimo. Puede existir otra asignación que mejore a todos los participantes al mismo tiempo sin ser estable; el algoritmo nunca la va a encontrar porque no es lo que busca.
## Profundizando
A nivel computacional, el algoritmo Gale-Shapley corre en tiempo O(n²) en el peor caso, donde n es el tamaño de cada grupo. Cada proponente puede hacer como máximo n propuestas antes de agotar su lista, y hay n proponentes en total, así que el número de propuestas está acotado por n². Es una cota ajustada: existen instancias donde efectivamente hacen falta cerca de n² propuestas para llegar a un matching estable.
El conjunto de todos los matchings estables para un mismo problema forma una estructura matemática llamada retículo. Tiene un elemento óptimo para los proponentes, que es el que encuentra el algoritmo, y un elemento óptimo para los receptores, que es el que resulta si se invierten los roles. En problemas grandes puede haber muchísimos matchings estables intermedios entre esos dos extremos.
Un resultado menos conocido pero muy usado en la práctica es el Teorema del Hospital Rural. En cualquier matching estable, el conjunto de receptores que queda con cupos vacíos es exactamente el mismo, y cada receptor con cupos sin llenar recibe el mismo conjunto de proponentes sin importar qué matching estable se elija. Esto explica por qué ciertos hospitales en zonas poco atractivas quedan sistemáticamente con vacantes, sin importar qué variante del algoritmo use el NRMP.
La extensión más difícil de resolver en la práctica es la de parejas que aplican juntas y piden ciudades compatibles entre sí. Ese problema, a diferencia del caso individual, puede no tener ningún matching estable, y encontrar uno cuando existe es computacionalmente difícil en el peor caso. El NRMP lo resuelve igual con heurísticas que funcionan bien en la práctica, aunque no tengan garantía teórica para el peor caso posible.
📖 Resumen en Telegram: [Ver resumen](https://telegra.ph/Gale-Shapley-cómo-funciona-el-matching-estable-del-Nobel-2012-10-01)
Tu próximo paso: tomá el código de este artículo, armá un caso con cinco proponentes y cinco receptores con tus propias listas de preferencias, y confirmá con la función `is_stable` que el resultado no tiene pares bloqueantes.
## Preguntas frecuentes
### ¿Quiénes inventaron Gale-Shapley?
David Gale y Lloyd Shapley, que lo publicaron en 1962 en un paper sobre admisión universitaria y matrimonio estable, sin pensar todavía en sus aplicaciones económicas reales.
### ¿Por qué Gale-Shapley ganó el Nobel de Economía 2012?
El Nobel reconoció la teoría del matching y el diseño de mercados, compartida entre Lloyd Shapley, que construyó la matemática, y Alvin Roth, que la aplicó a residencias médicas y trasplantes de riñón.
### ¿El matching estable es siempre único?
No. Para el mismo conjunto de preferencias puede haber varios matchings estables; el algoritmo encuentra específicamente el que es óptimo para el lado que propone.
### ¿Se puede manipular el algoritmo de aceptación diferida mintiendo?
El lado que propone no gana nada falseando sus preferencias, decir la verdad es su mejor estrategia. El lado que recibe ofertas, en cambio, a veces sí puede beneficiarse ocultando información.
### ¿Qué garantiza el Teorema del Hospital Rural en el matching estable?
Que el conjunto de receptores con cupos vacíos, y el conjunto de proponentes asignado a cada uno de ellos, es el mismo en cualquier matching estable posible para ese problema.
### ¿La app FirstDate de Singapur usa Gale-Shapley real?
Según el hilo que originó esta nota, sí: la app gubernamental para funcionarios de 21 a 35 años corre una versión del algoritmo, con verificación de identidad por Singpass y una ventana de 72 horas por match.
## Referencias
- [Hilo original en X](https://twitter.com/tuakdotsol/status/2105105417760391258): la descripción de cómo FirstDate usa Gale-Shapley.- [Wikipedia: Gale-Shapley algorithm](https://en.wikipedia.org/wiki/Gale%E2%80%93Shapley_algorithm): historia y formalización matemática del método.- [Nobel Prize 2012 press release](https://www.nobelprize.org/prizes/economic-sciences/2012/press-release/): anuncio oficial del premio a Shapley y Roth.- [National Resident Matching Program](https://www.nrmp.org/): la institución que aplica el algoritmo a residencias médicas en Estados Unidos.- [National Kidney Registry](https://www.kidneyregistry.org/): coordinación de cadenas de intercambio de riñones basadas en matching.
📱 **¿Te gusta este contenido?** Únete a nuestro canal de Telegram [@programacion](https://t.me/programacion) donde publicamos a diario lo más relevante de tecnología, IA y desarrollo. Resúmenes rápidos, contenido fresco todos los días.
Top comments (0)