Resumen Técnico: Auditorías de Límite de Riesgo Sublineales a partir de la Selección Directa de Boletas y Manifiestos Estadísticos de Boletas

1. Declaración del Problema

Las auditorías de límite de riesgo (RLA, por sus siglas en inglés) son procedimientos posteriores a las elecciones diseñados para ofrecer garantías estadísticas rigurosas de que un resultado electoral incorrecto será detectado con una probabilidad no mayor a un límite de riesgo preespecificado ($\alpha$). Aunque las RLA existentes ofrecen garantías de seguridad sólidas, enfrentan dos cuellos de botella críticos que limitan su eficiencia y aplicabilidad en diversas arquitecturas electorales:

1. El Cuello de Botella del Manifiesto de Boletas: Las RLA convencionales requieren un "manifiesto de boletas"—un registro preciso e independiente del software del tamaño de cada lote físico de boletas. Aunque las estimaciones aproximadas (por ejemplo, mediante pesaje) son fáciles de obtener, las RLA requieren alta precisión (errores $\delta \ll \mu$, donde $\mu$ es el margen electoral). Lograr esta precisión generalmente requiere un recuento manual de cada boleta para crear el manifiesto. Este proceso escala linealmente con el número total de boletas ($O(N)$), dominando a menudo el tiempo total de la auditoría y anulando las ganancias de eficiencia del muestreo estadístico.
2. El Cuello de Botella de Indexación en la Comparación de Boletas: El método de RLA más eficiente en términos de muestra es la "comparación de boletas", que empareja un Registro de Voto Emitido (CVR) seleccionado aleatoriamente con su boleta física. Sin embargo, esto requiere localizar eficientemente una boleta física específica basándose en un identificador. En las arquitecturas electorales modernas que utilizan tabuladores de cara al votante, las boletas se aleatorizan intencionalmente para preservar la privacidad del votante, rompiendo el vínculo entre el orden de los CVR y el orden físico de las boletas. Localizar una boleta específica requiere entonces una búsqueda lineal a través del lote (costosa) o un re-tabulado (costoso), obligando a las jurisdicciones a recurrir a métodos menos eficientes como el "sondeo de boletas" o la "comparación de lotes".

2. Metodología

Los autores proponen dos técnicas novedosas para abordar estos cuellos de botella, permitiendo una eficiencia de auditoría sublineal en un espectro más amplio de configuraciones electorales.

A. Prueba de Precisión Estadística para Manifiestos de Boletas

En lugar de requerir un recuento manual completo para establecer un manifiesto, los autores proponen un mecanismo estadístico de "arranque en caliente" (bootstrapping).

• Manifiesto Grueso: Los auditores comienzan con un "manifiesto grueso" obtenido mediante métodos de gran volumen de bajo esfuerzo (por ejemplo, pesaje), que proporciona tamaños de lote precisos dentro de un factor grande $\Delta$ (por ejemplo, 10%).
• Verificación Estadística: El auditor utiliza el manifiesto grueso para muestrear lotes con una probabilidad proporcional a sus tamaños reportados (tabulados). Para cada lote muestreado, el auditor realiza un recuento manual preciso para verificar el tamaño real.
• Certificación: Una prueba estadística determina si los tamaños tabulados están suficientemente cerca de los tamaños reales para la gran mayoría de la población de boletas. Si la prueba es aprobada, el manifiesto grueso se "actualiza" a un manifiesto de alta precisión con garantía estadística sin contar cada boleta. Esto reduce el costo de creación del manifiesto de $O(N)$ a una función sublineal de $N$.

B. Selección Directa de Boletas (DBS)

Para arquitecturas electorales donde las boletas carecen de identificadores en orden (lo que impide la comparación estándar de boletas), los autores proponen la "Selección Directa de Boletas".

• Procedimiento Inverso: A diferencia de las auditorías de comparación estándar (que eligen un CVR y encuentran la boleta), la DBS elige una boleta física uniformemente al azar de un lote, lee su identificador impreso y lo compara con el CVR correspondiente.
• Desafío de Detección de Duplicados: Esta inversión introduce un nuevo riesgo: un adversario podría manipular la tabla de CVR incluyendo identificadores que no corresponden a ninguna boleta física (o duplicando identificadores), evadiendo así la detección.
• Solución Estadística: Los autores introducen una nueva prueba estadística para la unicidad de identificadores. Al muestrear boletas y verificar duplicados o identificadores faltantes, la auditoría puede acotar la "tasa de multiplicidad de identificadores en exceso". Si los duplicados son suficientemente raros, la auditoría mantiene su límite de riesgo.
• Complejidad: La complejidad de muestra de la DBS es asintóticamente $O\left(\frac{\log(1/\alpha)}{\mu}\right) + O\left(\sqrt{\frac{N \log(1/\alpha)}{\mu}}\right)$. El segundo término (prueba de unicidad) escala con $\sqrt{N}$, derivado de la "paradoja del cumpleaños", lo cual es significativamente más eficiente que la búsqueda lineal requerida por los métodos tradicionales en estas arquitecturas.

