Asignación de cursos

La asignación de plazas en los cursos universitarios consiste en distribuirlas entre los estudiantes. Muchas universidades imponen un límite máximo de plazas para cada curso, con el fin de garantizar que los profesores puedan prestar la atención necesaria a cada alumno. Dado que la demanda de algunos cursos supera este límite, surge la pregunta de qué estudiantes deberían poder matricularse en cada uno.

Muchas instituciones permiten que los estudiantes se matriculen por orden de llegada . Sin embargo, esto puede generar resultados injustos: un estudiante que se encuentre cerca de su ordenador cuando comience la matrícula puede matricularse en todos los cursos más solicitados, mientras que un estudiante que llegue tarde podría descubrir que todos los cursos deseados ya están completos y solo podrá matricularse en los menos solicitados. Para mitigar esta injusticia, muchas instituciones utilizan mecanismos de asignación más sofisticados. ^{[ 1 ]}

En un mecanismo de selección por turnos (también llamado round-robin ), los estudiantes eligen cursos por turnos del conjunto de cursos con plazas disponibles. El orden de elección es aleatorio en la primera ronda y se invierte en las rondas siguientes. En la práctica, los estudiantes no tienen que elegir por rondas: pueden simplemente comunicar sus preferencias sobre cursos individuales a un ordenador, y este elige los cursos por ellos uno a uno. Este procedimiento se ha utilizado, por ejemplo, en la Harvard Business School desde mediados de la década de 1990. ^{[ 2 ]} Una ventaja importante de los mecanismos de selección por turnos es que son relativamente justos, en el sentido de que todos los estudiantes obtienen su curso t -ésimo antes de que cualquier estudiante reciba su curso ( t +1)-ésimo.

Un problema del procedimiento de borrador es que no es inmune a la manipulación estratégica : los estudiantes podrían obtener mejores cursos manipulando sus preferencias declaradas. Además, el borrador es fácil de manipular: los estudiantes deberían sobreestimar su preferencia por los cursos más deseados y subestimar su preferencia por los menos deseados. Los resultados de un estudio de campo en Harvard muestran que los estudiantes sí manipulan sus preferencias, y esta manipulación conduce a asignaciones que no son eficientes en el sentido de Pareto y tienen un bajo bienestar social . ^{[ 2 ]}

Una variante del borrador que puede reducir las ineficiencias debidas a la manipulación es el borrador proxy . En este mecanismo, los estudiantes siguen informando sus preferencias a una computadora, pero esta vez, la computadora manipula las preferencias por ellos de manera óptima y luego ejecuta el borrador original. Este procedimiento reduce la pérdida de bienestar debida a errores en la manipulación y a la falta de conocimiento de la posición en la secuencia de elección. ^{[ 3 ] : 5} Otras variantes son el borrador de búsqueda ^{[ 4 ]} y el borrador de mejora de Pareto . ^{[ 5 ]}

Otro problema del sistema de asignación aleatoria es que solo considera la clasificación ordinal de los estudiantes e ignora sus preferencias cardinales. Esto puede generar ineficiencias. Por ejemplo, supongamos que el primer estudiante en el orden aleatorio prefiere ligeramente el curso A al curso B, mientras que el segundo estudiante prefiere claramente A al B. El mecanismo de asignación aleatoria asignará A al primer estudiante, pero habría sido más eficiente (al menos desde una perspectiva utilitarista ) asignar A al segundo estudiante.

Los teóricos económicos han demostrado que la dictadura serial aleatoria (DSR) es el único mecanismo a prueba de manipulación que es Pareto-eficiente ex post y satisface otras propiedades naturales. Basándose en este hecho teórico, sugirieron su uso práctico para la asignación de cursos. ^{[ 6 ] [ 7 ] [ 8 ]}

Sin embargo, los experimentos de campo han demostrado que RSD funciona peor que el mecanismo de selección manipulable en medidas naturales como el número de estudiantes que obtienen su primera opción y el rango promedio de los cursos por estudiante. ^{[ 3 ] : 5}

En un mecanismo de subasta , a cada estudiante se le asigna una cantidad fija de dinero ficticio, que puede distribuir entre los cursos que desea cursar. Las ofertas de todos los estudiantes para todos los cursos se ordenan de mayor a menor y se procesan una a una. Cada oferta se acepta solo si el estudiante no ha completado su horario y el curso tiene plazas disponibles. Mecanismos similares se utilizan en la Ross School of Business , la Columbia Business School , la Haas School of Business , la Kellogg School of Management , la Universidad de Princeton , la Yale School of Management ^{[ 9 ]} y la Universidad de Tel Aviv ^{[ 10 ]} .

