ملخص تقني: عمليات تدقيق تحديد المخاطر دون الخطية من خلال الاختيار المباشر للبطاقات والبيانات الإحصائية للبطاقات

1. بيان المشكلة

تعد عمليات تدقيق تحديد المخاطر (RLAs) إجراءات ما بعد الانتخابات مصممة لتوفير ضمانات إحصائية صارمة بأن اكتشاف نتيجة انتخابية غير صحيحة يتم باحتمالية لا تتجاوز حد المخاطر المحدد مسبقاً ($\alpha$). وبينما توفر عمليات تدقيق تحديد المخاطر الحالية ضمانات أمنية قوية، إلا أنها تواجه عقبتين حرجتين تحدان من كفاءتها وقابليتها للتطبيق عبر مختلف بنيات الانتخابات:

1. عقبة بيان البطاقات (The Ballot Manifest Bottleneck): تتطلب عمليات تدقيق تحديد المخاطر التقليدية "بياناً للبطاقات" (ballot manifest)—وهو محاسبة دقيقة ومستقلة برمجياً لحجم كل دفعة من البطاقات. وبينما يسهل الحصول على تقديرات تقريبية (مثل الوزن)، تتطلب عمليات تدقيق تحديد المخاطر دقة عالية (حيث تكون الأخطاء $\delta \ll \mu$، حيث $\mu$ هو هامش الانتخابات). ويتطلب تحقيق هذه الدقة عادةً عدّاً يدوياً لكل بطاقة لإنشاء البيان. وتتوسع هذه العملية خطياً مع العدد الإجمالي للبطاقات ($O(N)$)، مما يهيمن غالباً على إجمالي وقت التدقيق ويبطل المكاسب في الكفاءة الناتجة عن أخذ العينات الإحصائية.

2. عقبة الفهرسة في مقارنة البطاقات (The Indexing Bottleneck in Ballot Comparison): إن أكثر طرق تدقيق تحديد المخاطر كفاءة في أخذ العينات هي "مقارنة البطاقات"، والتي تطابق سجل تصويت (CVR) تم اختياره عشوائياً ببطاقته الفيزيائية. ومع ذلك، يتطلب هذا الأمر تحديد موقع بطاقة فيزيائية معينة بكفاءة بناءً على معرف (identifier). وفي بنيات الانتخابات الحديثة التي تستخدم أجهزة تجميع الأصوات المواجهة للناخبين، يتم تعمد عشوائية ترتيب البطاقات للحفاظ على خصوصية الناخب، مما يكسر الرابط بين ترتيب سجلات التصويت (CVRs) والترتيب الفيزيائي للبطاقات. وبالتالي، فإن تحديد موقع بطاقة معينة يتطلب بحثاً خطياً عبر الدفعة (وهو أمر مكلف) أو إعادة التبويب (وهو أمر مكلف أيضاً)، مما يجبر الولايات القضائية على العودة إلى طرق أقل كفاءة مثل "استطلاع البطاقات" (ballot polling) أو "مقارنة الدفعات" (batch comparison).

2. المنهجية

يقترح المؤلفون تقنيتين مبتكرتين لمعالجة هاتين العقبتين، مما يتيح كفاءة تدقيق دون الخطية عبر نطاق أوسع من تكوينات الانتخابات.

أ. اختبار الدقة الإحصائية لبيانات البطاقات

بدلاً من اشتراط عدّ يدوي كامل لإنشاء بيان، يقترح المؤلفون آلية "تعزيز" (bootstrapping) إحصائية.

• البيان التقريبي (Coarse Manifest): يبدأ المدققون ببيان "تقريبي" يتم الحصول عليه عبر طرق ضخمة منخفضة الجهد (مثل الوزن)، والذي يوفر أحجام دفعات دقيقة ضمن عامل كبير $\Delta$ (على سبيل المثال 10%).
• التحقق الإحصائي: يستخدم المدقق البيان التقريبي لأخذ عينات من الدفعات باحتمالية تتناسب مع أحجامها المبلغ عنها (المجدولة). ولكل دفعة يتم اختيارها، يقوم المدقق بإجراء عدّ يدوي دقيق للتحقق من الحجم الحقيقي.
• الاعتماد (Certification): يحدد اختبار إحصائي ما إذا كانت الأحجام المجدولة قريبة بما يكفي من الأحجام الحقيقية لغالبية عدد البطاقات. إذا اجتاز الاختبار، يتم "ترقية" البيان التقريبي إلى بيان عالي الدقة ومضمون إحصائياً دون الحاجة لعدّ كل بطاقة. وهذا يقلل تكلفة إنشاء البيان من $O(N)$ إلى دالة دون خطية لـ $N$.

