Résumé technique : Audits à limite de risque sous-linéaires issus de la sélection directe de bulletins et de manifestes statistiques de bulletins

1. Énoncé du problème

Les audits à limite de risque (RLA) sont des procédures post-électorales conçues pour fournir des garanties statistiques rigoureuses qu'un résultat électoral incorrect sera détecté avec une probabilité n'excédant pas une limite de risque prédéfinie ($\alpha$). Bien que les RLA existants offrent de solides garanties de sécurité, ils se heurtent à deux goulots d'étranglement critiques qui limitent leur efficacité et leur applicabilité à travers diverses architectures électorales :

1. Le goulot d'étranglement du manifeste de bulletins : Les RLA conventionnels nécessitent un « manifeste de bulletins » — un comptage précis et indépendant du logiciel de la taille de chaque lot physique de bulletins. Bien que des estimations grossières (par exemple, par pesée) soient faciles à obtenir, les RLA exigent une grande précision (erreurs $\delta \ll \mu$, où $\mu$ est la marge électorale). Atteindre cette précision nécessite généralement un comptage manuel de chaque bulletin pour créer le manifeste. Ce processus évolue linéairement avec le nombre total de bulletins ($O(N)$), dominant souvent le temps total d'audit et annulant les gains d'efficacité du sondage statistique.
2. Le goulot d'étranglement de l'indexation dans la comparaison de bulletins : La méthode RLA la plus efficace en termes d'échantillonnage est la « comparaison de bulletins », qui associe un enregistrement de vote exprimé (CVR) sélectionné aléatoirement à son bulletin physique. Cependant, cela nécessite de localiser efficacement un bulletin physique spécifique à partir d'un identifiant. Dans les architectures électorales modernes utilisant des dépouilleurs accessibles aux électeurs, les bulletins sont intentionnellement randomisés pour préserver la vie privée des électeurs, rompant ainsi le lien entre l'ordre des CVR et l'ordre physique des bulletins. Localiser un bulletin spécifique nécessite alors une recherche linéaire dans le lot (coûteuse) ou un recomptage (coûteux), contraignant les juridictions à revenir vers des méthodes moins efficaces comme le « sondage de bulletins » ou la « comparaison de lots ».

2. Méthodologie

Les auteurs proposent deux techniques novatrices pour résoudre ces goulots d'étranglement, permettant une efficacité d'audit sous-linéaire sur un spectre plus large de configurations électorales.

A. Test de précision statistique pour les manifestes de bulletins

Au lieu d'exiger un comptage manuel complet pour établir un manifeste, les auteurs proposent un mécanisme statistique de « démarrage » (bootstrapping).

• Manifeste grossier : Les auditeurs commencent par un « manifeste grossier » obtenu par des méthodes de masse à faible effort (par exemple, par pesée), fournissant des tailles de lots précises à un facteur large $\Delta$ près (par exemple, 10 %).
• Vérification statistique : L'auditeur utilise le manifeste grossier pour échantillonner des lots avec une probabilité proportionnelle à leurs tailles déclarées (tabulées). Pour chaque lot échantillonné, l'auditeur effectue un comptage manuel précis pour vérifier la taille réelle.
• Certification : Un test statistique détermine si les tailles tabulées sont suffisamment proches des tailles réelles pour la vaste majorité de la population de bulletins. Si le test réussit, le manifeste grossier est « amélioré » en un manifeste de haute précision garanti statistiquement, sans compter chaque bulletin. Cela réduit le coût de création du manifeste de $O(N)$ à une fonction sous-linéaire de $N$.

B. Sélection directe de bulletins (DBS)

Pour les architectures électorales où les bulletins manquent d'identifiants dans l'ordre (empêchant la comparaison standard de bulletins), les auteurs proposent la « Sélection directe de bulletins ».

• Procédure inversée : Contrairement aux audits de comparaison standards (qui choisissent un CVR et trouvent le bulletin), la DBS choisit un bulletin physique uniformément au hasard dans un lot, lit son identifiant imprimé et le compare au CVR correspondant.
• Défi de détection des doublons : Cette inversion introduit un nouveau risque : un adversaire pourrait manipuler le tableau des CVR en incluant des identifiants ne correspondant à aucun bulletin physique (ou en dupliquant des identifiants), échappant ainsi à la détection.
• Solution statistique : Les auteurs introduisent un nouveau test statistique pour l'unicité des identifiants. En échantillonnant des bulletins et en vérifiant la présence d'identifiants en double ou manquants, l'audit peut borner le « taux d'excès de multiplicité des identifiants ». Si les doublons sont suffisamment rares, l'audit maintient sa limite de risque.
• Complexité : La complexité d'échantillonnage de la DBS est asymptotiquement $O\left(\frac{\log(1/\alpha)}{\mu}\right) + O\left(\sqrt{\frac{N \log(1/\alpha)}{\mu}}\right)$. Le deuxième terme (test d'unicité) évolue avec $\sqrt{N}$, dérivé du « paradoxe des anniversaires », ce qui est nettement plus efficace que la recherche linéaire requise par les méthodes traditionnelles dans ces architectures.

