Asymptotic Equivalence of Immediate and Deferred Acceptance

Imagina que eres el alcalde de una ciudad bulliciosa donde cada niño necesita un lugar en una escuela, pero hay exactamente tantos asientos como estudiantes. El problema no es solo encontrar un asiento, sino encontrar el asiento adecuado. Cada familia tiene una lista de escuelas que ama, desde "Mi Escuela de Ensueño" hasta "La que aceptaría si no tuviera otra opción". La ciudad también tiene reglas; tal vez una escuela da prioridad a los niños que viven cerca o que ya tienen hermanos allí. La gran pregunta para los responsables es: ¿Cómo emparejamos a los niños con las escuelas para que todos sean lo más felices posible?

Durante décadas, los expertos han debatido dos formas principales de hacer esto. El primer método se llama Aceptación Diferida (AD). Piensa en esto como un baile lento y cuidadoso. Los estudiantes postulan a su primera opción. Las escuelas retienen a sus candidatos favoritos, pero no dicen "sí" para siempre; solo dicen "tal vez". Si aparece un estudiante mejor, la escuela puede intercambiarlo. Este proceso se repza hasta que todos están asentados. Es famoso por ser justo e imposible de engañar, pero puede ser un poco desordenado e ineficiente.

El segundo método es la Aceptación Inmediata (AI), conocida también como el mecanismo de "Boston". Esto es más como una carrera frenética. Los estudiantes se alinean y postulan a su primera opción. Las escuelas miran la fila, eligen a su favorito basándose en la prioridad y dicen: "¡Estás dentro!" de inmediato. Si eres rechazado, corres instantáneamente hacia tu segunda opción. El problema es que, si postulas a tu primera opción tarde, podrías perder tu lugar frente a alguien con mayor prioridad que postuló antes, incluso si tú deseabas esa escuela más que nadie. Por esto, la AI suele ser criticada por ser injusta o fácil de manipular. Sin embargo, tiene un gran superpoder: si todos dicen la verdad sobre lo que quieren, la IA garantiza un resultado en el que nadie puede ser más feliz sin hacer que alguien más sea menos feliz. Esto se llama "Eficiencia de Pareto".

Así que, aquí está la pregunta del millón de dólares: ¿Realmente marca una gran diferencia el superpoder de la IA en la vida real? ¿Logra la IA meter a los niños en escuelas que les gustan mucho mejor que el método de la DA? ¿O la diferencia es solo una mota diminuta e invisible? Este es el rompecabezas que Josué Ortega aborda en su artículo.

---

La Gran Carrera Escolar: Un Cuento de Dos Mecanismos

Josué Ortega, un investigador de la Universidad Queen's de Belfast, decidió resolver este debate realizando un experimento mental masivo. No observó ciudades reales con su historia y política complicadas. En su lugar, imaginó un "mercado aleatorio" —un mundo donde la lista de escuelas favoritas de cada estudiante se extrae de forma completamente aleatoria, como sacar nombres de un sombrero. En este mundo, hay $n$ estudiantes y $n$ escuelas.

Ortega quería medir el "rango promedio". Imagina que cada estudiante recibe una puntuación basada en qué tan alto en su lista se encuentra la escuela asignada. Si obtienes tu opción #1, tu rango es 1. Si obtienes tu opción #100, tu rango es 100. El objetivo es mantener este número lo más bajo posible.

Durante mucho tiempo, supimos la respuesta para la danza lenta y cuidadosa (DA). Allá por la década de 1970, los matemáticos descubrieron que en un mercado aleatorio, el estudiante promedio termina en una escuela con un rango de aproximadamente $\log n$ (logaritmo de $n$). Si tienes 1,000 estudiantes, el rango promedio es aproximadamente 7. Si tienes 100,000 estudiantes, es aproximadamente 11. Crece, pero muy lentamente.

Pero, ¿qué pasa con la carrera frenética (IA)? Debido a que la IA funciona de manera diferente —donde el orden de postulación importa y los estudiantes pueden ser rechazados simplemente por ser "tardíos"— los matemáticos pensaron que podría ser mucho más compleja. Algunos científicos de la computación habían intentado resolverlo, pero solo podían calcular las probabilidades de obtener un rango específico, no el rango promedio para todos. Supusieron que también sería logarítmico, pero nadie podía probarlo.

