Your Recourse, My Loss? Algorithmic Recourse under Shared Constraints

Resumen Técnico: "¿Tu Recurso, Mi Pérdida? Recurso Algorítmico bajo Restricciones Compartidas"

Enunciado del Problema

La investigación actual sobre recurso algorítmico opera predominantemente bajo una asunción uno-a-uno, donde un único individuo busca una acción de costo mínimo para revertir una decisión desfavorable de un único modelo. Sin embargo, los sistemas de toma de decisiones del mundo real a menudo implican interacciones muchos-a-muchos: múltiples individuos (buscadores) compiten por recursos limitados de múltiples tomadores de decisiones (proveedores).

En estos entornos, las recomendaciones de recurso óptimas individualmente no son independientes. Cuando los proveedores tienen restricciones de capacidad (un límite sobre cuántos individuos pueden aceptar), la validez de una recomendación de recurso para un buscador depende de las acciones de los demás. Optimizar el bienestar individual de forma aislada ignora estas interacciones, lo que conduce a una brecha de bienestar: la diferencia entre el resultado teóricamente óptimo si cada buscador pudiera acceder a su proveedor preferido y el resultado realizado bajo restricciones de capacidad. La literatura existente ha abordado escenarios de múltiples buscadores, pero típicamente asume un único proveedor o ignora el problema de asignación a nivel de sistema inherente a la capacidad de recurso limitada.

Metodología

Los autores proponen un marco que modela el recurso algorítmico multiagente como un problema de emparejamiento bipartito ponderado con capacidad.

1. Formalización del Problema:
   • Buscadores ($S$) y Proveedores ($P$): Los buscadores se caracterizan por vectores de características; los proveedores poseen modelos de decisión (clasificadores) y una capacidad de emparejamiento $k_j$.
   • Costo de Recurso: Para cada par buscador-proveedor $(i, j)$, se precalcula un costo de recurso $c_{ij}$, que representa el esfuerzo mínimo para cambiar las características del buscador y satisfacer el modelo del proveedor $j$.
   • Transformación de Pesos: Los costos se convierten en pesos de arista $w_{ij} = e^{-\gamma \cdot c_{ij}}$, donde $\gamma$ es un parámetro de escala. Esta transformación refleja la Aversión Constante al Riesgo Absoluto (CARA), priorizando intervenciones de bajo costo.
   • Capas de Optimización:
     • Capa 1 (Emparejamiento Básico): Resuelve un Programa Lineal Entero Mixto (MILP) para maximizar el bienestar social ($\sum w_{ij}z_{ij}$) sujeto a restricciones individuales y de capacidad. Esto establece el bienestar social de referencia bajo capacidades fijas.
     • Capa 2 (Redistribución Óptima de Capacidad): Aborda la Brecha de Bienestar optimizando la distribución de una capacidad total fija $K$ entre los proveedores. Los autores proponen el Algoritmo 1, un enfoque voraz que asigna capacidad a los proveedores basándose en la frecuencia de su aparición en los emparejamientos preferidos individualmente del top-$K$ (pesos más altos). Esto evita resolver un MILP completo para la asignación de capacidad, ofreciendo una solución directa que recupera el bienestar social óptimo.
     • Capa 3 (Optimización Consciente del Costo): Introduce una penalización por desviarse de la configuración de capacidad inicial ($\hat{k}_j$). La función objetivo equilibra la maximización del bienestar social con la minimización del costo de los ajustes de capacidad ($\sum \beta_j |\Delta k_j|$), haciendo que la solución sea práctica para la implementación en el mundo real donde los cambios estructurales son costosos.
   • Extensión Aversa a la Desigualdad: Para abordar la equidad, el objetivo utilitario lineal se reemplaza con una función de bienestar social cóncava ($\sum u_i^\alpha$). Esta formulación prioriza a los buscadores con menores utilidades (mayores costos de recurso), intercambiando eficiencia agregada por equidad distributiva. Se define una Métrica de Equidad ($E$) como la utilidad mínima alcanzada por cualquier buscador emparejado con éxito.

