مجموعة سميث

مجموعة شوارتز تُعادل مجموعة سميث، باستثناء أنها تتجاهل الأصوات المتعادلة. وبصورة رسمية، فإن مجموعة شوارتز هي المجموعة التي يكون لأي مرشح داخلها مسار فوز مباشر على أي مرشح يهزمه.

يمكن إنشاء مجموعة سميث من مجموعة شوارتز عن طريق إضافة نوعين من المرشحين بشكل متكرر حتى لا يتبقى أي مرشحين من هذا النوع خارج المجموعة:

• المرشحون الذين تربطهم علاقة تعادل ثنائي مع مرشحين آخرين في المجموعة،
• المرشحون الذين يهزمون مرشحًا في المجموعة.

لاحظ أن المرشحين من النوع الثاني لا يمكن أن يوجدوا إلا بعد إضافة المرشحين من النوع الأول.

النظرية: المجموعات المهيمنة متداخلة ؛ أي أنه من بين أي مجموعتين مهيمنتين في الانتخابات، تكون إحداهما مجموعة جزئية من الأخرى.

البرهان: لنفترض، على العكس، وجود مجموعتين مهيمنتين، D و E ، لا تُعدّ أيٌّ منهما مجموعة جزئية من الأخرى. عندئذٍ، يجب أن يوجد مرشحان d ∈ D و e ∈ E بحيث يكون d ∉ E و e ∉ D. ولكن بحسب الفرضية، فإن d يهزم كل مرشح ليس في D (بما في ذلك e )، بينمايهزم e كل مرشح ليس في E (بما في ذلك d )، وهذا تناقض.

النتيجة: يترتب على ذلك أن مجموعة سميث هي أصغر مجموعة مهيمنة غير فارغة، وأنها محددة جيدًا.

نظرية: إذا كانت D مجموعة مهيمنة، فإنه يوجد حد أدنى θ _D بحيث تكون عناصر D هي تحديدًا المرشحين الذين تبلغ درجات كوبلاند الخاصة بهم θ _D على الأقل. (درجة كوبلاند للمرشح هي عدد المرشحين الآخرين الذين يتفوق عليهم بالإضافة إلى نصف عدد المرشحين الآخرين الذين يتعادل معهم).

البرهان: اختر d كعنصر من D بأقل قيمة لكوبلاند، وحدد هذه القيمة بـ θD _. الآن، لنفترض أن مرشحًا ما e ∉ D لديه قيمة كوبلاند لا تقل عن θD _. بما أن d ينتمي إلى D و e لا ينتمي إليه، فإنه يترتب على ذلك أن d يتفوق على e ؛ ولكيتكون قيمة كوبلاند لـ e مساوية على الأقل لقيمة d ، يجب أن يكون هناك مرشح ثالث f يحصل e على قيمة أفضلمنه مقارنةً بـ d . إذا كان f ∈ D ، فلدينا عنصر من D لا يتفوق على e ، وإذا كان f ∉ D، فلدينا مرشح خارج D لا يتفوق عليه d ، مما يؤدي إلى تناقض في كلتا الحالتين.

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

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

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

الطرق التي لا تستوفي معيار كوندورسيه لا تستوفي أيضاً معيار سميث. مع ذلك، قد لا تستوفي بعض طرق كوندورسيه (مثل طريقة مينيمكس ) معيار سميث.

يمكن شرح الخوارزمية بالتفصيل من خلال مثال. لنفترض أن مصفوفة النتائج هي كما يلي:

في هذا الجدول الرئيسي ، تكون القيمة 1 إذا فضّل عددٌ أكبر من الناخبين المرشح الأول على الثاني مقارنةً بمن فضّلوا الثاني على الأول؛ و0 إذا كان العكس صحيحًا؛ و 1 / 2 في حالة التعادل . أما العمود الأخير فيُظهر درجة كوبلاند للمرشح الأول.

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