El Secreto del "Coleccionista de Cupones"

El gran avance de Ortega fue darse cuenta de que ambos mecanismos, a pesar de parecer totalmente diferentes, están jugando secretamente el mismo juego. Utilizó un acertijo clásico llamado el Problema del Coleccionista de Cupones para explicarlo.

Imagina que estás tratando de coleccionar un set completo de $n$ tarjetas coleccionables diferentes. Cada vez que compras una caja de cereal, recibes una tarjeta aleatoria. ¿Cuántas cajas necesitas comprar para tener cada una de las tarjetas al menos una vez?
La respuesta es aproximadamente $n \times \log n$. Pasas mucho tiempo comprando cajas solo para encontrar las últimas pocas cartas raras que te faltan.

Ortega demostró que la Aceptación Diferida es exactamente como esto. Los estudiantes siguen postulando a escuelas hasta que cada escuela ha recibido al menos una postulación. El número total de postulaciones realizadas por todos es aproximadamente el mismo que el número de cajas de cereal que necesitarías comprar para coleccionar todos los cupones. Dado que el estudiante promedio realiza alrededor de $\log n$ postulaciones, su rango de escuela final también es de aproximadamente $\log n$.

Luego, Ortega dirigió su mirada a la Aceptación Inmediata. Al principio, parecía diferente porque los estudiantes no pueden seguir postulando inmediatamente; tienen que esperar a que termine una "ronda" antes de intentar de nuevo. Pero Ortega se dio cuenta de que, si miras el proceso de una manera específica, también es un coleccionista de cupones.

Imaginó una versión ligeramente "amnésica" del juego. Supongamos que un estudiante sigue eligiendo escuelas al azar, incluso si ya ha intentado esa escuela. Si elige una escuela que ya ha probado, simplemente la ignora (ese es un intento "desperdiciado"). Ortega demostió que incluso con estos intentos desperdiciados, el número de postulaciones reales necesarias para llenar cada escuela es todavía aproximadamente el mismo que el problema del coleccionista de cupones.

La Gran Revelación

Aquí está el remate: La diferencia entre los dos métodos es sorprendentemente pequeña.

Ortega demostró matemáticamente que a medida que el mercado se vuelve enorme (cuando $n$ es muy grande), el rango promedio para los estudiantes en el sistema de Aceptación Inmediata (IA) es también aproximadamente $\log n$.

Esto significa que, aunque la IA es "eficiente de Pareto" (lo que significa que es teóricamente perfecta si todos dicen la verdad), no ofrece a los estudiantes una ventaja masiva en términos de conseguir sus primeras opciones en comparación con el método de la DA. La mejora de "primer orden" —la ganancia grande y notable— simplemente no existe.

El artículo de Ortega descarta explícitamente la idea de que la IA sea una solución mágica que mejore drásticamente los resultados de los estudiantes en grandes mercados aleatorios. Aunque la IA podría ser ligeramente mejor en escenarios diminutos y específicos o con reglas de prioridad específicas, el artículo muestra que, en el caso general, los dos mecanismos son asintóticamente equivalentes. Ambos sitúan a los estudiantes en escuelas con un rango aproximadamente logarítmico en relación al tamaño del mercado.

Por qué esto importa

Este hallazgo es un poco desalentador para los fans del sistema de "Aceptación Inmediata", pero es un alivio para las matemáticas. Nos dice que la "eficiencia de Pareto" de la IA es un poco un espejismo cuando se trata de la felicidad promedio. El mecanismo que a menudo se critica por ser injusto y manipulable no entrega realmente un resultado promedio significativamente mejor que aquel que es justo y difícil de engañar.

El trabajo de Ortega extiende este hallazgo a otras variaciones también. Ya sea que las escuelas tengan múltiples asientos (emparejamiento de muchos a uno) o que se permita a los estudiantes saltarse escuelas llenas (una variación llamada "IA con saltos"), el resultado se mantiene: el rango promedio se mantiene alrededor de $\log n$.

Así que, la próxima vez que escuches a alguien argumentar que debemos usar el "mecanismo de Boston" porque es más eficiente, puedes sonreír y decir: "Bueno, tal vez sea eficiente, pero en realidad no logra que los niños entren en mejores escuelas en promedio que la otra forma". En la gran carrera de la elección escolar, ambos corredores están cruzando la línea de meta casi al mismo tiempo.