Riepilogo Tecnico: Audit a Limiti di Rischio Sublineari da Selezione Diretta delle Schede e Manifesti Statistici delle Schede

1. Enunciato del Problema

Gli audit a limiti di rischio (RLA) sono procedure post-elettorali progettate per fornire garanzie statistiche rigorose secondo cui un esito elettorale errato verrà rilevato con una probabilità non superiore a un limite di rischio predefinito ($\alpha$). Sebbene gli RLA esistenti offrano solide garanzie di sicurezza, affrontano due colli di bottiglia critici che ne limitano l'efficienza e l'applicabilità in architetture elettorali diverse:

1. Il Collo di Bottiglia del Manifesto delle Schede: Gli RLA convenzionali richiedono un "manifesto delle schede"—una contabilità accurata e indipendente dal software della dimensione di ogni lotto fisico di schede. Sebbene stime approssimative (ad esempio, tramite pesatura) siano facili da ottenere, gli RLA richiedono un'alta precisione (errori $\delta \ll \mu$, dove $\mu$ è il margine elettorale). Raggiungere tale precisione richiede tipicamente un conteggio manuale di ogni scheda per creare il manifesto. Questo processo scala linearmente con il numero totale di schede ($O(N)$), dominando spesso il tempo totale dell'audit e annullando i guadagni di efficienza del campionamento statistico.
2. Il Collo di Bottiglia dell'Indicizzazione nel Confronto delle Schede: Il metodo RLA più efficiente in termini di campione è il "confronto delle schede", che associa un Registro di Voto Emesso (CVR) selezionato casualmente alla sua scheda fisica. Tuttavia, ciò richiede di localizzare efficientemente una specifica scheda fisica basandosi su un identificatore. Nelle moderne architetture elettorali che utilizzano tabulatori a contatto con l'elettore, le schede sono intenzionalmente randomizzate per preservare la privacy dell'elettore, rompendo il legame tra l'ordine dei CVR e l'ordine fisico delle schede. Localizzare una specifica scheda richiede quindi una ricerca lineare nel lotto (costosa) o una ricalcolazione (costosa), costringendo le giurisdizioni a ricorrere a metodi meno efficienti come il "sondaggio delle schede" o il "confronto dei lotti".

2. Metodologia

Gli autori propongono due tecniche innovative per affrontare questi colli di bottiglia, consentendo un'efficienza di audit sublineare su un più ampio spettro di configurazioni elettorali.

A. Test di Accuratezza Statistica per i Manifesti delle Schede

Invece di richiedere un conteggio manuale completo per stabilire un manifesto, gli autori propongono un meccanismo statistico di "bootstrap".

• Manifesto Grezzo: Gli auditor iniziano con un "manifesto grezzo" ottenuto tramite metodi di massa a basso sforzo (ad esempio, pesatura), che fornisce dimensioni dei lotti accurate entro un grande fattore $\Delta$ (ad esempio, 10%).
• Verifica Statistica: L'auditor utilizza il manifesto grezzo per campionare i lotti con probabilità proporzionale alle loro dimensioni riportate (tabulate). Per ogni lotto campionato, l'auditor esegue un conteggio manuale preciso per verificare la dimensione reale.
• Certificazione: Un test statistico determina se le dimensioni tabulate sono sufficientemente vicine alle dimensioni reali per la stragrande maggioranza della popolazione delle schede. Se il test supera, il manifesto grezzo viene "aggiornato" a un manifesto ad alta precisione garantito statisticamente senza contare ogni scheda. Questo riduce il costo della creazione del manifesto da $O(N)$ a una funzione sublineare di $N$.

B. Selezione Diretta delle Schede (DBS)

Per le architetture elettorali in cui le schede mancano di identificatori in ordine (impedendo il confronto standard delle schede), gli autori propongono la "Selezione Diretta delle Schede".

• Procedura Invertita: A differenza degli audit di confronto standard (che scelgono un CVR e trovano la scheda), la DBS sceglie una scheda fisica uniformemente a caso da un lotto, ne legge l'identificatore impresso e la confronta con il CVR corrispondente.
• Sfida del Rilevamento dei Duplicati: Questa inversione introduce un nuovo rischio: un avversario potrebbe manipolare la tabella dei CVR includendo identificatori che non corrispondono a nessuna scheda fisica (o duplicando identificatori), eludendo così il rilevamento.
• Soluzione Statistica: Gli autori introducono un nuovo test statistico per l'univocità degli identificatori. Campionando le schede e controllando la presenza di identificatori duplicati o mancanti, l'audit può limitare il "tasso di molteplicità in eccesso degli identificatori". Se i duplicati sono sufficientemente rari, l'audit mantiene il proprio limite di rischio.
• Complessità: La complessità del campione della DBS è asintoticamente $O\left(\frac{\log(1/\alpha)}{\mu}\right) + O\left(\sqrt{\frac{N \log(1/\alpha)}{\mu}}\right)$. Il secondo termine (test di univocità) scala con $\sqrt{N}$, derivato dal "paradosso del compleanno", che è significativamente più efficiente della ricerca lineare richiesta dai metodi tradizionali in queste architetture.