3. Contributions clés

1. Démarrage statistique de manifeste : Une méthode pour transformer un manifeste grossier de faible précision en un manifeste de haute précision, certifié statistiquement, avec un effort sous-linéaire. Cela élimine le besoin d'un comptage manuel exhaustif pour établir le manifeste.
2. Sélection directe de bulletins (DBS) : Une nouvelle classe de RLA qui inverse la logique de comparaison standard pour s'adapter aux dépouilleurs accessibles aux électeurs avec des ordres de bulletins randomisés. Cette méthode évite les recherches linéaires et les recomptages.
3. Test d'identifiants en double : Un test statistique novateur intégré à l'audit pour détecter et borner le risque de duplication ou d'omission d'identifiants, garantissant que la limite de risque reste valide même lors de l'échantillonnage direct de bulletins physiques.
4. Cadre unifié : L'intégration de ces techniques permet une stratégie d'audit flexible où le choix de la méthode (sondage, comparaison ou DBS) peut être fait après l'élection en fonction de la marge observée, plutôt que de nécessiter des décisions d'infrastructure pré-électorales.

4. Résultats

Les auteurs ont évalué leurs techniques à l'aide de simulations basées sur des données électorales américaines (incluant des États comme la Californie, la Floride, la Géorgie et le Connecticut) et diverses tailles de marges.

• Efficacité du manifeste :
  • Pour une marge de 3 % en Californie (16 millions de bulletins), l'utilisation d'un manifeste statistiquement précis a réduit le temps total d'audit d'un facteur de 400 pour les audits de comparaison et de 20 pour les audits de sondage par rapport à la création d'un manifeste manuel complet.
  • Pour la sélection directe de bulletins, la réduction était d'un facteur de 8, car la méthode dépend toujours de $N$ (bien que réduite à $\sqrt{N}$) pour le test d'unicité, tandis que la comparaison/le sondage dépendent linéairement de $N$ pour la création du manifeste.
• Complexité d'échantillonnage et temps :
  • Petites marges : Pour une marge de 1 % au Connecticut, la sélection directe de bulletins a réduit la taille d'échantillon de bulletins requise de 55 % par rapport aux méthodes de sondage de pointe (Minerva/Providence).
  • Circonscriptions congressionnelles : Pour des marges comprises entre 0,5 % et 1 %, la DBS a surpassé le sondage de plus de 75 % en complexité d'échantillonnage.
  • Évolutivité : Les techniques permettent au temps d'audit d'évoluer avec la marge $\mu$ plutôt que d'être dominé par le coût fixe de la création du manifeste. Par exemple, dans une course à 2 % de marge en Géorgie, le temps d'audit est passé de 4 000 heures à 1 200 heures grâce à l'utilisation d'un manifeste statistique.

5. Signification et revendications

L'article affirme que ces techniques offrent une « réduction frappante de la complexité des RLA dans un large éventail de configurations et de marges électorales ».

• Efficacité sous-linéaire : La signification principale réside dans l'atteinte d'une efficacité sous-linéaire dans l'effort total d'audit. En découplant le besoin d'un manifeste parfait du besoin d'un comptage manuel complet, et en permettant des audits de comparaison efficaces dans des environnements randomisés, les auteurs soutiennent que les RLA peuvent être déployés de manière pratique dans des élections à grande échelle sans coûts temporels prohibitifs.
• Indépendance logicielle : Les méthodes maintiennent la propriété fondamentale des RLA d'indépendance logicielle. Les tests statistiques pour la précision du manifeste et l'unicité des identifiants reposent sur des comptages de bulletins physiques et des vérifications simples, ne nécessitant aucune confiance dans la logique interne du logiciel de dépouillement.
• Applicabilité pratique : Les auteurs soulignent que ces méthodes peuvent être immédiatement intégrées dans les cadres RLA stratifiés existants. Les juridictions peuvent choisir dynamiquement la méthode la plus efficace (sondage, comparaison ou DBS) en fonction de la marge spécifique du scrutin, optimisant l'allocation des ressources sans sacrifier les garanties de sécurité.

L'article conclut que, bien que les affirmations asymptotiques fournissent une intuition, les résultats numériques explicites démontrent que ces techniques rendent l'audit à haute assurance réalisable pour les juridictions à grande population et les marges serrées, où les méthodes précédentes étaient soit trop lentes (en raison de la création du manifeste), soit trop exigeantes en échantillonnage (en raison des inefficacités du sondage).