Bonsai: A class of effective methods for independent sampling of graph partitions

1. Il Problema: Campionamento Indipendente nelle Mappe Elettorali

Il contesto della ricerca riguarda la ridisegnazione dei distretti elettorali (redistricting) e l'analisi di eventuali bias nelle mappe elettorali attuate. Per valutare se una mappa è discriminatoria, si confrontano con un "insieme" (ensemble) di migliaia o milioni di mappe casuali generate da una distribuzione di probabilità ragionevole.

Le sfide principali identificate dagli autori riguardano i metodi attuali basati su Catene di Markov (come l'algoritmo ReCom):

• Mancanza di indipendenza: Le catene di Markov producono campioni correlati (autocorrelazione). Per ottenere campioni indipendenti, è necessario far girare la catena per un tempo di "mescolamento" (mixing time) molto lungo, che è spesso sconosciuto e teoricamente non garantito.
• Problemi di ergodicità: Non è sempre garantito che la catena possa raggiungere tutti gli stati possibili (ergodicità) o che lo faccia in tempi ragionevoli.
• Inefficienza computazionale: La necessità di lunghe catene per ogni campione riduce l'efficienza e richiede ensemble molto grandi per compensare la ridotta dimensione del campione effettivo (effective sample size).
• Limiti del Parallelismo: I metodi sequenziali basati su catene non si prestano bene al parallelismo massivo.

L'obiettivo è sviluppare metodi che permettano il campionamento indipendente di piani distrettuali, garantendo ergodicità, tempi di esecuzione prevedibili e la possibilità di parallelizzazione.

2. Metodologia: L'Algoritmo "Bonsai"

Gli autori propongono una nuova classe di algoritmi chiamata Bonsai, ispirata all'arte giapponese della modellazione degli alberi. A differenza dei metodi che modificano iterativamente i confini (come ReCom), Bonsai costruisce i distretti "dall'alto verso il basso" (top-down) attraverso tagli sequenziali su alberi di copertura (spanning trees).

Approccio Preliminare: "Complete Cut"

Prima di Bonsai, gli autori analizzano un approccio semplice basato sul campionamento di alberi di copertura uniformi finché non se ne trova uno "completamente tagliabile" (completely cuttable), ovvero un albero da cui è possibile rimuovere $k-1$ bordi per ottenere $k$ distretti di popolazione esattamente uguale.

• Risultato: Sebbene teoricamente possibile in tempo polinomiale per griglie specifiche, questo metodo è praticamente inefficiente: la probabilità di trovare un tale albero crolla drasticamente all'aumentare della dimensione del grafo o del numero di distretti.

L'Algoritmo Bonsai

Bonsai risolve l'inefficienza di "Complete Cut" adottando una strategia ricorsiva:

1. Campionamento dell'Albero: Si disegna un albero di copertura uniforme (o minimo) sul grafo corrente.
2. Identificazione dei Tagli Validi: Si identificano tutti i bordi dell'albero la cui rimozione divide il grafo in sottografi che rispettano i vincoli di popolazione (bilanciamento perfetto o approssimato).
3. Taglio Ricorsivo: Invece di attendere un albero perfetto, l'algoritmo esegue un taglio valido, ottenendo due sottografi.
4. Ripetizione: L'algoritmo ricorsivamente applica lo stesso processo ai sottografi risultanti, riutilizzando gli alberi di copertura generati sui pezzi (o generandone di nuovi se necessario) fino a quando ogni pezzo non corrisponde a un singolo distretto.
5. Backtracking: Per evitare che l'algoritmo rimanga intrappolato in configurazioni non risolvibili (es. un pezzo che non può essere ulteriormente diviso rispettando i vincoli), è stato introdotto un meccanismo di backtracking. Se un ramo fallisce dopo un certo numero di tentativi (parametri MaxTrees e MaxFails), l'algoritmo torna indietro, unisce i pezzi e prova un nuovo taglio.

Gestione del Bilanciamento Imperfetto ($\epsilon > 0$)

Per casi reali dove la popolazione non è perfettamente bilanciata, l'algoritmo utilizza una funzione moltiplicatrice di tolleranza $\phi(n)$ per definire quali tagli sono "validi".

• Un taglio è valido se la deviazione di popolazione dei sottografi risultanti è entro una soglia definita da $\phi(k_i) \cdot \epsilon$.
• Viene selezionato il "migliore" taglio tra quelli validi, ottimizzando il bilanciamento tra i sottografi.
• Garanzia Teorica: Se la funzione di tolleranza e il metodo di selezione sono scelti correttamente (es. $\phi(n)=n$ e selezione probabilistica), l'algoritmo garantisce che qualsiasi piano valido abbia una probabilità non nulla di essere generato, superando il problema dell'irriducibilità delle catene di Markov.

3. Contributi Chiave

1. Campionamento Indipendente: Bonsai genera piani uno alla volta in modo indipendente, eliminando la necessità di calcolare tempi di mescolamento e garantendo che la dimensione del campione effettivo sia uguale alla dimensione reale.
2. Parallelizzazione Massiva: Poiché ogni campione è indipendente, l'algoritmo può essere parallelizzato su migliaia di core senza overhead di comunicazione.
3. Descrizione Teorica della Distribuzione: Per il caso di bilanciamento perfetto ($\epsilon=0$), gli autori forniscono una descrizione esplicita della distribuzione di probabilità da cui Bonsai campiona (legata al numero di alberi di copertura sul grafo quoziente e sui singoli distretti).
4. Robustezza Teorica: Dimostrano che, a differenza delle catene di Markov dove l'ergodicità è spesso un'ipotesi non verificata, Bonsai garantisce teoricamente la possibilità di generare qualsiasi piano valido.

4. Risultati Sperimentali

Gli autori hanno confrontato Bonsai con quattro varianti dell'algoritmo ReCom (basato su alberi di copertura minimi o uniformi e diverse strategie di selezione dei distretti) su diversi dataset:

• Grafici a Griglia: Griglie $7\times7$ e $50\times50$ con vari numeri di distretti.
• Dati Reali: Grafici VTD (Voting Districts) della Pennsylvania (18 distretti congressuali) e della Carolina del Nord (99 distretti legislativi).

Risultati Principali:

• Statistiche di Compattezza: Le statistiche degli ensemble generati da Bonsai (numero di bordi tagliati, perimetri dei distretti) si collocano tra le due varianti principali di ReCom (selezione del bordo di taglio vs. selezione della coppia di distretti), tendendo ad essere più vicine alla variante di selezione della coppia di distretti.
• Distribuzione dei Voti: Nei dati reali (elezioni presidenziali 2016 in PA e governatoriali 2016 in NC), le distribuzioni della quota di voto democratico per distretto prodotte da Bonsai sono estremamente simili a quelle di tutte le varianti di ReCom.
• Efficienza: Bonsai evita i problemi di autocorrelazione, permettendo di ottenere ensemble statisticamente validi con meno campioni computazionalmente costosi rispetto alle catene di Markov.

5. Significato e Conclusioni

Il paper dimostra che l'approccio di Bonsai è un'alternativa praticabile e matematicamente trasparente ai metodi basati su Catene di Markov per l'analisi degli ensemble nel redistricting.

• Vantaggi Pratici: Offre velocità, parallelizzazione e assenza di autocorrelazione.
• Validità Statistica: I risultati empirici suggeriscono che molte statistiche a livello di ensemble (come la distribuzione dei voti) sono robuste rispetto alle differenze metodologiche tra approcci basati su alberi di copertura. Questo rafforza la fiducia nell'uso degli ensemble come strumento di verifica per le mappe elettorali.
• Impatto Giuridico e di Ricerca: Bonsai espande la cassetta degli attrezzi disponibile per ricercatori e avvocati, fornendo un metodo che non solo è computazionalmente efficiente, ma offre anche garanzie teoriche più solide sull'esplorazione dello spazio delle soluzioni rispetto ai metodi di Markov tradizionali.

In sintesi, Bonsai rappresenta un passo avanti significativo verso un campionamento indipendente, scalabile e teoricamente fondato per l'analisi della giustizia nelle mappe elettorali.