Two-Stage Stochastic Capacity Expansion in Stable Matching under Truthful or Strategic Preference Uncertainty

Este artículo presenta un modelo de expansión de capacidad estocástica en dos etapas para el emparejamiento estable en mercados de elección escolar, donde se optimiza la asignación de plazas considerando tanto la incertidumbre exógena de las preferencias como la endógena derivada de la conducta estratégica de los estudiantes, demostrando que ignorar estos comportamientos conduce a decisiones de capacidad subóptimas.

Lo esencial

Imagina que eres el director de una gran escuela pública con muchos estudiantes que quieren entrar. Tienes un problema clásico: los asientos (capacidad) son limitados, pero la demanda es alta.

Este artículo de investigación es como un manual de instrucciones para tomar la decisión más inteligente sobre cuántas aulas nuevas construir antes de saber exactamente qué escuelas prefieren los estudiantes.

Aquí te explico los conceptos clave usando analogías sencillas:

1. El Dilema del "Chef de Cocina" (La Incertidumbre)

Imagina que eres un chef que debe preparar un banquete para 1,000 personas.

• El problema: Tienes que comprar los ingredientes y preparar los platos antes de que los invitados lleguen y digan qué quieren comer.
• La realidad: Si preparas 500 pizzas y 500 ensaladas basándote en una "apuesta promedio" (quizás piensas que a la mitad les gusta pizza y a la otra mitad ensalada), podrías terminar con 300 pizzas sin comer y 200 personas sin ensalada.
• La solución del artículo: En lugar de adivinar el "promedio", el artículo propone usar una simulación de muchos escenarios. Imagina que el chef prepara 100 versiones diferentes del menú basándose en cómo podría comportarse la gente en diferentes situaciones (lluvia, fiesta, día de trabajo). Luego, elige la estrategia de compra de ingredientes que funcione mejor en casi todos esos escenarios posibles.

2. El Juego de las Sillas Musicales (La Estabilidad)

En el mundo de las escuelas, no basta con asignar asientos; la asignación debe ser "estable".

• La analogía: Imagina un juego de sillas musicales. Si un estudiante está en una silla (escuela) que no le gusta, pero hay otra silla vacía o ocupada por alguien a quien le gusta menos, y el estudiante tiene "mejores notas" que ese ocupante, se crea un caos (un "bloqueo").
• El objetivo: El sistema debe encontrar una asignación donde nadie quiera cambiar de silla a la fuerza. El algoritmo usado (llamado Deferred Acceptance) es como un árbitro muy estricto que asegura que nadie pueda quejarse de su asiento una vez que el juego termina.

3. Los Dos Tipos de Estudiantes (Verdad vs. Estrategia)

Aquí es donde el artículo se vuelve muy interesante. Los estudiantes no siempre dicen la verdad. Tienen dos "modos":

• Modo "Niño Bueno" (Verdad): El estudiante dice: "Quiero ir a la escuela A, luego a la B, luego a la C". No le importa si tiene pocas posibilidades de entrar a la A.
• Modo "Estratega" (Juego): El estudiante piensa: "La escuela A es mi favorita, pero sé que es muy difícil entrar. Si la pongo primero, me arriesgo a quedarme sin nada. Mejor pongo la escuela B (que es buena pero más fácil) como mi primera opción".
  • El giro: La decisión de "jugar" depende de cuántos asientos nuevos hayas construido. Si construyes más aulas en la escuela A, el estudiante siente que tiene más posibilidades y quizás se atreva a ponerla primero. Si no construyes nada, jugará a la defensiva.

4. El Gran Descubrimiento: No puedes ignorar el "Juego"

El estudio demuestra algo crucial:

• Si el director de la escuela construye aulas basándose en lo que dicen los "Niños Buenos" (que dicen la verdad), pero los estudiantes reales son "Estrategas", el resultado será un desastre.
• Analogía: Es como si el director construyera 100 aulas para fútbol porque cree que a todos les gusta el fútbol, pero en realidad, los estudiantes son "estrategas" que, al ver que hay pocas aulas de fútbol, deciden no inscribirse en absoluto y se van a otros deportes. El director pierde dinero y los estudiantes no se gradúan.

5. La Herramienta Mágica: SAA (Aproximación por Promedio de Muestras)

Como es imposible predecir el futuro con el 100% de certeza, los autores crearon un método matemático (SAA) que funciona así:

1. Generan miles de "futuros posibles" (escenarios).
2. En cada futuro, simulan cómo se comportarían los estudiantes (si dicen la verdad o si juegan).
3. Calculan la mejor cantidad de aulas para construir que funcione bien en todos esos futuros.

El resultado: Este método es mucho mejor que simplemente mirar el "promedio" de lo que la gente dice. Permite que más estudiantes entren a sus escuelas preferidas y reduce el desperdicio de dinero en aulas que nadie usa.

En Resumen