ب. الاختيار المباشر للبطاقات (Direct Ballot Selection - DBS)

بالنسبة لبنيات الانتخابات التي تفتقر فيها البطاقات إلى معرفات مرتبة (مما يمنع مقارنة البطاقات القياسية)، يقترح المؤلفون "الاختيار المباشعي للبطاقات".

• الإجراء المعكوس: على عكس عمليات مقارنة البطاقات القياسية (التي تختار سجل تصويت وتبحث عن البطاقة)، يقوم الاختيار المباشر للبطاقات باختيار بطاقة فيزيائية عشوائياً من دفعة ما، ويقرأ المعرف المطبوع عليها، ثم يقارنها بسجل التصويت المقابل لها.
• تحدي اكتشاف التكرار: هذا الانعكاس يستحدث خطراً جديداً: يمكن للمهاجم التلاعب بجدول سجلات التصويت (CVR) عبر تضمين معرفات لا تقابل أي بطاقة فيزيائية (أو تكرار المعرفات)، وبالتالي التهرب من الاكتشاف.
• الحل الإحصائي: يقدم المؤلفون اختباراً إحصائياً جديداً لتفرد المعرفات. ومن خلال أخذ عينات من البطاقات والتحقق من وجود معرفات مكررة أو مفقودة، يمكن للتدقيق تحديد "معدل تعدد المعرفات الزائد". إذا كانت التكرارات نادرة بما يكفي، فإن التدقيق يحافظ على حد المخاطر الخاص به.
• التعقيد: تعقيد العينة في DBS هو $O\left(\frac{\log(1/\alpha)}{\mu}\right) + O\left(\sqrt{\frac{N \log(1/\alpha)}{\mu}}\right)$. المصطلح الثاني (اختبار التفرد) يتوسع مع $\sqrt{N}$، وهو مشتق من "مفارقة عيد الميلاد" (birthday paradox)، وهو أكثر كفاءة بكثير من البحث الخطي المطلوب في الطرق التقليدية في هذه البنيات.

3. المساهمات الرئيسية

1. التعزيز الإحصائي للبيانات (Statistical Manifest Bootstrapping): طريقة لتحويل بيان تقريبي منخفض الدقة إلى بيان عالي الدقة ومعتمد إحصائياً بجهد دون خطي. وهذا يلغي الحاجة إلى العد اليدوي الشامل لإنشاء البيان.
2. الاختيار المباشر للبطاقات (DBS): فئة جديدة من عمليات تدقيق تحديد المخاطر التي تعكس منطق المقارنة القياسي لاستيعاب أجهزة تجميع الأصوات المواجهة للناخبين ذات الترتيب العشوائي للبطاقات. وتتجنب هذه الطريقة عمليات البحث الخطي وإعادة التبويب.
3. اختبار تفرد المعرفات: اختبار إحصائي جديد مدمج في التدقيق لاكتشاف وحصر خطر تكرار أو حذف المعرفات، مما يضمن بقاء حد المخاطر قائماً حتى عند أخذ عينات من البطاقات الفيزيائية مباشرة.
4. إطار عمل موحد: يسمح دمج هذه التقنيات باستراتيجية تدقيق مرنة حيث يمكن اتخاذ القرار بشأن الطريقة الأكثر كفاءة (الاستطلاع، أو المقارنة، أو الاختيار المباشر للبطاقات) بعد الانتخابات، بناءً على الهامش الملحوظ، بدلاً من المتطلبات الأساسية لما قبل الانتخابات.

4. النتائج

