Resumo Técnico: Auditorias de Limite de Risco Sublineares a partir da Seleção Direta de Urnas e Manifestos Estatísticos de Urnas

1. Declaração do Problema

Auditorias de Limite de Risco (RLAs) são procedimentos pós-eleitorais projetados para fornecer garantias estatísticas rigorosas de que um resultado eleitoral incorreto será detectado com uma probabilidade não superior a um limite de risco pré-especificado ($\alpha$). Embora as RLAs existentes ofereçam fortes garantias de segurança, elas enfrentam dois gargalos críticos que limitam sua eficiência e aplicabilidade em diversas arquiteturas eleitorais:

1. O Gargalo do Manifesto de Urnas: As RLAs convencionais exigem um "manifesto de urnas" — um registro preciso e independente de software do tamanho de cada lote físico de urnas. Embora estimativas grosseiras (por exemplo, via pesagem) sejam fáceis de obter, as RLAs exigem alta precisão (erros $\delta \ll \mu$, onde $\mu$ é a margem da eleição). Alcançar essa precisão normalmente requer uma contagem manual de cada urna para criar o manifesto. Esse processo escala linearmente com o número total de urnas ($O(N)$), frequentemente dominando o tempo total de auditoria e anulando os ganhos de eficiência da amostragem estatística.
2. O Gargalo de Indexação na Comparação de Urnas: O método RLA mais eficiente em termos de amostra é a "comparação de urnas", que associa um Registro de Voto Emitido (CVR) selecionado aleatoriamente à sua urna física. No entanto, isso exige localizar eficientemente uma urna física específica com base em um identificador. Em arquiteturas eleitorais modernas que utilizam tabuladores voltados para o eleitor, as urnas são intencionalmente randomizadas para preservar a privacidade do eleitor, quebrando o vínculo entre a ordem dos CVRs e a ordem física das urnas. Localizar uma urna específica exige então uma busca linear pelo lote (custoso) ou re-tabulação (custosa), forçando as jurisdições a recorrer a métodos menos eficientes, como "pesquisa de urnas" ou "comparação de lotes".

2. Metodologia

Os autores propõem duas técnicas inovadoras para abordar esses gargalos, permitindo eficiência de auditoria sublinear em um espectro mais amplo de configurações eleitorais.

A. Teste de Precisão Estatística para Manifestos de Urnas

Em vez de exigir uma contagem manual completa para estabelecer um manifesto, os autores propõem um mecanismo estatístico de "inicialização" (bootstrapping).

• Manifesto Grosseiro: Os auditores começam com um "manifesto grosseiro" obtido por métodos de grande volume de baixo esforço (por exemplo, pesagem), que fornece tamanhos de lote precisos dentro de um grande fator $\Delta$ (por exemplo, 10%).
• Verificação Estatística: O auditor utiliza o manifesto grosseiro para amostrar lotes com probabilidade proporcional aos seus tamanhos reportados (tabulados). Para cada lote amostrado, o auditor realiza uma contagem manual precisa para verificar o tamanho real.
• Certificação: Um teste estatístico determina se os tamanhos tabulados estão suficientemente próximos dos tamanhos reais para a vasta maioria da população de urnas. Se o teste passar, o manifesto grosseiro é "atualizado" para um manifesto de alta precisão com garantia estatística, sem contar cada urna. Isso reduz o custo de criação do manifesto de $O(N)$ para uma função sublinear de $N$.

B. Seleção Direta de Urnas (DBS)

Para arquiteturas eleitorais onde as urnas carecem de identificadores em ordem (impedindo a comparação padrão de urnas), os autores propõem a "Seleção Direta de Urnas".

• Procedimento Reverso: Diferentemente das auditorias de comparação padrão (que escolhem um CVR e encontram a urna), a DBS escolhe uma urna física uniformemente ao acaso de um lote, lê seu identificador impresso e compara-o com o CVR correspondente.
• Desafio de Detecção de Duplicatas: Essa inversão introduz um novo risco: um adversário poderia manipular a tabela de CVRs incluindo identificadores que não correspondem a nenhuma urna física (ou duplicando identificadores), evadindo assim a detecção.
• Solução Estatística: Os autores introduzem um novo teste estatístico para unicidade de identificadores. Ao amostrar urnas e verificar identificadores duplicados ou ausentes, a auditoria pode limitar a "taxa de multiplicidade excessiva de identificadores". Se as duplicatas forem suficientemente raras, a auditoria mantém seu limite de risco.
• Complexidade: A complexidade de amostra da DBS é assintoticamente $O\left(\frac{\log(1/\alpha)}{\mu}\right) + O\left(\sqrt{\frac{N \log(1/\alpha)}{\mu}}\right)$. O segundo termo (teste de unicidade) escala com $\sqrt{N}$, derivado do "paradoxo do aniversário", o que é significativamente mais eficiente do que a busca linear exigida pelos métodos tradicionais nessas arquiteturas.

