Resumen Técnico: Transporte Óptimo bajo Restricciones de Equidad de Grupo

1. Planteamiento del Problema

El artículo aborda el desafío de garantizar la equidad de grupo (group fairness) en los mecanismos de emparejamiento algorítmico, los cuales se utilizan cada vez más para asignar recursos escasos (por ejemplo, empleos, admisiones escolares o intercambios de riñones). Si bien el Transporte Óptimo (OT) estándar proporciona un marco poderoso para emparejar dos distribuciones basadas en la similitud de características, puede reforzar o amplificar inadvertidamente las disparidades existentes si las características están correlacionadas con atributos sensibles (por ejemplo, el estatus socioeconómico o la etnia).

Los autores formalizan una nueva noción de equidad de grupo para el OT. A diferencia de trabajos previos centrados en la equidad individual o restricciones específicas (como la participación mínima), este enfoque permite que un planificador central especifique una matriz de objetivos de equidad $F$. Esta matriz define la probabilidad deseada de emparejar individuos de cualquier grupo $s$ en la población de origen con cualquier grupo $w$ en la población de destino. El objetivo es encontrar un plan de OT que minimice el costo de transporte mientras se satisfacen estas restricciones explícitas de masa intergrupal.

2. Metodología

El artículo propone una jerarquía de enfoques para resolver este problema, que van desde restricciones exactas hasta formulaciones relajadas.

2.1. Equidad Exacta: FairSinkhorn

Para escenarios que requieren un cumplimiento estricto de los objetivos de equidad, los autores definen el problema de OT con equidad $F$ ($F$-fair Optimal Transport). Esto implica minimizar el objetivo de OT entrópico sujeto a restricciones lineales donde la masa marginal entre los grupos $(s, w)$ debe ser igual a $F_{sw}$.

• Algoritmo: Derivan un algoritmo Sinkhorn modificado, denominado FairSinkhorn. Al analizar la formulación dual, demuestran que la solución conserva la estructura multiplicativa de las iteraciones estándar de Sinkhorn, pero incluye un paso de proyección adicional para imponer las restricciones de nivel de grupo.
• Garantía Teórica: Bajo el supuesto de medidas de soporte compacto, demuestran la existencia y unicidad del plan de OT con equidad.

2.2. Estrategias de Equidad Aproximada

Reconociendo que la equidad exacta puede degradar significamente la calidad del emparejamiento (el "precio de la equidad"), los autores proponen dos estrategias de relajación:

A. OT con Penalización por Equidad

Este enfoque incorpora la violación de la equidad como un término de penalización en la función objetivo:
$$\min_{\Pi} \text{Tr}[\Pi^\top C] + \varepsilon \text{KL}(\Pi) + \lambda L_F(\Pi)$$
donde $L_F(\Pi)$ es el error cuadrático entre las probabilidades reales de emparejamiento de grupo y el objetivo $F$, y $\lambda$ controla la compensación (trade-off).

• Optimización: El problema sigue siendo convexo. Se resuelve utilizando un algoritmo de gradiente condicional generalizado, donde cada iteración linealiza la penalización de equidad y resuelve un subproblema (un OT entrópico con un costo modificado) mediante el algoritmo Sinkhorn estándar.
• Complejidad de Muestra: Los autores derivan un nuevo límite de complejidad de muestra finita para este problema penalizado. Demuestran que el error de estimación escala como $O(n^{-1/2})$, igualando al OT entrópico estándar, lo que implica que añadir la penalización de equidad no reduce la eficiencia estadística.

B. Aprendizaje de Costos mediante Optimización Bilevel

Esta estrategia aprende una función de costo base $c_\theta$ tal que el plan de OT resultante satisface naturalmente los objetivos de equidad.

• Formulación: Se plantea un problema de optimización bilevel donde el bucle externo minimiza la pérdida de equidad $L_F(\Pi_\varepsilon(c_\theta))$ con respecto a los parámetros del costo $\theta$, y el bucle interno resuelve el problema de OT para un costo fijo.
• Parametrizaciones: La función de costo puede parametrizarse como una distancia de Mahalanobis (transformación lineal de las características) o mediante redes neuronales (incrustaciones no lineales).
• Generalización: Una ventaja clave es la capacidad de reutilización; una vez aprendido $c_\theta$, este puede aplicarse a nuevas muestras no vistas utilizando OT estándar sin necesidad de una nueva optimización.
• Garantía Teórica: Los autores establecen un límite uniforme sobre la desviación de la equidad entre la solución de la población y las aproximaciones de muestra finita para cualquier costo en la familia parametrizada. El límite depende del tamaño de la muestra y de la acotación de la función de costo.