Los mecanismos de licitación presentan varias desventajas. En primer lugar, al igual que las subastas de primer precio , no son inmunes a la manipulación estratégica. Esto puede llevar a que los estudiantes dediquen mucho esfuerzo a decidir cuánto pujar por cada curso, adivinando cuánto pujarían otros estudiantes. En segundo lugar, los resultados pueden ser ineficientes. Las pujas de los estudiantes cumplen dos funciones: inferir las preferencias de los estudiantes y determinar quién tiene mayor derecho a un cupo. Estas dos funciones pueden entrar en conflicto, lo que puede generar resultados ineficientes. ^{[ 11 ]} En tercer lugar, el resultado de un mecanismo de licitación puede ser muy injusto: algunos estudiantes pueden no recibir ningún curso deseado, mientras que otros reciben todos los que desean. ^{[ 12 ]}

Kominers, Rubbery y Ullman ^{[ 1 ]} presentan un mecanismo de puja por poder , cuyo objetivo es calcular manipulaciones de alta calidad en nombre de cada estudiante. Según sus simulaciones, este mecanismo reduce los incentivos para manipular y, por lo tanto, puede mejorar la eficiencia.

En un mecanismo de equilibrio , cada estudiante puede clasificar todos los horarios factibles de los cursos (es decir, todos los subconjuntos de cursos en los que ningún par de cursos se superpone en el tiempo, ningún par de cursos enseña el mismo material en diferentes momentos, etc.). Luego, una computadora encuentra un equilibrio competitivo de ingresos iguales en este mercado. Dado que puede no existir un equilibrio competitivo exacto, un mecanismo que se usa con frecuencia en la práctica es el Equilibrio Competitivo Aproximado de Ingresos Iguales (A-CEEI). Eric Budish desarrolló la teoría; ^{[ 12 ]} Othman y Sandholm ^{[ 13 ]} proporcionaron implementaciones informáticas eficientes. Budish, Cachon, Kessler y Othman mejoraron la implementación; su implementación, llamada CourseMatch, se ha implementado en la Wharton Business School , reemplazando el mecanismo anterior basado en ofertas. ^{[ 14 ]} Ha sido implementado comercialmente por Cognomos. ^{[ 15 ]} Recientemente, Budish, Gao, Othman, Rubinstein y Zhang presentaron un nuevo algoritmo para encontrar un CEEI aproximado, que es sustancialmente más rápido, alcanza un error de liquidación cero en todas las instancias prácticas y tiene mejores propiedades de incentivo que el algoritmo anterior. ^{[ 16 ]}

La necesidad de informar una clasificación de horarios es un desafío importante en la implementación de dichos algoritmos, ya que el número de horarios factibles puede ser muy grande. ^{[ 17 ] [ 18 ]} Superar este desafío requiere diseñar un lenguaje simple que permita a los estudiantes describir sus preferencias en un tiempo razonable. El lenguaje desarrollado en Wharton permite a los estudiantes especificar una utilidad para cada curso individual y un "valor de ajuste" para cada par de cursos. La utilidad de cada par es la suma de las utilidades de los cursos individuales, más el valor de ajuste. Los valores de ajuste cero, positivos y negativos corresponden a cursos que son bienes independientes , complementarios y sustitutivos , respectivamente. Además, algunas combinaciones específicas de cursos (por ejemplo, aquellos que se imparten al mismo tiempo o tienen el mismo contenido) están específicamente prohibidas. Si bien este lenguaje no permite expresar todas las clasificaciones posibles de horarios, es suficiente en la práctica. ^{[ 14 ]}

Soumalis, Zamanlooy, Weissteiner y Seuken ^{[ 19 ]} presentan un método para utilizar el aprendizaje automático para aprender y corregir errores en el informe de los estudiantes.

Un problema importante de A-CEEI es que requiere mucha capacidad de cálculo, ya que necesita buscar en el espacio de vectores de precios y, para cada vector de precios, debe calcular las combinaciones óptimas de muchos estudiantes.

Atef-Yekta y Day ^{[ 20 ]} buscan mejorar la eficiencia de los mecanismos de selección incorporando elementos de subasta, manteniendo al mismo tiempo su estructura ronda por ronda que mejora la equidad. Presentan varios algoritmos heurísticos:

• Algoritmo TTC : inspirado en los ciclos de negociación más altos . Cada estudiante distribuye 1000 puntos entre cursos. En cada ronda, cada estudiante señala el curso de mayor valor entre los restantes que le son factibles. Cada curso acepta a los postores con las ofertas más altas según su capacidad y rechaza a los que ofrecen las más bajas. Los estudiantes rechazados señalan su nuevo curso de mayor valor, y el proceso se repite hasta que todos los estudiantes reciben un curso. Solo entonces, el algoritmo pasa a la siguiente ronda. El objetivo es combinar la eficiencia de la subasta con la equidad del proceso de selección.
• Algoritmo SP : inspirado en la subasta de segundo precio . Es similar al TTC multironda, con una diferencia: para cada curso con capacidad q , todos los estudiantes aceptados pagan el ( q + 1)-ésimo "precio" (en puntos), y los puntos restantes (la oferta menos el precio) se transfieren a su mejor curso restante, lo que mejora sus posibilidades de ganarlo en la siguiente ronda.
• TTC-O y SP-O : versiones optimizadas de TTC y SP; que utilizan programación lineal entera para calcular el bienestar óptimo global.
• Algoritmo OC : este algoritmo no se ejecuta ronda por ronda; realiza una optimización global de los rangos ordinales y, en consecuencia, una optimización global de la suma de las utilidades cardinales. La optimización se realiza mediante programación lineal entera. Este mecanismo es Pareto-eficiente con respecto a los rangos ordinales.

