Estabilidad y aleatoriedad en admisión escolar

Abstract

En este trabajo se estudian dos preguntas surgidas durante la implementación del Sistema de Admisión Escolar chileno, el cual asigna de manera centralizada estudiantes a colegios según sus preferencias, usando el algoritmo de Aceptación Diferida y una regla de rompimiento de empates aleatoria. La primera pregunta tratada es sobre la existencia de asignaciones estables cuando las familias prefieren que sus hijos estudien en un mismo colegio en lugar de separados. Pri- meramente damos una definición formal de la estabilidad en este contexto, que llamamos estabilidad familiar. Probamos luego que si las preferencias de los colegios son sobre los estu- diantes no necesariamente existe asignación estable, incluso si son todas iguales. Probamos que si las preferencias de los colegios son todas iguales y según un orden sobre las familias entonces siempre existe asignación con estabilidad familiar, incluso si las preferencias de las familias son arbitrarias sobre todas las posibles asignaciones. En el caso en que las preferen- cias de los colegios pueden ser distintas y según órdenes sobre las familias, mostramos que no siempre existe asignación, incluso si las familias son indiferentes al colegio, condicional en que todos los hijos están en el mismo. Si en este último caso se agrega que los colegios prefieren siempre recibir completas a las familias con más de un hijo, entonces se garantiza estabilidad pero las familias tienen claros incentivos para mentir sobre su composición. La segunda pregunta estudiada es sobre la cantidad de asignaciones estables en un mercado bipartito con preferencias aleatorias cuando el número de agentes no es igual a ambos lados. A este respecto, extendemos al caso de preferencias aleatorias no uniformes, bajo el modelo de popularidades propuesto por Immorlica et al. [11], el resultado de Ashlagi et al. [4] que establece que la proporción de agentes con múltiples parejas estables tiende a 0 cuando las preferencias son uniformes y el mercado es desbalanceado. Mediante una adaptación de la demostración del resultado para preferencias uniformes y un resultado sobre el problema del Coleccionista de Cupones, encontramos condiciones necesarias sobre la dispersión de las popularidades y la popularidad del exceso de agentes en el lado largo del mercado, para que la proporción antes mencionada tienda a 0.