ننظر إلى أعلى درجة (5) ونُدرج المرشحين (الفائزين في مسابقة كوبلاند) الذين حصلوا على درجة لا تقل عن هذه الدرجة، أي {A,D}. ينتمي هؤلاء المرشحون بالتأكيد إلى مجموعة سميث، ويجب إضافة أي مرشحين لم يتغلبوا عليهم. للعثور على المرشحين الذين لم يتغلبوا عليهم، ننظر إلى الخلايا في الجدول أسفل المربع العلوي الأيسر 2×2 الذي يحتوي على {A,D} (يظهر هذا المربع بحدود متقطعة): الخلايا المعنية مُظللة باللون الأصفر في الجدول. نحتاج إلى إيجاد أقل قيمة غير صفرية (موضعيًا) بين هذه الخلايا، وهي الخلية الموجودة في الصف G. يجب إضافة جميع المرشحين حتى هذا الصف، وأي صفوف أدنى منها بنفس الدرجة، إلى المجموعة، التي تتوسع إلى {A,D,G}.

الآن، ننظر إلى أي خلايا جديدة يجب أخذها في الاعتبار، وهي تلك الموجودة أسفل المربع العلوي الأيسر الذي يحتوي على {A,D,G}، باستثناء تلك الموجودة في العمودين الأولين اللذين سبق أن أخذناهما في الحسبان. الخلايا التي تحتاج إلى اهتمام مُظللة باللون الأزرق الفاتح. وكما في السابق، نحدد أدنى قيمة غير صفرية بين الخلايا الجديدة، ونضيف جميع الصفوف التي تليها، وجميع الصفوف التي لها نفس القيمة، إلى المجموعة الموسعة، التي تضم الآن {A,D,G,C}.

نكرر العملية للخلايا الجديدة أسفل الأعضاء الأربعة المعروف انتمائهم إلى مجموعة سميث. هذه الخلايا مظللة باللون الوردي، وتتيح لنا إيجاد أي مرشحين لم يستبعدهم أي من {A,D,G,C}. مرة أخرى، يوجد مرشح واحد فقط، وهو F، نضيفه إلى المجموعة.

الخلايا التي تدخل في الاعتبار مظللة باللون الأخضر الفاتح، وبما أن جميع قيمها تساوي صفرًا، فلا حاجة لإضافة أي مرشحين جدد إلى المجموعة، التي تُحدد بالتالي على أنها {A,D,G,C,F}. وبملاحظة أن جميع القيم في المربع الأسود تساوي صفرًا، نتأكد من أن جميع المرشحين الموجودين أعلاه يتفوقون على جميع المرشحين الموجودين داخله.

توضح دالة C التالية الخوارزمية من خلال إرجاع عدد عناصر مجموعة سميث لمصفوفة نتائج مضاعفة r ومصفوفة s لدرجات كوبلاند المضاعفة. يوجد n مرشحًا؛ r _{_ij} تساوي 2 إذا كان عدد الناخبين الذين يفضلون المرشح i على j أكبر من عدد الذين يفضلون j على i ، و1 إذا تساوى العددان، و0 إذا كان عدد الناخبين الذين يفضلون j على i أكبر من عدد الذين يفضلون i على j  ؛ s _{_i} هي مجموع r _{_ij} على j . يُفترض أن المرشحين مُرتبون تنازليًا حسب درجة كوبلاند.  

دالة smithset ( int ** r , int * s , int n ) { int row , col , lhs , rhs ; for ( rhs = 1 , lhs = 0 ; lhs < rhs ; lhs = rhs , rhs = row + 1 ) { for (; rhs < n && s [ rhs ] == s [ rhs - 1 ]; rhs ++ ); /* هذا السطر اختياري */ for ( col = rhs , row = n ; col == rhs && row >= rhs ; row-- ) for ( col = lhs ; col < rhs && r [ row - 1 ][ col ] == 0 ; col ++ ) ; } return lhs ; }