3. Contribuciones Clave

1. Arranque en Caliente (Bootstrapping) Estadístico de Manifiestos: Un método para transformar un manifiesto grueso de baja precisión en un manifiesto de alta precisión, certificado estadísticamente, con esfuerzo sublineal. Esto elimina la necesidad de un recuento manual exhaustivo para establecer el manifiesto.
2. Selección Directa de Boletas (DBS): Una nueva clase de RLA que invierte la lógica estándar de comparación para acomodar tabuladores de cara al votante con órdenes de boletas aleatorizados. Este método evita búsquedas lineales y re-tabulados.
3. Prueba de Identificadores Duplicados: Una prueba estadística novedosa integrada en la auditoría para detectar y acotar el riesgo de duplicación u omisión de identificadores, asegurando que el límite de riesgo se mantenga incluso al muestrear boletas físicas directamente.
4. Marco Unificado: La integración de estas técnicas permite una estrategia de auditoría flexible donde la elección del método (sondeo, comparación o DBS) puede realizarse después de la elección basándose en el margen observado, en lugar de requerir decisiones de infraestructura previas a la elección.

4. Resultados

Los autores evaluaron sus técnicas utilizando simulaciones basadas en datos electorales de EE. UU. (incluyendo estados como California, Florida, Georgia y Connecticut) y diversos tamaños de margen.

• Eficiencia del Manifiesto:
  • Para un margen del 3% en California (16 millones de boletas), el uso de un manifiesto estadísticamente preciso redujo el tiempo total de auditoría en un factor de 400 para auditorías de comparación y de 20 para auditorías de sondeo en comparación con la creación de un manifiesto manual completo.
  • Para la Selección Directa de Boletas, la reducción fue un factor de 8, ya que el método aún depende de $N$ (aunque reducido a $\sqrt{N}$) para la prueba de unicidad, mientras que la comparación/sondeo dependen linealmente de $N$ para la creación del manifiesto.
• Complejidad de Muestra y Tiempo:
  • Margenes Pequeños: Para un margen del 1% en Connecticut, la Selección Directa de Boletas redujo el tamaño de muestra de boletas requerido en un 55% en comparación con los métodos de sondeo más avanzados (Minerva/Providence).
  • Distritos Congresionales: Para márgenes entre 0.5% y 1%, la DBS mejoró el sondeo en más del 75% en complejidad de muestra.
  • Escalabilidad: Las técnicas permiten que el tiempo de auditoría escale con el margen $\mu$ en lugar de estar dominado por el costo fijo de la creación del manifiesto. Por ejemplo, en una carrera con un margen del 2% en Georgia, el tiempo de auditoría disminuyó de 4,000 horas a 1,200 horas al utilizar un manifiesto estadístico.

5. Significado y Afirmaciones

El artículo afirma que estas técnicas proporcionan una "reducción notable en la complejidad de las RLA en una amplia gama de configuraciones electorales y márgenes".

• Eficiencia Sublineal: El significado principal es lograr una eficiencia sublineal en el esfuerzo total de auditoría. Al desacoplar la necesidad de un manifiesto perfecto de la necesidad de un recuento manual completo, y al permitir auditorías de comparación eficientes en entornos aleatorizados, los autores argumentan que las RLA pueden implementarse de manera práctica en elecciones a gran escala sin costos de tiempo prohibitivos.
• Independencia del Software: Los métodos mantienen la propiedad central de independencia del software de las RLA. Las pruebas estadísticas para la precisión del manifiesto y la unicidad de identificadores se basan en conteos físicos de boletas y verificaciones simples, sin requerir confianza en la lógica interna del software de tabulación.
• Aplicabilidad Práctica: Los autores enfatizan que estos métodos pueden incorporarse inmediatamente en los marcos de RLA estratificados existentes. Las jurisdicciones pueden elegir dinámicamente el método más eficiente (sondeo, comparación o DBS) basándose en el margen específico de la contienda, optimizando la asignación de recursos sin sacrificar las garantías de seguridad.

El artículo concluye que, aunque las afirmaciones asintóticas proporcionan intuición, los resultados numéricos explícitos demuestran que estas técnicas hacen viable la auditoría de alta garantía para jurisdicciones de gran población y márgenes ajustados, donde los métodos anteriores eran demasiado lentos (debido a la creación del manifiesto) o demasiado intensivos en muestras (debido a las ineficiencias del sondeo).