قيم المؤلفون تقنياتهم باستخدام محاكاة تعتمد على بيانات الانتخابات الأمريكية (بما في ذلك ولايات مثل كاليفورنيا، وفلوريدا، وجورجيا، وكونيتيكت) وهوامش مختلفة.

• كفاءة البيان (Manifest Efficiency):
  • بالنسبة لهامش 3% في كاليفورنيا (16 مليون بطاقة)، أدى استخدام بيان دقيق إحصائياً إلى تقليل إجمالي وقت التدقيق بمقدار 400 ضعف لعمليات مقارنة البطاقات و 20 ضعفاً لعمليات استطلاع البطاقات مقارنة بإنشاء بيان يدوي كامل.
  • بالنسبة للاختيار المباشر للبطاقات، كان الانخفاض بمقدار 8 أضعاف، حيث لا تزال الطريقة تعتمد على $N$ (وإن تم تقليلها إلى $\sqrt{N}$)، بينما تعتمد المقارنة/الاستطلاع خطياً على $N$ لإنشاء البيان.
• تعقيد العينة والوقت:
  • الهوامش الصغيرة: بالنسبة لهامش 1% في كونيتيكت، قلل الاختيار المباشر للبطاقات حجم عينة البطاقات المطلوبة بنسبة 55% مقارنة بأحدث طرق الاستطلاع (Minerva/Providence).
  • الدوائر الانتخابية: بالنسبة للهوامش بين 0.5% و 1%، تفوق الاختيار المباشر للبطاقات على الاستطلاع بنسبة تزيد عن 75% في تعقيد العينة.
  • القابلية للتوسع: تسمح هذه التقنيات بتوسيع وقت التدقيق مع الهامش $\mu$ بدلاً من أن يهيمن بالوقت على التكلفة الثابتة لإنشاء البيان. على سبيل المثال، في سباق به هامش 2% في جورجيا، انخفض وقت التدقيق من 4,000 ساعة إلى 1,200 ساعة باستخدام بيان إحصائي.

5. الأهمية والادعاءات

يزعم البحث أن هذه التقنيات توفر "تقليلاً مذهلاً في تعقيد عمليات تدقيق تحديد المخاطر عبر مجموعة واسعة من تكوينات الانتخابات والهوامش".

• الكفاءة دون الخطية: تكمن الأهمية الأساسية في تحقيق كفاءة دون خطية في إجمالي جهد التدقيق. ومن خلال فصل الحاجة إلى بيان مثالي عن الحاجة إلى عد يدوي كامل، وتمكين عمليات مقارنة البطاقات بكفاءة في البيئات العشوائية، يجادل المؤلفون بأن عمليات تدقيق تحديد المخاطر يمكن نشرها عملياً في الانتخابات واسعة النطاق دون تكاليف زمنية باهظة.
• الاستقلال البرمجي: تحافظ هذه الأساليب على خاصية الاستقلال البرمجي الأساسية لعمليات تدقيق تحديد المخاطر. وتعتمد الاختبارات الإحصائية لدقة البيان وتفرد المعرفات على عد البطاقات الفيزيائية والتحققات البسيطة، مما لا يتطلب الثقة في المنطق الداخلي لبرمجيات التبويب.
• القابلية للتطبيق العملي: يؤكد المؤلفون أن هذه الأساليب يمكن دمجها فوراً في أطر عمل تدقيق تحديد المخاطر الطبقية الموجودة. ويمكن للولايات القضائية اختيار الطريقة الأكثر كفاءة ديناميكياً (الاستطلاع، أو المقارنة، أو الاختيار المباشر للبطاقات) بناءً على هامش المنافسة، مما يحسن تخصيص الموارد دون التضحية بالضمانات الأمنية.

يخلص البحث إلى أنه بينما توفر البيانات الوصفية (asymptotic statements) الحد الأدنى من الفهم، فإن النتائج الرقمية الصريحة توضح أن هذه التقنيات تجعل التدقيق عالي الضمان ممكناً للولايات ذات السكان الكبيرة والهوامش الضيقة حيث كانت الطرق السابقة إما بطيئة جداً (بسبب إنشاء البيان) أو كثيفة العينات (بسبب عدم كفاءة الاستطلاع).