قابلية الجمع الدفعي

في علم الانتخابات ، تُعتبر طريقة التصويت قابلةً للجمع إذا كان من الممكن حصر نتائج الانتخابات محليًا على مستوى كل دائرة انتخابية ، ثم حساب النتائج بجمع جميع الأصوات. وبشكل أدق، يقيس تعقيد التجميع أو الجمع لنظام التصويت صعوبة عدّ الأصوات في كل دائرة انتخابية على حدة ، وهو يساوي أقل عدد من البتات اللازمة لتلخيص جميع الأصوات. ^{[ 1 ]} تُسمى طريقة التصويت قابلةً للجمع إذا كان عدد البتات ينمو كدالة متعددة الحدود لعدد المرشحين.

في كثير من الأحيان، يتعين على مجموعة ما قبول قرار، ولكن لا يمكن جمع جميع الأصوات في مكان واحد. في مثل هذه الحالة، نحتاج إلى جمع أصوات الناخبين الحاضرين وتلخيصها بحيث نتمكن، عند وصول الأصوات الأخرى، من تحديد الفائز. يُعرف تعقيد تجميع قاعدة التصويت بأنه أقل عدد من البتات اللازمة لهذا التلخيص.

تتمثل إحدى المزايا الرئيسية لانخفاض تعقيد عملية تجميع البيانات في تسهيل التحقق من نتائج التصويت. إذ يسمح هذا التعقيد بتلخيص النتائج في كل مركز اقتراع على حدة، وهو ما يسهل التحقق منه من خلال قيام ممثلين عن كل حزب بفرز الأصوات في كل مركز. بعد ذلك، يمكن لأي ناخب التحقق من النتيجة النهائية بجمع نتائج مراكز الاقتراع الألف. هذه الإمكانية للتحقق مهمة لضمان ثقة الجمهور وقبوله للنتائج. ^{[ 1 ]} ويمكن لمراجعي الانتخابات المستقلين استخدام المعلومات المنشورة علنًا من كل دائرة انتخابية لتحديد أي دليل على تزوير الانتخابات باستخدام الأساليب الإحصائية.

يُعد تعقيد التجميع مفيدًا أيضًا من الناحية الخوارزمية لحساب الفائز بالاستقراء العكسي في ألعاب التصويت ستاكلبرغ . ^{[ 2 ]}

لنفترض أن r هي قاعدة تصويت : دالة تأخذ كمدخل قائمة من n ورقة اقتراع مرتبة ، تمثل تفضيلات n ناخبًا، وتعيد نتيجة. يوجد عدد k < n من الناخبين الذين تُعرف أصواتهم . دالة التجميع هي دالة f تأخذ كمدخل قائمة من k ورقة اقتراع مرتبة وتعيد مخرجًا بحيث، عند إعطاء أي عدد u  := n - k من أوراق الاقتراع المرتبة الإضافية، يمكن حساب مخرج r على مجموعة أوراق الاقتراع بأكملها بدقة.

تُعرَّف تعقيدية تجميع القاعدة r بأنها أسوأ حالة لعدد البتات في مخرجات دالة التجميع الأكثر كفاءة f . ^{[ 1 ]} عادةً ما يكون هذا العدد دالةً لـ n (عدد الناخبين)، و k (عدد الأصوات المعروفة)، و c (عدد المرشحين). مع ذلك، سنركز على c فقط للتبسيط، لأننا عادةً ما نهتم بالحالة التي يكون فيها عدد الأصوات المجهولة كبيرًا جدًا.

عدد أوراق الاقتراع الممكنة لأي قاعدة تصويت تفضيلي هو${\displaystyle \Theta (c!)}$مما يوفر حدًا أعلى للتعقيد. ومع ذلك، فإن معظم القواعد لها تعقيد تجميع أقل بكثير. ^{[ 1 ]}

تدرس كاريا ولانغ تعقيد تجميع العديد من قواعد التصويت متعددة الفائزين ، سواء باستخدام بطاقات الاقتراع المصنفة أو بطاقات الاقتراع بالموافقة . على سبيل المثال:

• بالنسبة للتصويت الفردي غير القابل للتحويل ، يكمن التعقيد في${\displaystyle \Theta (c)}$.
• بالنسبة لبوردا، يكمن التعقيد في${\displaystyle \Theta (c\log {kc})}$[ ^{5 ]​}

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

• نظام التصويت
• تعقيد المساحة