Este paper es un consejo para los planificadores de ciudades y escuelas: No construyas el futuro basándote en lo que la gente dice que hará hoy.

Debes entender que:

1. La gente cambia su comportamiento según las reglas del juego (cuántos asientos hay).
2. Si ignoras esta estrategia y la incertidumbre, terminarás con escuelas vacías o estudiantes frustrados.
3. Usar simulaciones avanzadas (como las que proponen) te permite tomar decisiones más inteligentes, ahorrando dinero y haciendo más felices a los estudiantes.

Es como si dejaras de adivinar qué ropa vender en una tienda y empezaras a usar un sistema que predice el clima, las tendencias y el comportamiento de los compradores para decidir exactamente qué stock tener, evitando que te quedes con ropa que nadie quiere.

Resumen técnico

Aquí presento un resumen técnico detallado del artículo "Two-Stage Stochastic Capacity Expansion in Stable Matching under Truthful or Strategic Preference Uncertainty" (Expansión de Capacidad Estocástica de Dos Etapas en Emparejamiento Estable bajo Incertidumbre de Preferencias Verdaderas o Estratégicas), escrito por Bazotte, Carvalho y Vidal.

---

1. Planteamiento del Problema

El artículo aborda un problema de optimización en mercados de emparejamiento muchos-a-uno (como la admisión escolar o la asignación de residencias médicas), donde una central de asignación (clearinghouse) debe decidir la expansión de capacidad de las instituciones (escuelas) antes de conocer las preferencias reales de los agentes (estudiantes).

Características clave del problema:

• Incertidumbre Temporal: Las decisiones de capacidad (primera etapa) se toman antes de que se revelen las preferencias de los estudiantes.
• Comportamiento de los Agentes: Los estudiantes pueden actuar de dos formas:
  1. Veraz (Truthful - UM): Reportan sus preferencias reales. La incertidumbre es exógena (independiente de la decisión).
  2. Estratégico (Strategic): Modifican sus preferencias reportadas basándose en sus preferencias reales y en sus creencias sobre las probabilidades de admisión, las cuales dependen de las capacidades decididas por la central. Esto genera incertidumbre endógena (dependiente de la decisión).
• Segunda Etapa: Una vez reveladas las preferencias reportadas, la central ejecuta un emparejamiento estable óptimo para el estudiante (usando el algoritmo de Aceptación Diferida - DAA) basado en las capacidades expandidas y las prioridades de las escuelas.
• Objetivo: Minimizar el valor esperado de la suma de los rangos de las asignaciones de los estudiantes (maximizar el bienestar estudiantil) sujeto a un presupuesto de expansión de capacidad.

El problema se denomina 2-STMMP (Two-Stage Stochastic Matching Problem with Uncertain Preferences).

2. Metodología

Los autores proponen un marco de Programación Estocástica de Dos Etapas utilizando la Aproximación por Promedio de Muestras (SAA - Sample Average Approximation) para manejar la gran cantidad de escenarios posibles de preferencias.

A. Modelado de Comportamientos

Se definen tres modelos de comportamiento estudiantil:

1. Maximización de Utilidad (UM): Los estudiantes reportan sus $K$ mejores opciones reales. Incertidumbre exógena.
2. Maximización Conjunta de Utilidad Esperada (CEUM): Basado en el problema de elección de cartera de Chade y Smith (2006). Los estudiantes seleccionan un subconjunto de escuelas para maximizar la utilidad esperada conjunta, considerando tanto la probabilidad de admisión como el riesgo de rechazo por parte de escuelas preferidas.
3. Maximización de Utilidad Esperada Individual (IEUM): Una aproximación simplificada donde los estudiantes maximizan la suma de utilidades individuales esperadas, ignorando el riesgo de rechazo de opciones superiores (racionalidad acotada).

En los casos estratégicos (CEUM e IEUM), las preferencias reportadas son funciones de las decisiones de capacidad ($x$) y las preferencias reales ($u$), creando un problema de nivel doble (bilevel) que se transforma en un programa de un solo nivel mediante técnicas de transformación de variables.

B. Formulación Matemática

• Programa SAA: Se discretiza la distribución de preferencias en un conjunto de escenarios $W_N$.
• Modelos Exactos:
  • Para UM: Se utiliza una formulación de "Restricciones L modificadas" (L-constraints) adaptada de trabajos previos.
  • Para CEUM e IEUM: Se desarrollan formulaciones exactas que integran algoritmos de optimización interna (MIA para CEUM, IOA para IEUM) dentro del programa estocástico para definir las preferencias reportadas. Esto resulta en programas de enteros mixtos (MILP) complejos con variables binarias adicionales para modelar la selección de preferencias.