3. Contribuciones Clave

1. Noción de Equidad Novedosa: Introducción de una definición de equidad de grupo basada en objetivos y flexible para el OT, que permite a los planificadores especificar arbitrarias probabilidades de emparejamiento intergrupal.
2. Algoritmos:
   • FairSinkhorn: Un resolvedor exacto para planes de OT con equidad.
   • OT Penalizado: Una relajación convexa que permite compensaciones ajustables entre costo y equidad.
   • Aprendizaje de Costos: Un marco de optimización bilevel para aprender costos que inducen emparejamientos equitativos, permitiendo la generalización a nuevos datos.
3. Análisis Teórico:
   • Prueba de existencia/unicidad para el OT con equidad exacto.
   • Derivación de un límite de complejidad de muestra para el OT entrópico penalizado (mostrando una convergencia de $O(n^{-1/2})$).
   • Derivación de un límite de desviación uniforme para el enfoque de aprendizaje de costos, garantizando la equidad en datos no vistos.
4. Validación Empírica: Experimentos con datos sintéticos (mezclas gaussianas y distribuciones circulares) y un conjunto de datos semi-sintético de una aplicación de citas demuestran la efectividad de los enfoques y las compensaciones entre costo y equidad.

4. Resultados

• Control de la Compensación (Trade-off): El enfoque penalizado logra interpolar con éxito entre el OT convencional (bajo costo, alta inequidad) y FairSinkhorn (equidad perfecta, alto costo), permitiendo un control detallado mediante el parámetro de penalización $\lambda$.
• Sensibilidad a la Geometría: En los conjuntos de datos sintéticos, el enfoque penalizado generalmente logra una mejor compensación entre costo y equidad que el aprendizaje de costos cuando la geometría de los datos es compleja (por ejemplo, distribuciones circulares), ya que el OT penalizado no impone restricciones estructurales al mapa de transporte. Sin embargo, el aprendizaje de costos con redes neuronales puede aproximar objetivos complejos donde los costos lineales (Mahalanobis) fallan.
• Generalización: En el experimento de "reutilización", los costos aprendidos (tanto Mahalanobis como MLP) mantuvieron niveles de equidad en nuevas muestras de prueba comparables al rendimiento de entrenamiento, superando significativamente al OT convencional. El tiempo de inferencia para aplicar un costo aprendido fue significativamente menor que resolver un nuevo OT penalizado para cada nuevo lote.
• Aplicación en el Mundo Real: En el conjunto de datos de la aplicación de citas (alta dimensionalidad, múltiples grupos), los métodos reprodujeron la compensación convexa entre costo y equidad observada en los entornos sintéticos, validando su aplicabilidad a escenarios complejos y reales.

5. Significado y Reivindicaciones

El artículo afirma proporcionar un marco basado en principios para que reguladores y diseñadores de mercados impongan objetivos de equidad en los mecanismos de emparejamiento. Al enmarcar la equidad como restricciones de masa explícitas entre grupos, este trabajo cierra la brecha entre el transporte óptimo teórico y los requisitos prácticos de política (por ejemplo, cuotas o metas de diversidad).

Los autores enfatizan que su trabajo:

• Ofrece una definición flexible de equidad que puede acomodar diversos objetivos legislativos o políticos (por ejemplo, la regla de los cuatro quintos o cuotas de diversidad).
• Proporciona garantías teóricas tanto de la eficiencia estadística del enfoque penalizado como de la capacidad de generalización del enfoque de aprendizaje de costos.
• Destaca la compensación entre eficiencia (costo de transporte) y equidad, demostrando que, si bien la equidad exacta es posible, los enfoques relajados suelen ofrecer un equilibrio más práctico.

El artículo concluye señalando las limitaciones: el marco actual se centra en la equidad de grupo y no se extiende directamente a la equidad individual. Además, aunque los métodos optimizan el proceso de emparejamiento, los autores reconocen que el diseño del objetivo de equidad en sí mismo sigue siendo una decisión política y ética que queda fuera del alcance del algoritmo. Se sugiere como trabajo futuro explorar la equidad individual, un análisis más profundo de la relación entre equidad y sesgo, y el modelado del impacto de los emparejamientos en los resultados individuales.