3. Contributi Chiave

1. Bootstrap Statistico del Manifesto: Un metodo per trasformare un manifesto grezzo a bassa accuratezza in un manifesto ad alta accuratezza, certificato statisticamente, con sforzo sublineare. Questo elimina la necessità di un conteggio manuale esaustivo per stabilire il manifesto.
2. Selezione Diretta delle Schede (DBS): Una nuova classe di RLA che inverte la logica di confronto standard per adattarsi ai tabulatori a contatto con l'elettore con ordini di schede randomizzati. Questo metodo evita ricerche lineari e ricalcolazioni.
3. Test per Identificatori Duplicati: Un nuovo test statistico integrato nell'audit per rilevare e limitare il rischio di duplicazione o omissione degli identificatori, garantendo che il limite di rischio valga anche quando si campionano direttamente le schede fisiche.
4. Quadro Unificato: L'integrazione di queste tecniche consente una strategia di audit flessibile in cui la scelta del metodo (sondaggio, confronto o DBS) può essere effettuata dopo l'elezione in base al margine osservato, piuttosto che richiedere decisioni infrastrutturali pre-elettorali.

4. Risultati

Gli autori hanno valutato le loro tecniche utilizzando simulazioni basate su dati elettorali statunitensi (inclusi stati come California, Florida, Georgia e Connecticut) e varie dimensioni di margine.

• Efficienza del Manifesto:
  • Per un margine del 3% in California (16 milioni di schede), l'uso di un manifesto statisticamente accurato ha ridotto il tempo totale di audit di un fattore di 400 per gli audit di confronto e di 20 per gli audit di sondaggio rispetto alla creazione di un manifesto manuale completo.
  • Per la Selezione Diretta delle Schede, la riduzione è stata di un fattore di 8, poiché il metodo dipende ancora da $N$ (sebbene ridotto a $\sqrt{N}$) per il test di univocità, mentre il confronto/sondaggio dipendono linearmente da $N$ per la creazione del manifesto.
• Complessità del Campione e Tempo:
  • Margini Piccoli: Per un margine dell'1% nel Connecticut, la Selezione Diretta delle Schede ha ridotto la dimensione del campione di schede richiesto del 55% rispetto ai metodi di sondaggio all'avanguardia (Minerva/Providence).
  • Distretti Congressionali: Per margini compresi tra lo 0,5% e l'1%, la DBS ha migliorato il sondaggio di oltre il 75% in termini di complessità del campione.
  • Scalabilità: Le tecniche consentono al tempo di audit di scalare con il margine $\mu$ invece di essere dominate dal costo fisso della creazione del manifesto. Ad esempio, in una gara con margine del 2% in Georgia, il tempo di audit è sceso da 4.000 ore a 1.200 ore utilizzando un manifesto statistico.

5. Significato e Affermazioni

Il documento afferma che queste tecniche forniscono una "riduzione sorprendente della complessità degli RLA in un'ampia gamma di configurazioni elettorali e margini".

• Efficienza Sublineare: Il significato principale è il raggiungimento di un'efficienza sublineare nello sforzo totale di audit. Disaccoppiando la necessità di un manifesto perfetto dalla necessità di un conteggio manuale completo e consentendo audit di confronto efficienti in ambienti randomizzati, gli autori sostengono che gli RLA possano essere implementati praticamente in elezioni su larga scala senza costi temporali proibitivi.
• Indipendenza dal Software: I metodi mantengono la proprietà fondamentale degli RLA di indipendenza dal software. I test statistici per l'accuratezza del manifesto e l'univocità degli identificatori si basano su conteggi fisici delle schede e controlli semplici, non richiedendo fiducia nella logica interna del software di tabulazione.
• Applicabilità Pratica: Gli autori sottolineano che questi metodi possono essere immediatamente incorporati nei quadri RLA stratificati esistenti. Le giurisdizioni possono scegliere dinamicamente il metodo più efficiente (sondaggio, confronto o DBS) in base al margine specifico della competizione, ottimizzando l'allocazione delle risorse senza sacrificare le garanzie di sicurezza.

Il documento conclude che, sebbene le affermazioni asintotiche forniscano intuizioni, i risultati numerici espliciti dimostrano che queste tecniche rendono l'audit ad alta garanzia fattibile per giurisdizioni con grandi popolazioni e margini ristretti, dove i metodi precedenti erano o troppo lenti (a causa della creazione del manifesto) o troppo intensivi in termini di campioni (a causa delle inefficienze del sondaggio).