Your Recourse, My Loss? Algorithmic Recourse under Shared Constraints

Riepilogo Tecnico: "Il Tuo Ricorso, La Mia Perdita? Ricorso Algorithmico sotto Vincoli Condivisi"

Enunciato del Problema

La ricerca attuale sul ricorso algorithmico opera prevalentemente sotto un'assunzione uno-a-uno, in cui un singolo individuo cerca un'azione a costo minimo per invertire una decisione sfavorevole da un singolo modello. Tuttavia, i sistemi decisionali del mondo reale spesso coinvolgono interazioni molti-a-molti: più individui (ricorrenti) competono per risorse limitate da più decisori (fornitori).

In questi contesti, le raccomandazioni di ricorso ottimali a livello individuale non sono indipendenti. Quando i fornitori hanno vincoli di capacità (un limite al numero di individui che possono accettare), la validità di una raccomandazione di ricorso per un ricorrente dipende dalle azioni degli altri. Ottimizzare il benessere individuale in isolamento ignora queste interazioni, portando a un divario di benessere: la differenza tra l'esito teoricamente ottimale se ogni ricorrente potesse accedere al proprio fornitore preferito e l'esito realizzato sotto vincoli di capacità. La letteratura esistente ha affrontato scenari con più ricorrenti, ma tipicamente assume un singolo fornitore o ignora il problema di allocazione a livello di sistema intrinseco nella capacità di ricorso limitata.

Metodologia

Gli autori propongono un framework che modella il ricorso algorithmico multi-agente come un problema di matching bipartito pesato con capacità.

1. Formalizzazione del Problema:
   • Ricorrenti ($S$) e Fornitori ($P$): I ricorrenti sono caratterizzati da vettori di caratteristiche; i fornitori possiedono modelli decisionali (classificatori) e una capacità di matching $k_j$.
   • Costo del Ricorso: Per ogni coppia ricorrente-fornitore $(i, j)$, viene precalcolato un costo di ricorso $c_{ij}$, che rappresenta lo sforzo minimo necessario per modificare le caratteristiche del ricorrente al fine di soddisfare il modello del fornitore $j$.
   • Trasformazione dei Pesi: I costi sono convertiti in pesi degli archi $w_{ij} = e^{-\gamma \cdot c_{ij}}$, dove $\gamma$ è un parametro di scala. Questa trasformazione riflette l'Avversione Assoluta al Rischio Costante (CARA), dando priorità agli interventi a basso costo.
   • Livelli di Ottimizzazione:
     • Livello 1 (Matching di Base): Risolve un Programma Lineare Intero Misto (MILP) per massimizzare il benessere sociale ($\sum w_{ij}z_{ij}$) soggetto a vincoli individuali e di capacità. Ciò stabilisce il benessere sociale di base sotto capacità fisse.
     • Livello 2 (Ridistribuzione Ottimale della Capacità): Affronta il Divario di Benessere ottimizzando la distribuzione di una capacità totale fissa $K$ tra i fornitori. Gli autori propongono l'Algoritmo 1, un approccio greedy che assegna capacità ai fornitori in base alla frequenza del loro apparire nei matching individualmente preferiti top-$K$ (pesi più alti). Questo evita di risolvere un MILP completo per l'allocazione della capacità, offrendo una soluzione diretta che recupera il benessere sociale ottimale.
     • Livello 3 (Ottimizzazione Consapevole dei Costi): Introduce una penalità per la deviazione dalla configurazione di capacità iniziale ($\hat{k}_j$). La funzione obiettivo bilancia la massimizzazione del benessere sociale con la minimizzazione del costo degli aggiustamenti di capacità ($\sum \beta_j |\Delta k_j|$), rendendo la soluzione pratica per il dispiegamento nel mondo reale dove i cambiamenti strutturali sono costosi.
   • Estensione Avversa alla Disuguaglianza: Per affrontare l'equità, l'obiettivo utilitaristico lineare è sostituito da una funzione di benessere sociale concava ($\sum u_i^\alpha$). Questa formulazione dà priorità ai ricorrenti con utilità più basse (costi di ricorso più alti), scambiando l'efficienza aggregata per l'equità distributiva. Viene definita una Metrica di Equità ($E$) come l'utilità minima raggiunta da qualsiasi ricorrente con successo nel matching.

