Algoritmo Gale-Shapley: cómo funciona el matching estable

⏱️ Lectura: 16 min

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.

📑 En este artículo

1. TL;DR
2. ¿Qué es el algoritmo Gale-Shapley?
3. Por qué importa
4. Cómo funciona el algoritmo Gale-Shapley
5. Ejemplos prácticos en código
   1. Cómo confirmar que un matching es estable
6. Cómo empezar
7. Casos de uso reales
8. Comparativa con alternativas
9. Errores comunes y buenas prácticas
10. Profundizando
11. Preguntas frecuentes
    1. ¿Quiénes inventaron Gale-Shapley?
    2. ¿Por qué Gale-Shapley ganó el Nobel de Economía 2012?
    3. ¿El matching estable es siempre único?
    4. ¿Se puede manipular el algoritmo de aceptación diferida mintiendo?
    5. ¿Qué garantiza el Teorema del Hospital Rural en el matching estable?
    6. ¿La app FirstDate de Singapur usa Gale-Shapley real?
12. Referencias
    1. 📚 Artículos relacionados

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) < receiver_prefs[r].index(rival):
                current_match[r] = p
                free_proposers.append(rival)
            else:
                free_proposers.append(p)

    return current_match

proposer_prefs = {"Ana": ["H1", "H2"], "Beto": ["H1", "H2"]}
receiver_prefs = {"H1": ["Beto", "Ana"], "H2": ["Ana", "Beto"]}

print(gale_shapley(proposer_prefs, receiver_prefs))

Con solo dos proponentes y dos receptores, Beto termina en H1 y Ana en H2, aunque ambos preferían H1 primero. La salida literal es:

{'H1': 'Beto', 'H2': 'Ana'}

El mismo código sirve para un caso con tres proponentes y tres receptores, el tamaño mínimo donde ya aparecen rechazos y reasignaciones en cadena:

proposer_prefs = {
    "Dr. Ruiz": ["Hosp A", "Hosp B", "Hosp C"],
    "Dr. Soto": ["Hosp B", "Hosp A", "Hosp C"],
    "Dr. Vega": ["Hosp A", "Hosp C", "Hosp B"],
}
receiver_prefs = {
    "Hosp A": ["Dr. Vega", "Dr. Ruiz", "Dr. Soto"],
    "Hosp B": ["Dr. Ruiz", "Dr. Soto", "Dr. Vega"],
    "Hosp C": ["Dr. Soto", "Dr. Vega", "Dr. Ruiz"],
}

matching = gale_shapley(proposer_prefs, receiver_prefs)
print(matching)

Acá el Dr. Ruiz propone primero a Hosp A y es aceptado, pero después lo desplaza el Dr. Vega, a quien Hosp A prefiere más. Ruiz se reubica en Hosp B desplazando a Soto, que termina su recorrido en Hosp C. La salida literal es:

{'Hosp A': 'Dr. Vega', 'Hosp B': 'Dr. Ruiz', 'Hosp C': 'Dr. Soto'}

Cómo confirmar que un matching es estable

No hace falta confiar a ciegas en el algoritmo: se puede verificar el resultado buscando pares bloqueantes, dos participantes que preferirían estar juntos antes que con su pareja asignada. Si la función no encuentra ninguno, el matching es estable por definición.

def is_stable(matching, proposer_prefs, receiver_prefs):
    match_of_proposer = {p: r for r, p in matching.items()}
    for p, prefs in proposer_prefs.items():
        r_assigned = match_of_proposer[p]
        rank_assigned = prefs.index(r_assigned)
        for r in prefs[:rank_assigned]:
            rival = matching[r]
            if receiver_prefs[r].index(p) < receiver_prefs[r].index(rival):
                return False
    return True

print(is_stable(matching, proposer_prefs, receiver_prefs))

La salida literal es True: no existe ningún médico que prefiera un hospital distinto al suyo cuyo hospital, a su vez, lo prefiera a él por sobre quien ya tiene asignado.

Cómo empezar

No hace falta instalar nada más que Python 3 (cualquier versión 3.8 o superior sirve, sin librerías externas).

1. Verificar la versión instalada: python3 --version (en Windows, python --version desde PowerShell).
2. Guardar el primer bloque de código en un archivo gale_shapley.py.
3. Agregar las funciones is_stable y los diccionarios de preferencias al mismo archivo.
4. Ejecutarlo: python3 gale_shapley.py (Windows: python gale_shapley.py).
5. Confirmar que la salida coincide con los diccionarios mostrados arriba y que is_stable devuelve True.

Casos de uso reales

El caso más citado es el National Resident Matching Program (NRMP) de Estados Unidos, que asigna cada año a los médicos recién graduados a sus hospitales de residencia. El sistema original, de los años 50, ya resolvía el problema con una lógica equivalente a la de Gale-Shapley sin que nadie lo hubiera formalizado todavía. Alvin Roth lo demostró matemáticamente décadas después y ayudó a rediseñarlo en los años 90 para que también pudiera emparejar parejas de médicos que buscaban residencia en la misma ciudad, un problema bastante más difícil que el caso individual.

La aplicación más dramática es el intercambio de riñones. Cuando un donante y un receptor son incompatibles entre sí, pero compatibles con otro par en la misma situación, un matching estable encuentra cadenas que permiten varios trasplantes simultáneos sin que nadie ceda un órgano sin recibir uno a cambio. El National Kidney Registry coordina cadenas de este tipo, muchas veces arrancando con un donante altruista que no tiene un receptor específico en mente.

Nueva York y Boston rediseñaron la asignación de cupos en sus escuelas públicas con variantes del mismo mecanismo a comienzos de los años 2000. Lo hicieron después de que economistas demostraran que el sistema anterior premiaba a las familias que sabían jugar con las preferencias declaradas, no a las que más necesitaban un cupo escolar.

Y volviendo al gancho inicial: en FirstDate, cada participante arma su lista de preferencias y descartes, el sistema corre una versión del algoritmo, y el resultado se revela en ciclos de un match a la vez, con una ventana de 72 horas para decidir y verificación de identidad vía Singpass. Por ahora el piloto está limitado a funcionarios públicos de 21 a 35 años. La diferencia con una app comercial no es cosmética: Tinder necesita que sigas deslizando, mientras que un matching estable bien calculado apunta a sacarte de la plataforma cuanto antes.

Comparativa con alternativas

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

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: la descripción de cómo FirstDate usa Gale-Shapley.
• Wikipedia: Gale-Shapley algorithm: historia y formalización matemática del método.
• Nobel Prize 2012 press release: anuncio oficial del premio a Shapley y Roth.
• National Resident Matching Program: la institución que aplica el algoritmo a residencias médicas en Estados Unidos.
• National Kidney Registry: coordinación de cadenas de intercambio de riñones basadas en matching.

📱 ¿Te gusta este contenido? Únete a nuestro canal de Telegram @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.

Imagen destacada: Foto de GuerrillaBuzz en Unsplash