Contribuciones Clave

• Marco Muchos-a-Muchos: El artículo extiende el recurso algorítmico de recomendaciones individuales aisladas a un diseño a nivel de sistema que involucra múltiples buscadores y múltiples proveedores con restricciones de capacidad.
• Cuantificación de la Brecha de Bienestar: Define y cuantifica formalmente la pérdida de eficiencia (brecha de bienestar) que surge cuando las recomendaciones óptimas individualmente son inviables a nivel de sistema debido a restricciones de capacidad.
• Optimización de Tres Capas:
  1. Una formulación de emparejamiento con capacidad de referencia.
  2. Un algoritmo eficiente (Algoritmo 1) para redistribuir óptimamente la capacidad total fija y minimizar la brecha de bienestar.
  3. Una optimización consciente del costo que equilibra las ganancias de bienestar con los costos operativos de modificar las capacidades de los proveedores.
• Formulación Aversa a la Desigualdad: La introducción de un objetivo de bienestar cóncavo para priorizar explícitamente a los buscadores desfavorecidos, demostrando que se pueden lograr ganancias significativas en equidad con pérdidas marginales de eficiencia.

Resultados Experimentales

El marco se validó en conjuntos de datos sintéticos (Two-Moon) y del mundo real (Crédito, COMPAS) con números variables de buscadores y proveedores.

• Logro de Bienestar: Bajo distribuciones de capacidad fijas y arbitrarias, el sistema alcanzó solo el 83–93% del bienestar individual teórico.
• Impacto de la Redistribución: Aplicar la redistribución óptima de capacidad (Capa 2) restauró el bienestar social al 100% del límite superior del bienestar individual, demostrando que la brecha de bienestar es causada principalmente por una mala asignación y no por la escasez de recursos.
• Compensaciones Conscientes del Costo: La optimización consciente del costo (Capa 3) alcanzó un bienestar casi óptimo (93–99% del óptimo) requiriendo solo ajustes menores a la configuración de capacidad inicial, demostrando la viabilidad práctica.
• Compensación Equidad-Eficiencia: En los experimentos aversos a la desigualdad, reducir el parámetro $\alpha$ (aumentando la aversión a la desigualdad) duplicó la utilidad mínima para los buscadores peor situados (Métrica de Equidad $E$) mientras incurrió en solo una pérdida de ~3.4% en el bienestar social total.
• Sensibilidad a Hiperparámetros: El estudio analizó el parámetro de escala $\gamma$, identificando una relación en forma de "U" entre $\gamma$ y el logro de bienestar. Sugiere un rango operativo (el "codo" de la curva) donde las diferencias de costo son significativas sin hacer indistinguibles las alternativas no óptimas.

Significado y Afirmaciones

El artículo afirma cerrar la brecha entre el recurso algorítmico individual y el diseño a nivel de sistema. Su significado principal radica en demostrar que:

1. La Coordinación a Nivel de Sistema es Esencial: Las recomendaciones óptimas individualmente son insuficientes en entornos con recursos limitados; es necesaria una asignación coordinada para lograr un bienestar social casi óptimo.
2. La Eficiencia es Alcanzable con Mínimo Cambio: La brecha de bienestar puede cerrarse casi por completo redistribuyendo óptimamente los recursos existentes, en lugar de requerir aumentos masivos en la capacidad total.
3. El Recurso es una Elección de Diseño: La asignación del recurso no es meramente un problema de optimización técnica, sino una decisión de diseño de sistema cargada de valores. El marco proporciona un camino tratable para equilibrar la eficiencia agregada con la equidad distributiva, permitiendo a las partes interesadas elegir explícitamente cómo priorizar a los individuos más desfavorecidos cuando los recursos son escasos.

Los autores concluyen que su trabajo proporciona una base para diseñar sistemas de recurso que no solo sean accionables para los individuos, sino también eficientes y equitativos a nivel de población.