Equidad Individual bajo Restricciones de Equidad Colectiva en Asignación Bipartita - Un Marco para Aproximarlas Todas

Estudiamos la asignación probabilística de elementos a plataformas que satisface tanto las restricciones de equidad colectiva como individual. Cada elemento pertenece a grupos específicos y tiene un orden de preferencias sobre las plataformas. Cada plataforma impone equidad colectiva limitando el número de elementos por grupo que pueden asignarse a ella. Podría haber múltiples soluciones óptimas que satisfacen las restricciones de equidad colectiva, pero esto por sí solo ignora las preferencias de los elementos. Nuestro enfoque explora una solución de 'equidad de lo mejor de ambos mundos' para obtener una asignación aleatoria, que es ex-ante individualmente justa y ex-post colectivamente justa. Así, buscamos una distribución 'probabilísticamente individualmente justa' sobre asignaciones 'justas en grupo' donde cada elemento tiene una probabilidad 'alta' de emparejarse con una de sus mejores opciones. Esta distribución también es ex-ante colectivamente justa. Los usuarios pueden personalizar las restricciones de equidad para adaptarlas a sus requisitos. Nuestro primer resultado es un algoritmo en tiempo polinómico que calcula una distribución sobre asignaciones 'justas en grupo' de tal manera que las restricciones de equidad individual se satisfacen aproximadamente y el tamaño esperado de una asignación está cerca de OPT. Probamos empíricamente esto en conjuntos de datos del mundo real. Presentamos dos algoritmos de aproximación bicriteria en tiempo polinómico adicionales que los usuarios pueden elegir para equilibrar los compromisos entre equidad colectiva y equidad individual. Para grupos disjuntos, proporcionamos un algoritmo exacto en tiempo polinómico adaptable a límites de 'equidad colectiva' inferiores adicionales. Ampliando nuestro modelo, abarcamos 'maxmin de equidad grupal,' amplificando grupos subrepresentados, y 'mindom de equidad grupal,' reduciendo la representación de grupos dominantes.