• Heurísticas Propuestas: Debido a la complejidad computacional (NP-duro), se proponen métodos aproximados:
  1. Relajación Lagrangiana (LR): Específica para el caso UM. Relaja las restricciones de estabilidad para obtener cotas inferiores fuertes y utiliza el DAA para generar soluciones factibles.
  2. Búsqueda Local (LS): Un algoritmo voraz que explora vecindades de decisiones de capacidad (incrementar, transferir o intercambiar asientos).
  3. Recocido Simulado (SA): Un método probabilístico que permite aceptar soluciones peores temporalmente para escapar de óptimos locales, mostrando mayor escalabilidad que LS.

3. Contribuciones Clave

1. Modelo 2-STMMP: Introducción y definición formal del primer modelo de expansión de capacidad en emparejamiento estable que considera simultáneamente la incertidumbre de preferencias y el comportamiento estratégico de los agentes.
2. Transformación de Incertidumbre Endógena: Aplicación de métodos de transformación de variables para manejar la dependencia de las preferencias reportadas respecto a las decisiones de capacidad, permitiendo el uso de técnicas de SAA estándar.
3. Kit de Solución: Desarrollo de formulaciones matemáticas exactas y un conjunto de heurísticas (LR, LS, SA) adaptadas a cada comportamiento, demostrando que las heurísticas son esenciales para instancias grandes y estratégicas.
4. Análisis de Valor de la Solución Estocástica (VSS): Demostración cuantitativa de que ignorar la incertidumbre (usando escenarios promedios deterministas) conduce a decisiones de capacidad subóptimas.

4. Resultados Experimentales

Los experimentos se realizaron en instancias pequeñas y grandes (hasta 1000 estudiantes y 60 escuelas) con diferentes presupuestos y límites de longitud de lista ($K$).

• Superioridad del Enfoque Estocástico (SAA vs. EV):

  • Las soluciones basadas en SAA superan consistentemente al enfoque de escenario promedio (EV) en todos los comportamientos.
  • El Valor de la Solución Estocástica (VSS) es significativo: las decisiones estocásticas mejoran la asignación de los estudiantes (rangos más bajos) y aumentan el número de estudiantes que entran al mercado o mejoran su asignación en comparación con el enfoque determinista.
  • El VSS aumenta a medida que crece el presupuesto de expansión, indicando que la incertidumbre es más crítica cuando hay más opciones de decisión.

• Impacto del Comportamiento Estratégico:

  • Asumir comportamiento veraz (UM) cuando los estudiantes actúan estratégicamente (CEUM o IEUM) resulta en una pérdida significativa de calidad en la asignación (brechas de comportamiento del 5% al 10% en preferencias y hasta 30% en número de beneficiarios).
  • Efecto de $K$ (Longitud de lista):
    • Si $K$ es pequeño, las decisiones basadas en UM se asemejan más a las óptimas para IEUM.
    • Si $K$ es grande, las decisiones basadas en UM se acercan más a las óptimas para CEUM.
  • Error de Modelado: Asumir el comportamiento estratégico incorrecto (ej. asumir IEUM cuando es CEUM) también genera grandes pérdidas, subrayando la necesidad de modelar con precisión la psicología del agente.

• Rendimiento Computacional:

  • UM: Se puede resolver exactamente para instancias grandes en tiempos razonables, pero las heurísticas (especialmente LR y SA) son más rápidas y robustas.
  • Estratégico (CEUM/IEUM): Los métodos exactos fallan en encontrar soluciones óptimas en tiempos prácticos para instancias grandes (huecos de optimalidad cercanos al 100%). Las heurísticas SA y LS son esenciales, encontrando soluciones de alta calidad (huecos de cota superior < 1-2%) en segundos o minutos.

5. Significado e Implicaciones

Este trabajo tiene implicaciones profundas para el diseño de mecanismos en el sector público y privado:

1. Planificación de Capacidad: Las decisiones de infraestructura (construcción de aulas, contratación de personal) no deben basarse en promedios históricos de preferencias, sino en modelos estocásticos que anticipen la variabilidad y el comportamiento estratégico.
2. Bienestar Social: Ignorar la incertidumbre o el comportamiento estratégico lleva a una asignación ineficiente de recursos, dejando a estudiantes sin asignar o en escuelas menos preferidas, lo que tiene consecuencias sociales y económicas negativas.
3. Robustez del Mecanismo: Aunque los mecanismos como el DAA son "a prueba de estrategias" (strategy-proof) en un sentido teórico bajo preferencias fijas, la incertidumbre sobre las probabilidades de admisión induce a los estudiantes a comportarse estratégicamente. Los planificadores deben anticipar esto.
4. Aplicabilidad General: El marco 2-STMMP es aplicable más allá de la elección escolar, incluyendo la distribución de vacunas, reasentamiento de refugiados y asignación de recursos médicos, donde la capacidad se fija antes de conocer la demanda exacta.

En conclusión, el artículo establece que la gestión de la incertidumbre estocástica y la modelación precisa del comportamiento humano son componentes críticos e inseparables para la planificación eficiente de capacidades en mercados de emparejamiento.