Sintesi Tecnica: Trasporto Ottimale sotto Vincoli di Equità di Gruppo

1. Definizione del Problema

Il documento affronta la sfida di garantire l'equità di gruppo (group fairness) nei meccanismi di abbinamento algoritmico (algorithmic matching), che vengono utilizzati sempre più spesso per allocare risorse scarse (ad esempio, posti di lavoro, ammissioni scolastiche o scambi di reni). Sebbene l'Ottimale Trasporto (OT) standard fornisca un potente quadro per abbinare due distribuzioni in base alla somiglianza delle caratteristiche, può involontariamente rafforzare o amplificare le disparità esistenti se le caratteristiche sono correlate con attributi sensibili (ad esempio, stato socioeconomico o etnia).

Gli autori formalizzano una nuova nozione di equità di gruppo per l'OT. A differenza dei lavori precedenti focalizzati sull'equità individuale o su vincoli specifici (come la partecipazione minima), questo approccio consente a un pianificatore centrale di specificare una matrice di obiettivi di equità $F$. Questa matrice definisce la probabilità desiderata di abbinare individui appartenenti a qualsiasi gruppo $s$ della popolazione sorgente a qualsiasi gruppo $w$ della popolazione target. L'obiettivo è trovare un piano di OT che minimizzi il costo di trasporto soddisfacendo al contempo questi espliciti vincoli di massa inter-gruppo.

2. Metodologia

Il documento propone una gerarchia di approcci per risolvere questo problema, che spaziano dai vincoli esatti alle formulazioni rilassate.

2.1. Equità Esatta: FairSinkhorn

Per scenari che richiedono l'aderenza rigorosa agli obiettivi di equità, gli autori definiscono il problema dell'OT equo-$F$ ($F$-fair Optimal Transport). Questo comporta la minimizzazione dell'obiettivo OT entropico soggetto a vincoli lineari in cui la massa marginale tra i gruppi $(s, w)$ deve essere uguale a $F_{sw}$.

• Algoritmo: Derivano un algoritmo Sinkhorn modificato, denominato FairSinkhorn. Analizzando la formulazione duale, dimostrano che la soluzione mantiene la struttura moltiplicativa delle iterazioni standard di Sinkhorn ma include un passaggio di proiezione aggiuntivo per imporre i vincoli a livello di gruppo.
• Garanzia Teorica: Sotto l'ipotesi di misure a supporto compatto, dimostrano l'esistenza e l'unicità del piano di OT equo.

2.2. Strategie di Equità Approssimata

Riconoscendo che l'equità esatta può degradare significamente la qualità dell'abbinamento (il "prezzo dell'equità"), gli autori propongono due strategie di rilassamento:

A. OT con Penalità di Equità (Fairness-Penalized OT)

Questo approccio incorpora la violazione dell'equità come termine di penalità nella funzione obiettivo:
$$\min_{\Pi} \text{Tr}[\Pi^\top C] + \varepsilon \text{KL}(\Pi) + \lambda L_F(\Pi)$$
dove $L_F(\Pi)$ è l'errore quadratico tra le probabilità di abbinamento di gruppo effettive e il target $F$, e $\lambda$ controlla il compromesso (trade-off).

• Ottimizzazione: Il problema rimane convesso. Viene risolto utilizzando un algoritmo di gradiente condizionato generalizzato, dove ogni iterazione linearizza la penalità di equità e risolve un sottoproblema (un OT entropico con costo modificato) tramite lo standard algoritmo Sinkhorn.
• Complessità di Campionamento: Gli autori derivano un nuovo limite di complessità del campione finito per questo problema penalizzato. Dimostrano che l'errore di stima scala come $O(n^{-1/2})$, eguagliando l'OT entropico standard, il che implica che l'aggiunta della penalità di equità non riduce l'efficienza statistica.

B. Apprendimento del Costo tramite Ottimizzazione Bilevel

Questa strategia apprende una funzione di costo fondamentale $c_\theta$ tale che il piano OT risultante soddisfi naturalmente gli obiettivi di equità.

• Formulazione: Viene posta un'ottimizzazione bilevel in cui il ciclo esterno minimizza la perdita di equità $L_F(\Pi_\varepsilon(c_\theta))$ rispetto ai parametri del costo $\theta$, e il ciclo interno risolve il problema OT per un costo fissato.
• Parametrizzazioni: La funzione di costo può essere parametrizzata come una distanza di Mahalanobis (trasformazione lineare delle caratteristiche) o tramite reti neurali (embedding non lineari).
• Generalizzazione: Un vantaggio chiave è la riutilizzabilità; una volta appreso $c_\theta$, esso può essere applicato a nuovi campioni non visti utilizzando l'OT standard senza una nuova ottimizzazione.
• Garanzia Teorica: Gli autori stabiliscono un limite uniforme sulla deviazione dell'equità tra la soluzione della popolazione e le approssimazioni a campione finito per qualsiasi costo nella famiglia parametrizzata. Il limite dipende dalla dimensione del campione e dalla limitatezza della funzione di costo.

