Experimental Design for Matching

Sintesi Tecnica: Progettazione Sperimentale per l'Matching

Definizione del Problema
I meccanismi di matching sono infrastrutture critiche nella gestione delle operazioni (operations management), spaziando dall'istruzione all'assistenza sanitaria e alle piattaforme digitali. Una sfida fondamentale sorge quando i professionisti cercano di confrontare empiricamente un nuovo algoritmo di matching (trattamento) rispetto a uno status quo (controllo) su una popolazione finita. I metodi standard di inferenza causale affrontano un ostacolo unico in questo contesto: l'interferenza da matching. A differenza delle unità sperimentali indipendenti, l'assegnazione di un'unità a un particolare match nel piano di trattamento può precludere la sua assegnazione nel piano di controllo a causa di vincoli di capacità e compatibilità. Di conseguenza, i controfattuali a livello individuale sono inosservabili e le decisioni di randomizzazione sono accoppiate tra le unità. La letteratura esistente si concentra spesso sul mitigare il bias all'interno di un meccanismo di matching fisso o assume specifici modelli comportamentali. Questo articolo affronta il vuoto relativo a come confrontare sperimentalmente due piani di matching predeterminati senza imporre modelli di outcome o comportamentali, basandosi esclusivamente su una prospettiva basata sul design (design-based).

Metodologia
Gli autori propongono l'Alternating Path Randomized Design (AP Design), un framework fondato sulla teoria dei grafi e sull'inferenza basata sul design.

1. Insieme di Disaccordo e Decomposizione:
   L'intuizione strutturale centrale è la definizione dell'insieme di disaccordo ($\Delta M_{(t,c)}$), che comprende le coppie di match presenti in esattamente uno dei due piani (trattamento o controllo). Il documento dimostra che per i matching uno-a-uno, questo insieme ammette una decomposizione unica in cammini alternati (alternating paths) e cicli disgiunti. In queste strutture, gli archi alternano tra il matching di trattamento ($M_t$) e il matching di controllo ($M_c$). A causa dei vincoli di capacità, gli archi adiacenti in un cammino o ciclo alternato non possono essere simultaneamente realizzati.

2. Schema di Randomizzazione:
   L'AP Design esegue una randomizzazione sequenziale lungo questi cammini e cicli.

   • Caso Cammino (Path): Per un cammino aperto, il primo arco viene selezionato con probabilità $p/(1+p)$. Gli archi successivi vengono selezionati con probabilità condizionata $p$ se il predecessore non è stato selezionato; altrimenti, l'arco viene saltato deterministicamente (probabilità 0).
   • Caso Ciclo (Cycle): Si applicano regole sequenziali simili, con l'ultimo arco determinato deterministicamente in base alla realizzazione del primo e del penultimo arco per garantire la fattibilità.
   • Indipendenza: La randomizzazione è eseguita indipendentemente tra diversi cammini e cicli.

3. Stima:
   Gli autori utilizzano lo stimatore di Horvitz-Thompson per stimare l'Effetto Medio del Trattamento (ATE). Essi stabiliscono l'imparzialità (unbiasedness) di questo stimatore sotto l'AP design.

4. Ottimizzazione (Framework Minimax):
   Per ottimizzare l'efficienza, gli autori analizzano la varianza peggiore dello stimatore sotto un'assunzione di potenziale outcome limitato. Formulano un problema minimax per trovare la probabilità di randomizzazione condizionale ottimale $p$.

   • Risultato Asintotico: Per cammini e cicli lunghi, la $p$ ottimale converge a $\sqrt{2} - 1 \approx 0.4142$. Questo valore è strettamente inferiore a 0.5, riflettendo un compromesso in cui la riduzione della contribuzione della varianza dell'attuale arco richiede di tenere conto dell'interferenza a valle.

5. Estensione Many-to-One:
   Il framework è esteso ai matching many-to-one (es. assegnazione di studenti alle scuole), dove i vincoli di capacità complicano la decomposizione. Gli autori costruiscono un grafo diretto ausiliario sbilanciato per rappresentare l'insieme di disaccordo. Riducono il problema della ricerca di una decomposizione fattibile a due compiti di teoria dei grafi:

   • Ricerca di cammini di aumento (augmenting paths) in una rete di flusso costruita per gestire gli squilibri nei gradi dei nodi.
   • Esecuzione di decomposizioni di tour di Eulero (Euler-tour decompositions) sul grafo bilanciato residuo.
     Ciò assicura che i cammini e i cicli alternati risultanti soddisfino i vincoli di capacità, permettendo all'AP design e alle garanzie di inferenza di essere applicati.

Risultati Chiave

• Imparzialità (Unbiasedness): Lo stimatore di Horvitz-Thompson sotto l'AP design è imparziale per l'ATE.
• Scalabilità della Varianza: A differenza dei design ingenui (che selezionano l'intero matching di trattamento o di controllo con probabilità 0.5), dove la varianza non svanisce all'aumentare della dimensione della popolazione $N \to \infty$, la varianza dell'estimatore AP diminuisce con un tasso di $O(1/N)$.
• Teorema del Limite Centrale (CLT): Il documento stabilisce un CLT per popolazione finita per lo stimatore. Questo risultato è non banale perché la decomposizione dell'insieme di disaccordo può presentare schemi complessi, eterogenei e potenzialmente instabili (miscele di componenti brevi e lunghi) al crescere della popolazione. La prova combina argomenti di Lindeberg-Feller con tecniche di $\alpha$-mixing e il teorema di Bolzano-Weierstrass.
• Limiti della Varianza: Gli autori derivano un limite superiore stimabile della varianza che si basa solo su quantità osservabili, consentendo la costruzione di intervalli di confidenza asintotici.
• Validazione Numerica: Utilizzando un dataset sulla forza lavoro (Revelio Labs), gli esperimenti numerici confermano che l'AP design supera significativamente il design ingenuo in termini di riduzione della varianza. La distribuzione empirica dello stimatore si allinea con la distribuzione normale standard, validando il CLT. La $p$ ottimale empirica ($\approx 0.417$) corrisponde strettamente all'ottimo teorico del caso peggiore ($\sqrt{2}-1$).

Significato e Rivendicazioni
Il documento sostiene di fornire un framework basato sul design e privo di assunzioni per testare i meccanismi di matching. La sua importanza risiede nel:

1. Affrontare l'Interferenza da Matching: Offre una soluzione rigorosa al problema specifico dell'interferenza inerente ai mercati di matching, dove le unità non sono indipendenti.
2. Innovazione Strutturale: La decomposizione unica dell'insieme di disaccordo in cammini e cicli alternati fornisce una base strutturale rigorosa per gestire l'interferenza.
3. Inferenza Robusta: Stabilendo un CLT che accoglie strutture di componenti instabili ed eterogenee, il lavoro consente un'inferenza asintotica valida in ambienti di matching complessi senza richiedere modelli di outcome.
4. Applicabilità Pratica: L'estensione ai matching many-to-one tramite strumenti di teoria dei grafi (cammini di aumento e tour di Eulero) rende la metodologia applicabile a scenari del mondo reale con vincoli di capacità, come lo scambio di organi e la scelta scolastica.

Gli autori posizionano questo lavoro come una prospettiva complementare alla modellazione strutturale, offrendo un terreno di test empirico diretto per nuovi algoritmi di matching rispetto agli status quo nella gestione delle operazioni e nella progettazione di piattaforme.