Compararon sus cinco algoritmos con los mecanismos de licitación y selección en 100 mercados de muestra, cada uno con 900 estudiantes y una capacidad de 6 cursos. Había 112 secciones de cursos, algunas pertenecientes al mismo curso y otras superpuestas (por lo que no se pueden cursar juntas). Las capacidades de los cursos se seleccionaron aleatoriamente a partir de distribuciones uniformes discretas. Las características son similares a las de la Harvard Business School . Evaluaron los algoritmos utilizando varias métricas:

• Binario : el número promedio de plazas por curso por estudiante (una medida de eficiencia), y el rango y la desviación estándar (dos medidas de equidad).
• Ordinal : el promedio del rango total por estudiante, y el rango y la desviación estándar.
• Cardinal : la utilidad total promedio por estudiante, y el rango y la desviación estándar.

En los aspectos binarios y ordinales, OC obtuvo la mejor puntuación en eficiencia y equidad; seguido de SP-O y TTC-O; luego Draft, SP y TTC; y Bidding obtuvo la peor puntuación. En el aspecto cardinal, OC y BPM fueron los más eficientes, pero SP-O y TTC-O fueron los más equitativos. Draft fue muy ineficiente y BPM muy injusto, mientras que SP y TTC fueron moderadamente eficientes y moderadamente equitativos.

Dado que ningún algoritmo es inmune a la manipulación estratégica, estudiaron los incentivos para dicha manipulación en cada uno de ellos, es decir, cuánto puede ganar un estudiante mediante ella. Sus experimentos demuestran que, en el mecanismo de pujas, la ganancia para los manipuladores es mayor, y el daño que la manipulación causa a los estudiantes honestos también es mayor. La menor combinación de ganancia y daño se observó en TTC-O, SP-O y Draft.

La mayoría de los trabajos asumen que solo los estudiantes tienen preferencias sobre los cursos, mientras que los cursos no tienen preferencias; es decir, el mercado es unilateral . Sin embargo, algunos trabajos asumen que los cursos también pueden tener preferencias y, por lo tanto, el mercado es bilateral . ^{[ 21 ]} El objetivo principal en un mercado bilateral es encontrar un emparejamiento estable , y el algoritmo principal es el algoritmo de Gale-Shapley (aceptación diferida, DA).

Diebold, Aziz, Bichler, Matthes y Schneider ^{[ 22 ]} comparan dos mecanismos: la asignación de clases óptima para el estudiante y la asignación de clases ajustada a la eficiencia. También analizan las extensiones recientes relativas a la asignación de horarios de cursos, en lugar de cursos individuales. Presentan un experimento de campo que demuestra las ventajas de los mecanismos de emparejamiento estables.

Diebold y Bichler ^{[ 23 ]} comparan varios mecanismos para el emparejamiento bilateral en la información de asignación de cursos.

Krishna y Unver ^{[ 24 ]} y Sonmez y Unver ^{[ 9 ]} consideran un mercado unilateral, pero aun así sugieren usar un emparejamiento bilateral. Su razonamiento es que, en los mecanismos existentes, las ofertas de los estudiantes tienen dos funciones diferentes: se usan para determinar quién tiene mayor derecho a cada plaza en el curso (y en esta función, se usan como herramienta estratégica); y se usan para inferir las preferencias de los estudiantes. Sugieren separar estas dos funciones: permiten que cada estudiante reporte tanto un valor cardinal para cada curso como una clasificación ordinal de los cursos; estos dos informes no tienen por qué ser consistentes. Al ejecutar DA, las preferencias de los estudiantes se determinan por sus clasificaciones ordinales, y las preferencias de los cursos se determinan por los valores cardinales de los estudiantes. En efecto, un curso "prefiere" aceptar a un estudiante que lo desea más. Como en el algoritmo DA, cada estudiante "propone" al curso mejor clasificado en su clasificación ordinal; los cursos con mayor demanda ordenan entonces a los estudiantes según sus valores cardinales y rechazan a los más bajos. Según los informes, basándose en la teoría y en experimentos de campo, este esquema mejora la eficiencia de la asignación. Sin embargo, informar dos conjuntos de preferencias inconsistentes puede aumentar los problemas de incentivos. Además, el algoritmo no ofrece garantías de equidad.

Otros mecanismos para la asignación de cursos utilizan una asignación aleatoria justa . ^{[ 25 ]}