3. Contributi Chiave

1. Nuova Nozione di Equità: Introduzione di una definizione flessibile di equità di gruppo basata su target per l'OT, che permette ai pianificatori di specificare arbitrari obiettivi di abbinamento inter-gruppo.
2. Algoritmi:
   • FairSinkhorn: Un risolutore esatto per piani di OT equi.
   • OT Penalizzato: Un rilassamento convesso che permette compromessi regolabili tra costo ed equità.
   • Apprendimento del Costo: Un framework di ottimizzazione bilevel per apprendere i costi che inducono abbinamenti equi, consentendo la generalizzazione a nuovi dati.
3. Analisi Teorica:
   • Prova di esistenza/unicità per l'OT equo esatto.
   • Derivazione di un limite di complessità del campione per l'OT entropico penalizzato (mostrando una convergenza $O(n^{-1/2})$).
   • Derivazione di un limite di deviazione uniforme per l'approccio di apprendimento del costo, garantendo l'equità su dati non visti.
4. Validazione Empirica: Esperimenti su dati sintetici (miscele gaussiane e distribuzioni circolari) e un dataset semi-sintetico di un'app di incontri dimostrano l'efficacia degli approcci e i compromessi tra costo ed equità.

4. Risultati

• Controllo del Compromesso (Trade-off): L'approccio penalizzato interpola con successo tra l'OT vanilla (basso costo, alta iniquità) e FairSinkhorn (equità perfetta, alto costo), permettendo un controllo fine tramite il parametro di penalità $\lambda$.
• Sensibilità alla Geometria: Sui dataset sintetici, l'approccio penalizzato generalmente raggiunge un miglior compromesso costo-equità rispetto all'apprendimento del costo quando la geometria dei dati è complessa (es. distribuzioni circolari), poiché l'OT penalizzato non impone restrizioni strutturali sulla mappa di trasporto. Tuttavia, l'apprendimento del costo con reti neurali può approssimare target complessi dove i costi lineari (Mahalanobis) falliscono.
• Generalizzazione: Nell'esperimento di "riutilizzabilità", i costi appresi (sia Mahalanobis che MLP) hanno mantenuto livelli di equità sui nuovi campioni di test comparabili alle prestazioni di addestramento, superando significativamente l'OT vanilla. Il tempo di inferenza per applicare un costo appreso era significativamente inferiore rispetto alla risoluzione di un nuovo OT penalizzato per ogni nuovo batch.
• Applicazione nel Mondo Reale: Sull'app di incontri (alta dimensionalità, molteplici gruppi), i metodi hanno riprodotto il compromesso convesso costo-equità osservato nei setting sintetici, validandone l'applicabilità a scenari reali complessi.

5. Significato e Rivendicazioni

Il documento sostiene di fornire un framework rigoroso per regolatori e progettisti di mercati per imporre obiettivi di equità nei meccanismi di abbinamento. Inquadrando l'equità come vincoli di massa espliciti tra i gruppi, questo lavoro colma il divario tra l'ottimale trasporto teorico e i requisoli politici pratici (ad esempio, quote o obiettivi di diversità).

Gli autori sottolineano che il loro lavoro:

• Offre una definizione flessibile di equità che può accogliere vari obiettivi legislativi o politici (ad esempio, la "regola dei quattro quinti" o le quote di diversità).
• Fornisce garanzie teoriche sia sull'efficienza statistica dell'approccio penalizzato che sulla capacità di generalizzazione dell'approccio di apprendimento del costo.
• Evidenzia il compromesso tra efficienza (costo di trasporto) ed equità, dimostrando che, sebbene l'equità esatta sia possibile, gli approcci rilassati offrono spesso un equilibrio più pratico.

Il documento conclude notando i limiti: l'attuale framework si concentra sull'equità di gruppo e non si estende direttamente all'equità individuale. Inoltre, sebbene i metodi ottimizzino il processo di abbinamento, il lavoro riconosce che la progettazione del target di equità stesso rimane una decisione politica ed etica esterna all'algoritmo. Il lavoro futuro suggerisce di esplorare l'equità individuale, un'analisi più profonda del trade-off tra equità e bias, e la modellazione dell'impatto degli abbinamenti sugli esiti individuali a valle.