Contributi Chiave

• Framework Molti-a-Molti: Il documento estende il ricorso algorithmico dalle raccomandazioni individuali isolate a un design a livello di sistema che coinvolge più ricorrenti e più fornitori con vincoli di capacità.
• Quantificazione del Divario di Benessere: Definisce e quantifica formalmente la perdita di efficienza (divario di benessere) che sorge quando le raccomandazioni ottimali a livello individuale sono non fattibili a livello di sistema a causa dei vincoli di capacità.
• Ottimizzazione a Tre Livelli:
  1. Una formulazione di base di matching con capacità.
  2. Un algoritmo efficiente (Algoritmo 1) per ridistribuire in modo ottimale la capacità totale fissa al fine di minimizzare il divario di benessere.
  3. Un'ottimizzazione consapevole dei costi che bilancia i guadagni di benessere con i costi operativi della modifica delle capacità dei fornitori.
• Formulazione Avversa alla Disuguaglianza: L'introduzione di un obiettivo di benessere concavo per dare priorità esplicitamente ai ricorrenti svantaggiati, dimostrando che significativi guadagni di equità possono essere ottenuti con perdite marginali di efficienza.

Risultati Sperimentali

Il framework è stato validato su dataset sintetici (Two-Moon) e reali (Credit, COMPAS) con numeri variabili di ricorrenti e fornitori.

• Raggiungimento del Benessere: Sotto distribuzioni di capacità fisse e arbitrarie, il sistema ha raggiunto solo l'83–93% del benessere individuale teorico.
• Impatto della Ridistribuzione: Applicando la ridistribuzione ottimale della capacità (Livello 2), il benessere sociale è stato ripristinato al 100% del limite superiore del benessere individuale, dimostrando che il divario di benessere è causato principalmente da un'allocazione errata piuttosto che dalla scarsità di risorse.
• Trade-off Consapevoli dei Costi: L'ottimizzazione consapevole dei costi (Livello 3) ha raggiunto un benessere quasi ottimale (93–99% dell'ottimo) richiedendo solo piccoli aggiustamenti alla configurazione di capacità iniziale, dimostrando la fattibilità pratica.
• Trade-off Equità-Efficienza: Negli esperimenti avversi alla disuguaglianza, riducendo il parametro $\alpha$ (aumentando l'avversione alla disuguaglianza), l'utilità minima per i ricorrenti più svantaggiati (Metrica di Equità $E$) è raddoppiata, sostenendo solo una perdita di circa il 3,4% nel benessere sociale totale.
• Sensibilità agli Iperparametri: Lo studio ha analizzato il parametro di scala $\gamma$, identificando una relazione a "forma di U" tra $\gamma$ e il raggiungimento del benessere. Suggerisce un intervallo operativo (il "gomito" della curva) in cui le differenze di costo sono significative senza rendere indistinguibili le alternative non ottimali.

Significato e Affermazioni

Il documento afferma di colmare il divario tra il ricorso algorithmico individuale e il design a livello di sistema. Il suo significato principale risiede nel dimostrare che:

1. Il Coordinamento a Livello di Sistema è Essenziale: Le raccomandazioni ottimali a livello individuale sono insufficienti in ambienti con risorse limitate; è necessaria un'allocazione coordinata per raggiungere un benessere sociale quasi ottimale.
2. L'Efficienza è Raggiungibile con Minimi Cambiamenti: Il divario di benessere può essere chiuso quasi interamente ridistribuendo in modo ottimale le risorse esistenti, piuttosto che richiedendo aumenti massicci della capacità totale.
3. Il Ricorso è una Scelta di Design: L'allocazione del ricorso non è meramente un problema di ottimizzazione tecnica, ma una decisione di design di sistema carica di valori. Il framework fornisce un percorso trattabile per bilanciare l'efficienza aggregata con l'equità distributiva, permettendo agli stakeholder di scegliere esplicitamente come dare priorità agli individui più svantaggiati quando le risorse sono scarse.

Gli autori concludono che il loro lavoro fornisce una base per progettare sistemi di ricorso che non siano solo attuabili per gli individui, ma anche efficienti ed equi a livello di popolazione.