Experimental Design for Matching

Resumen Técnico: Diseño Experimental para el Emparejamiento (Matching)

Planteamiento del Problema
Los mecanismos de emparejamiento son infraestructuras críticas en la gestión de operaciones, abarcando la educación, la atención médica y las plataformas digitales. Un desafío fundamental surge cuando los profesionales buscan comparar empíricamente un nuevo algoritmo de emparejamiento (tratamiento) contra un statu quo (control) en una población finita. Los métodos estándar de inferencia causal enfrentan un obstáculo único en este entorno: la interferencia de emparejamiento. A diferencia de las unidades experimentales independientes, asignar una unidad a un emparejamiento específico en el plan de tratamiento puede impedir su asignación en el plan de control debido a restricciones de capacidad y compatibilidad. En consecuencia, los contrafácticos a nivel individual son inobservables y las decisiones de aleatorización están vinculadas entre las unidades. La literatura existente a menudo se centra en mitigar el sesgo dentro de un mecanismo de emparejamiento fijo o asume modelos conductuales o de resultados específicos. Este artículo aborda la brecha de cómo comparar experimentalmente dos planes de emparejamiento predeterminados sin imponer modelos de resultados o de comportamiento, basándose únicamente en una perspectiva de diseño.

Metodología
Los autores proponen el Diseño de Caminos Aleatorios Alternos (Diseño AP), un marco fundamentado en la teoría de grafos y la inferencia basada en el diseño.

1. Conjunto de Desacuerdo y Descomposición:
   La visión estructural central es la definición del conjunto de desacuerdo ($\Delta M_{(t,c)}$), que comprende pares de emparejamiento presentes en exactamente uno de los dos planes (tratamiento o control). El artículo demuestra que, para emparejamientos de uno a uno, este conjunto admite una descomposición única en caminos alternos y ciclos disjuntos. En estas estructuras, las aristas alternan entre el emparejamiento de tratamiento ($M_t$) y el de control ($M_c$). Debido a las restricciones de capacidad, las aristas adyacentes en un camino alterno o ciclo no pueden realizarse simultáneamente.

2. Esquema de Aleatorización:
   El Diseño AP realiza una aleatorización secuencial a lo largo de estos caminos y ciclos.

   • Caso de Camino: Para un camino abierto, la primera arista se selecciona con una probabilidad de $p/(1+p)$. Las aristas subsiguientes se seleccionan con una probabilidad condicional de $p$ si el predecesor no fue seleccionado; de lo contrario, la arista se omite determinísticamente (probabilidad 0).
   • Caso de Ciclo: Se aplican reglas secuenciales similares, con la última arista determinada de forma determinística basándose en la realización de la primera y la penúltima arista para asegurar la factibilidad.
   • Independencia: La aleatorización se realiza de forma independiente en diferentes caminos y ciclos.

3. Estimación:
   Los autores utilizan el estimador de Horvitz-Thompson para estimar el Efecto de Tratamiento Promedio (ATE). Establecen la imparcialidad de este estimador bajo el diseño AP.

4. Optimización (Marco Minimax):
   Para optimizar la eficiencia, los autores analizan la varianza en el peor de los casos del estimador bajo un supuesto de resultados potenciales acotados. Formulan un problema minimax para encontrar la probabilidad de aleatorización condicional óptima $p$.

   • Resultado Asintótico: Para caminos y ciclos largos, la $p$ óptima converge a $\sqrt{2} - 1 \approx 0.4142$. Este valor es estrictamente menor que 0.5, lo que refleja un compromiso donde la reducción de la contribución de la varianza de la arista actual requiere considerar la interferencia descendente.

5. Extensión de Muchos a Uno:
   El marco se extiende a emparejamientos de muchos a uno (por ejemplo, la asignación de estudiantes a escuelas), donde las restricciones de capacidad complican la descomposición. Los autores construyen un grafo dirigido desbalanceado auxiliar para representar el conjunto de desacuerdo. Reducen el problema de encontrar una descomposición factible a dos tareas de teoría de grafos:

   • Encontrar caminos de aumento en una red de flujo construida para manejar los desequilibrios en los grados de los nodos.
   • Realizar descomposiciones de tours de Euler en el grafo balanceado residual.
     Esto asegura que los caminos alternos y ciclos resultantes satisfagan las restricciones de capacidad, permitiendo que el diseño AP y las garantías de inferencia se trasladen.

Resultados Clave

• Imparcialidad: El estimador de Horvitz-Thompson bajo el diseño AP es imparcial para el ATE.
• Escalamiento de la Varianza: A diferencia de los diseños ingenuos (que seleccionan todo el emparejamiento de tratamiento o control con una probabilidad de 0.5), donde la varianza no desaparece a medida que el tamaño de la población $N \to \infty$, la varianza del estimador AP disminuye a una tasa de $O(1/N)$.
• Teorema del Límite Central (TLC): El artículo establece un TLC de población finita para el estimador. Este resultado es no trivial porque la descomposición del conjunto de desacuerdo puede exhibir patrones complejos, heterogéneos y potencialmente inestables (mezclas de componentes cortos y largos) a medida que la población crece. La prueba combina argumentos de Lindeberg-Feller con técnicas de $\alpha$-mezcla y el teorema de Bolzano-Weierstrass.
• Límites de Varianza: Los autores derivan un límite superior estimable para la varianza que depende solo de cantidades observables, lo que permite la construcción de intervalos de confianza asintóticos.
• Validación Numérica: Utilizando un conjunto de datos de fuerza laboral (Revelio Labs), los experimentos numéricos confirman que el diseño AP supera significativamente al diseño ingenuo en términos de reducción de la varianza. La distribución empírica del estimador se alinea con la distribución normal estándar, validando el TLC. La $p$ óptima empírica ($\approx 0.417$) coincide estrechamente con el óptimo teórico del peor caso ($\sqrt{2}-1$).

Significancia y Reivindicaciones
El artículo afirma proporcionar un marco basado en el diseño y libre de supuestos para probar mecanismos de emparejamiento. Su significancia radica en:

1. Abordar la Interferencia de Emparejamiento: Ofrece una solución fundamentada al problema específico de la interferencia de emparejamiento inherente a los mercados de emparejamiento, donde las unidades no son independientes.
2. Innovación Estructural: La descomposición única del conjunto de desacuerdo en caminos y ciclos alternos proporciona una base estructural rigurosa para gestionar la interferencia.
3. Inferencia Robusta: Al establecer un TLC que acomoda estructuras de componentes inestables y heterogéneas, el trabajo permite una inferencia asintótica válida en entornos de emparejamiento complejos sin requerir modelos de resultados.
4. Aplicabilidad Práctica: La extensión a emparejamientos de muchos a uno mediante herramientas de teoría de grafos (caminos de aumento y tours de Euler) hace que la metodología sea aplicable a escenarios del mundo real con restricciones de capacidad, como el intercambio de órganos o la elección de escuelas.

Los autores posicionan este trabajo como una perspectiva complementaria al modelado estructural, ofreciendo un terreno de prueba empírica directa para nuevos algoritmos de emparejamiento frente a los estatus quo en la gestión de operaciones y el diseño de plataformas.