Fundamental Limits and Optimal Methods for Sharp Analytical Causal Bounds in Instrumental Variable Models

1. Problema e Contesto

Il paper affronta il problema della identificazione parziale degli effetti causali nei modelli a variabile strumentale (IV), in particolare quando l'identificazione puntuale non è possibile a causa di assunzioni strutturali deboli (come l'assenza di monotonia). L'obiettivo è derivare limiti analitici acuti (sharp bounds) per l'Effetto Medio del Trattamento (ATE) e le implicazioni testabili (inequazioni IV) del modello.

Esistono due approcci principali nella letteratura esistente:

1. Approcci basati sull'ottimizzazione (es. framework di Balke-Pearl): Garantiscono limiti acuti ma richiedono la risoluzione di programmi lineari su spazi di distribuzione di dati completi, con complessità computazionale che cresce rapidamente (spesso esponenzialmente) con il numero di valori delle variabili.
2. Approcci euristici/algebrici: Derivano limiti usando leggi probabilistiche e disuguaglianze generiche (es. Fréchet). Sebbene computazionalmente più efficienti, non è garantito che siano acuti. Alcuni lavori recenti hanno ipotizzato che fosse possibile ottenere limiti acuti analitici con complessità polinomiale tramite questi metodi.

Il paper sfida questa ipotesi, dimostrando che il vantaggio computazionale percepito è illusorio.

2. Metodologia

Gli autori formulano il problema di identificazione come un Programma Lineare (PL).

• Formulazione Primal: Lo spazio delle distribuzioni dei dati completi ($Q$) compatibili con i dati osservati ($P$) e le assunzioni del modello IV è definito da un poliedro convesso $\Gamma(p)$, descritto da equazioni lineari e vincoli di non negatività.
• Formulazione Duale: Sfruttando il teorema di dualità forte, il problema viene trasformato nel suo duale.
  • Per i limiti ATE, il problema duale massimizza/minimizza una funzione lineare su un insieme di variabili duali vincolato da $Mv \leq c$. I limiti acuti corrispondono ai vertici di questo poliedro duale.
  • Per le implicazioni testabili, il problema si riduce a verificare la fattibilità del sistema primario. Secondo il teorema dell'alternativa, ciò equivale a verificare che $p^T r \leq 0$ per tutti i raggi estremi del cono duale $K = \{r : Mr \leq 0\}$.

La chiave della metodologia risiede nell'analisi combinatoria della struttura geometrica di questi poliedri duali ($H$ per i limiti e $K$ per le implicazioni). Gli autori caratterizzano esplicitamente i vertici di $H$ e i raggi estremi di $K$ per il caso di variabili categoriche, dimostrando che il loro numero cresce esponenzialmente con la dimensione del supporto della variabile di esito ($n$).

3. Contributi Chiave

A. Limiti Fondamentali di Complessità

Il contributo teorico principale è la dimostrazione che non esiste una famiglia di espressioni lineari analitiche di dimensione polinomiale che possa fornire limiti acuti per l'ATE o un sistema completo di implicazioni testabili nel modello IV discreto.

• Per l'ATE: Se la variabile di esito $Y$ assume $n$ valori distinti, qualsiasi limite acuto superiore (o inferiore) deve essere esprimibile come il massimo (o minimo) su una collezione di termini lineari la cui cardinalità cresce esponenzialmente in $n$.
• Per le Implicazioni IV: Il numero di disuguaglianze necessarie e sufficienti per caratterizzare completamente il modello IV cresce anch'esso esponenzialmente in $n$.
  Questo dimostra che la complessità esponenziale osservata nei metodi di ottimizzazione non è un artefatto algoritmico, ma una caratteristica intrinseca del modello IV.

B. Caratterizzazione Esatta (Caso Strumento Binario)

Per il caso specifico di uno strumento binario ($\ell=2$), gli autori forniscono una caratterizzazione completa e costruttiva:

1. Limiti ATE: Identificano un insieme di "firme" ammissibili (vettori binari) che corrispondono biunivocamente ai vertici del poliedro duale. Derivano formule chiuse per i limiti acuti basate su queste firme.
2. Implicazioni Testabili: Derivano esplicitamente l'insieme completo e non ridondante di disuguaglianze IV necessarie e sufficienti. Per $n$ valori di esito, il numero di tali disuguaglianze è $2^{n+1} - 4$.

C. Algoritmi e Codice Ottimizzati

Come complemento costruttivo, gli autori hanno sviluppato un pacchetto software (disponibile in Python e R) che:

• Calcola i limiti acuti e le disuguaglianze IV con complessità temporale lineare rispetto al numero di termini necessari (ottimale, poiché deve almeno elencarli).
• Evita l'enumerazione esplicita dei vertici del poliedro primario (che è computazionalmente proibitiva) sfruttando invece le caratterizzazioni strutturali dei vertici e dei raggi estremi del duale.
• Dimostra sperimentalmente guadagni computazionali enormi rispetto a metodi esistenti (come causaloptim), rendendo calcolabili limiti acuti per dimensioni di supporto moderate ($n \ge 6$) che erano precedentemente intrattabili.

4. Risultati Principali

• Dimostrazione di Impossibilità: È stato provato che qualsiasi metodo che produca limiti analitici acuti con complessità polinomiale fallisce nel catturare tutti i casi possibili. La crescita esponenziale è inevitabile.
• Conteggio Esatto:
  • Numero di termini nei limiti ATE per strumento binario: $5 \times 4^{n-1} - 2^{n+2} + 4$.
  • Numero di disuguaglianze IV per strumento binario: $2^{n+1} - 4$.
• Validità e Acutezza: I limiti e le disuguaglianze derivati sono stati provati essere sia validi (coprono il vero valore) che acuti (il più stretto possibile dato il modello).
• Performance Computazionale: Le simulazioni mostrano che il metodo proposto è migliaia di volte più veloce dei metodi di enumerazione dei vertici standard per $n \ge 6$, calcolando l'intero insieme di limiti in millisecondi.

5. Significato e Implicazioni

Questo lavoro ha un impatto significativo sulla causalità computazionale e l'econometria:

1. Chiusura di una questione aperta: Confuta l'ipotesi che esistano metodi analitici "semplici" (polinomiali) per ottenere limiti acuti in modelli IV complessi, chiudendo la ricerca su tale direzione.
2. Standard di riferimento: Fornisce la prima caratterizzazione completa e non ridondante delle implicazioni testabili per modelli IV con esiti multi-valore, migliorando risultati precedenti (es. Bonet 2001, Kédagni & Mourifié 2020) che erano parziali o ridondanti.
3. Fattibilità Pratica: Nonostante la complessità teorica esponenziale, l'approccio algoritmico proposto rende praticabile il calcolo di limiti acuti per problemi reali di dimensioni moderate, offrendo uno strumento essenziale per la validazione di modelli causali in presenza di variabili strumentali.
4. Generalizzabilità: Sebbene i risultati espliciti siano per strumenti binari, le prove di complessità esponenziale si estendono al caso di strumenti multi-valore ($\ell > 2$), stabilendo un limite inferiore fondamentale per qualsiasi approccio futuro.

In sintesi, il paper stabilisce che la complessità combinatoria è un ostacolo fondamentale nella derivazione di limiti analitici acuti per l'IV, ma offre al contempo la soluzione algoritmica ottimale per superare questo ostacolo nella pratica.