3. Contribuições Principais

1. Inicialização Estatística de Manifestos: Um método para transformar um manifesto grosseiro de baixa precisão em um manifesto de alta precisão, certificado estatisticamente, com esforço sublinear. Isso elimina a necessidade de contagem manual exaustiva para estabelecer o manifesto.
2. Seleção Direta de Urnas (DBS): Uma nova classe de RLAs que inverte a lógica padrão de comparação para acomodar tabuladores voltados para o eleitor com ordens de urnas randomizadas. Este método evita buscas lineares e re-tabulação.
3. Teste de Identificadores Duplicados: Um teste estatístico inovador integrado à auditoria para detectar e limitar o risco de duplicação ou omissão de identificadores, garantindo que o limite de risco se mantenha mesmo ao amostrar urnas físicas diretamente.
4. Estrutura Unificada: A integração dessas técnicas permite uma estratégia de auditoria flexível, onde a escolha do método (pesquisa, comparação ou DBS) pode ser feita após a eleição com base na margem observada, em vez de exigir decisões de infraestrutura pré-eleitorais.

4. Resultados

Os autores avaliaram suas técnicas usando simulações baseadas em dados eleitorais dos EUA (incluindo estados como Califórnia, Flórida, Geórgia e Connecticut) e vários tamanhos de margem.

• Eficiência do Manifesto:
  • Para uma margem de 3% na Califórnia (16 milhões de urnas), o uso de um manifesto estatisticamente preciso reduziu o tempo total de auditoria por um fator de 400 para auditorias de comparação e 20 para auditorias de pesquisa, em comparação com a criação de um manifesto manual completo.
  • Para a Seleção Direta de Urnas, a redução foi de um fator de 8, pois o método ainda depende de $N$ (embora reduzido a $\sqrt{N}$) para o teste de unicidade, enquanto comparação/pesquisa dependem linearmente de $N$ para a criação do manifesto.
• Complexidade de Amostra e Tempo:
  • Margens Pequenas: Para uma margem de 1% em Connecticut, a Seleção Direta de Urnas reduziu o tamanho da amostra de urnas necessária em 55% em comparação com os métodos de pesquisa de última geração (Minerva/Providence).
  • Distritos Congressionais: Para margens entre 0,5% e 1%, a DBS superou a pesquisa em mais de 75% na complexidade de amostra.
  • Escalabilidade: As técnicas permitem que o tempo de auditoria escale com a margem $\mu$, em vez de ser dominado pelo custo fixo da criação do manifesto. Por exemplo, em uma corrida com margem de 2% na Geórgia, o tempo de auditoria caiu de 4.000 horas para 1.200 horas ao usar um manifesto estatístico.

5. Significado e Alegações

O artigo afirma que essas técnicas proporcionam uma "redução notável na complexidade das RLAs em uma ampla gama de configurações e margens eleitorais".

• Eficiência Sublinear: O significado principal é alcançar eficiência sublinear no esforço total de auditoria. Ao desacoplar a necessidade de um manifesto perfeito da necessidade de uma contagem manual completa e ao permitir auditorias de comparação eficientes em ambientes randomizados, os autores argumentam que as RLAs podem ser implementadas na prática em eleições de grande escala sem custos de tempo proibitivos.
• Independência de Software: Os métodos mantêm a propriedade central de independência de software das RLAs. Os testes estatísticos para precisão do manifesto e unicidade de identificadores dependem de contagens físicas de urnas e verificações simples, não exigindo confiança na lógica interna do software de tabulação.
• Aplicabilidade Prática: Os autores enfatizam que esses métodos podem ser imediatamente incorporados às estruturas de RLA estratificadas existentes. As jurisdições podem escolher dinamicamente o método mais eficiente (pesquisa, comparação ou DBS) com base na margem específica da disputa, otimizando a alocação de recursos sem sacrificar as garantias de segurança.

O artigo conclui que, embora declarações assintóticas forneçam intuição, os resultados numéricos explícitos demonstram que essas técnicas tornam a auditoria de alta garantia viável para jurisdições de grande população e margens apertadas, onde os métodos anteriores eram ou muito lentos (devido à criação do manifesto) ou muito intensivos em amostragem (devido a ineficiências na pesquisa).