طريقة شولز

تصغير|200بك|يسار

**طريقة شولز Schulze method**  هي نظام انتخابي أنشأه ماركوس شولز في عام 1997، والذي يختار فائزًا واحدًا باستخدام الأصوات التي تُعبِّر عن التفضيلات. يمكن أيضًا استخدام هذه الطريقة لإنشاء قائمة مرتبة بالفائزين. تُعرف طريقة شولز أيضًا باسم **إسقاط شوارتز المتسلسل** (**Schwartz Sequential dropping** **SSD**)، **وإسقاط شوارتز المتسلسل المقاوم للاستنساخ** (**CSSD**)، **وطريقة Beatpath**، **والفائز في Beatpath**، **وتصويت المسار**، **والفائز في المسار**. طريقة شولز هي طريقة كوندورسيه (Condorcet method)، مما يعني أنه إذا كان هناك مرشح مفضل بأغلبية على كل مرشح آخر في المقارنات الزوجية، فإن هذا المرشح سيكون هو الفائز عند تطبيق طريقة شولز.

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

## وصف الطريقة

### الاقتراع
يسار|تصغير|181x181بك| عينة اقتراع تطلب من الناخبين ترتيب المرشحين حسب الأفضلية
المدخلات الخاصة بطريقة شولز هي نفسها المستخدمة في الأنظمة الانتخابية الأخرى ذات الفائز الواحد: يجب على كل ناخب تقديم قائمة تفضيلات مرتبة للمرشحين حيث يُسمح بالتعادل (tie)( ترتيب ضعيف صارم a strict weak order).

إحدى الطرق النموذجية التي يستخدمها الناخبون لتحديد تفضيلاتهم في بطاقة الاقتراع هي كما يلي. تُدرِج كل بطاقة اقتراع جميع المرشحين، ويقوم كل ناخب بترتيب هذه القائمة حسب تفضيله باستخدام الأرقام: يضع الناخب الرقم "1" بجانب المرشح الأكثر تفضيلاً، والرقم "2" بجوار المرشح الثاني الأكثر تفضيلاً، وهكذا. يجوز لكل ناخب اختيارياً:

* إعطاء نفس الأفضلية لأكثر من مرشح. وهذا يدل على أن هذا الناخب لا يفرق بين هؤلاء المرشحين.
* استخدم أرقامًا غير متتالية للتعبير عن التفضيلات. وهذا ليس له أي تأثير على نتيجة الانتخابات، لأن الترتيب الذي يقوم به الناخبين للمرشحين هو المهم فقط، وليس الأعداد المطلقة للتفضيلات.
* إبقاء المرشحين دون ترتيب. عندما لا يقوم الناخب بترتيب جميع المرشحين، يُفسر ذلك كما لو أن هذا الناخب (1) يفضل بشدة جميع المرشحين المصنفين على جميع المرشحين غير المصنفين، و(2) غير مبال بين جميع المرشحين غير المصنفين.

### الحساب
نفرض أن d[V,W] هو عدد الناخبين الذين يُفضلون المرشح V على المرشح W.

*المسار* (*path*) من المرشح X إلى المرشح Y هو تسلسل المرشحين C(1),\cdots,C(n) بالخصائص التالية:

# C(1) = X وC(n) = Y.
# لكل i = 1,\cdots,(n-1): d[C(i),C(i+1)] > d[C(i+1),C(i)].

بمعنى آخر، في المقارنة الزوجية، سيتفوق كل مرشح في المسار على المرشح التالي له في نفس المسار.

*يُشار إلى قوة المسار (strength) بالرمز* p، بحيث تكون قوة المسار من المرشح X للمرشح Y هي أصغر عدد من الناخبين في تسلسل المقارنات:

: لكل i = 1,\cdots,(n-1): d[C(i),C(i+1)] \ge p.

لزوج من المرشحين A وB المرتبطين بمسار واحد على الأقل، فإن *قوة المسار الأقوى* p[A,B] هي القوة القصوى للمسارات التي تربط بينها. إذا لم يكن هناك مسار من المرشح A للمرشح B على الإطلاق، فإن قوة المسار تساوي الصفر p[A,B] = 0.

يكون المُرَشَّح D *أفضل* من المرشح E إذا وفقط إذا كان p[D,E] > p[E,D].

يكون المُرَشَّح D هو *الفائز المحتمل* إذا وفقط إذا كان p[D,E] \ge p[E,D] لكل مرشح آخر E.

يمكن إثبات أن تحقق كُلا من p[X,Y] > p[Y,X] وp[Y,Z] > p[Z,Y] معا يعني أن p[X,Z] > p[Z,X]. ولذلك، فمن المضمون (1) أن التعريف أعلاه لـ " *الأفضل* " يحدد بالفعل علاقة متعدية و(2) أن هناك دائمًا مرشح واحد على الأقل D يُحقق أن p[D,E] \ge p[E,D] لكل مرشح آخر E.

## مثال
في المثال التالي، قام 45 ناخبًا بتصنيف 5 مرشحين.

يجب حساب التفضيلات الزوجية أولاً. على سبيل المثال، عند المقارنة بين  و، هناك  ناخبًا يفضلون  على ، و ناخبًا يفضلون  على  لذا فإن d[A, B] = 20 وd[B, A] = 25. المجموعة الكاملة من التفضيلات الزوجية في الشكل التالي:
[يسار|تصغير|300x300بك| [بيان موجه|رسم بياني موجه مُسمى بالتفضيلات الزوجية d[*, *].]]

تظهر خلايا d[X, Y] بخلفية خضراء فاتحة إذا كانت d[X, Y] > d[Y, X]، وإلا فسيكون لون الخلفية أحمر فاتح. لا يوجد فائز بلا منازع من خلال النظر فقط إلى الاختلافات الزوجية هنا.

الآن يجب تحديد أقوى المسارات. للمساعدة في تصور أقوى المسارات، نستخدم الرسم البياني الموجود على اليمين لتوضيح مجموعة التفضيلات الزوجية في شكل رسم بياني موجه. يُسمى السهم من العقدة التي تمثل المرشح X إلى العقدة التي تمثل المرشح Y بـ d[X, Y]. لتجنب ازدحام الرسم التخطيطي، يُرسم سهم من X إلى Y فقط عندما يكون d[X, Y] > d[Y, X] (أي خلايا الجدول ذات الخلفية الخضراء الفاتحة)، مع حذف السهم الموجود في الاتجاه المعاكس (خلايا الجدول ذات الخلفية الحمراء الفاتحة).

أحد الأمثلة على حساب أقوى مسار هو p[B,D] = 33: حيت أن أقوى مسار من B إلى D هو المسار المباشر (B,D) الذي تبلغ قوته 33. لكن عند حساب p[A,C]، فإن أقوى مسار من A إلى C ليس هو المسار المباشر (A,C) ذي القوة 26، بل أقوى مسار هو المسار غير المباشر (A,D,C) ذي القوة 28 وهي القوة الأقل بين (30،28)، حيث أن *قوة* المسار هي قوة أضعف حلقاته.

لكل زوج من المرشحين X وY، يوضح الجدول التالي أقوى مسار من المرشح X إلى المرشح Y باللون الأحمر، مع وضع خط تحت الحلقة الأضعف.

الآن يمكن تحديد مخرجات طريقة شولز. على سبيل المثال، عند المقارنة بين  و، بما أن (28 =) p[A,B] > p[B,A] (= 25)، بالنسبة لطريقة شولز فإن المرشح  *أفضل* من المرشح  مثال آخر هو (31 =) p[E,D] > p[D,E] (= 24)، لذا فإن المرشح E *أفضل* من المرشح D. وبالاستمرار على هذا النحو، تكون النتيجة أن ترتيب شولز هو E > A > C > B > D، ويفوز  وبعبارة أخرى،  يفوز لأن p[E,X] \ge p[X,E] لكل مرشح آخر X.

## تطبيق
الخطوة الصعبة الوحيدة في تنفيذ طريقة شولز هي حساب أقوى "قوى المسار". ومع ذلك، فهذه مشكلة معروفة في نظرية الرسم البياني وتسمى أحيانًا مشكلة المسار الأوسع (widest path problem). إحدى الطرق البسيطة لحساب القوى هي استخدام خوارزمية فلويد-مارشل. يوضح الكود التالي تلك الخوارزمية.
```text
# Input: d[i,j], the number of voters who prefer candidate i to candidate j.
# Output: p[i,j], the strength of the strongest path from candidate i to candidate j.

for i from 1 to C
 for j from 1 to C
 if i ≠ j then
 if d[i,j] > d[j,i] then
 p[i,j] := d[i,j]
 else
 p[i,j] := 0

for i from 1 to C
 for j from 1 to C
 if i ≠ j then
 for k from 1 to C
 if i ≠ k and j ≠ k then
 p[j,k] := max (p[j,k], min (p[j,i], p[i,k]))
```
هذه الخوارزمية فعالة ولها وقت تشغيل O(''C'' <sup>3</sup>) حيث *C* هو عدد المرشحين.

## التعادل والتطبيقات البديلة
عند السماح للمستخدمين بوجود تعادل في تفضيلاتهم، تعتمد نتيجة طريقة شولز بطبيعة الحال على كيفية تفسير هذه التعادلات في تعريف d[*,*]. هناك خياران طبيعيان هما أن d[A,B] يمثل إما عدد الناخبين الذين يُفضلون بشكل صارم A على B أي (A>B)، أو *هامش* *margin* (الناخبين مع A>B) مطروح منه (الناخبين مع B>A). ولكن بغض النظر عن كيفية تعريف الـ *d*، فإن تصنيف شولز ليس له دورات، وبافتراض أن *d* فريدة من نوعها، فإنه ليس له أي تعادل.

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

هناك طريقة بديلة لوصف الفائز في طريقة شولز وهي الإجراء التالي:

# ارسم رسمًا بيانيًا موجهًا كاملاً لجميع المرشحين، وجميع الحواف الممكنة بين المرشحين
# بشكل متكرر [أ] احذف جميع المرشحين غير الموجودين في مجموعة شوارتز (أي أي مرشح *x* لا يمكنه الوصول إلى جميع الآخرين الذين وصلوا إلى *x*) و[ب] احذف حافة الرسم البياني ذات القيمة الأصغر (إذا كان بالهامش، أصغر هامش؛ إذا كان بالأصوات، أقل الأصوات).
# الفائز هو آخر مرشح غير محذوف.

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

# أنشئ جدول النتائج، المسمى "مصفوفة التفضيلات الزوجية"، كما هو مستخدم في المثال أعلاه. إذا كنت تستخدم الهوامش بدلاً من إجمالي الأصوات الأولية، فاطرحها من مُدورها (subtract it from its transpose). بعد ذلك، يعتبر كل رقم موجب فوزًا زوجيًا للمرشح في هذا الصف (ومميزًا باللون الأخضر)، وتكون التعادلات أصفارًا، والخسائر سالبة (مميزة باللون الأحمر). قم بترتيب المرشحين حسب المدة التي قضوها أثناء عملية الإقصاء (الحذف).
# إذا كان هناك مرشح ليس في خطه اللون الأحمر، فهو الذي يفوز.
# بخلاف ذلك، ارسم مربعًا حول مجموعة شوارتز في الزاوية اليسرى العليا. ويمكن وصفها بأنها الحد الأدنى من "دائرة الفائزين" للمرشحين الذين لا يخسرون أمام أي شخص خارج الدائرة. لاحظ أنه لا يوجد لون أحمر على يمين المربع، مما يعني أنها دائرة فائز، ولاحظ أنه داخل المربع لا توجد إمكانية لإعادة الترتيب من شأنها أن تُنتج دائرة فائز أصغر.
# قم بشطب كل جزء من الجدول خارج المربع.
# إذا لم يكن هناك أي مرشح بدون لون أحمر على خطه، فيجب التنازل عن شيء ما؛ لقد خسر كل مرشح بعض السباق، والخسارة التي نتحملها بشكل أفضل هي تلك التي حصل فيها الخاسر على أكبر عدد من الأصوات. لذا، خذ الخلية الحمراء ذات الرقم الأعلى (إذا كانت الهوامش، الأقل سلبية)، اجعلها خضراء - أو أي لون آخر غير الأحمر - وارجع إلى الخطوة 2.

فيما يلي جدول الهوامش المصنوع من المثال أعلاه. لاحظ تغيير الترتيب لأغراض العرض التوضيحي.

الخروج الأول (خسارة A أمام E بصوت واحد) لا يساعد في تقليص مجموعة شوارتز.

لذلك نصل مباشرة إلى الخروج الثاني (خسارة E أمام C بـ 3 أصوات)، وهذا يوضح لنا الفائز، E، بصفه الواضح.

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

## المعايير المستوفاة والفاشلة

### معايير مستوفاة
تستوفي طريقة شولز المعايير التالية:

* Unrestricted domain
* Non-imposition (a.k.a. citizen sovereignty)
* Non-dictatorship
* أمثلية باريتو
* Monotonicity criterion
* Majority criterion
* Majority loser criterion
* Condorcet criterion
* Condorcet loser criterion
* 
* Smith criterion
* Independence of Smith-dominated alternatives
* Mutual majority criterion
* 
* Reversal symmetry
* Mono-append
* Mono-add-plump
* Resolvability criterion
* تعقيد الوقت
* prudence
* MinMax sets
*  if  are used for d[X,Y]
* Symmetric-completion if margins are used for d[X,Y]

### معايير فاشلة
بما أن طريقة شولز تفي بمعيار كوندورسيه، فإنها تفشل تلقائيا في تلبية المعايير التالية:

* المشاركة 
* تناسق
* عدم القدرة على المساومة
* عدم القدرة على الدفن
* في وقت لاحق لا ضرر

وبالمثل، بما أن طريقة شولز ليست دكتاتورية وتوافق على إجماع الأصوات، فإن نظرية السهم تشير ضمنًا إلى أنها تفشل في تلبية معيار

* استقلال البدائل غير ذات الصلة (Independence of irrelevant alternatives)

كما فشلت طريقة شولز في:

* معيار بيتون يونغ: الاستقلال المحلي للبدائل غير ذات الصلة.

### جدول المقارنة
يقارن الجدول التالي طريقة شولز مع طرق الانتخابات التفضيلية الأخرى للفائز الواحد:

يمكن رؤية الفرق الرئيسي بين طريقة شولز وطريقة الأزواج المرتبة (ranked pairs) في هذا المثال:

لنفترض أن نتيجة MinMax لمجموعة **X** من المرشحين هي قوة أقوى فوز زوجي للمرشح A ∉ **X** ضد المرشح B ∈ **X**. فإن طريقة شولز، وليس الأزواج المُرتبة، تضمن أن الفائز هو دائمًا مرشح للمجموعة ذات الحد الأدنى من نقاط MinMax.  لذا، فإن طريقة شولز، إلى حد ما، تقلل من الأغلبية الأكبر التي يجب عكسها عند تحديد الفائز.

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

## التاريخ
ابتكرت ماركوس شولز طريقة شولز في عام 1997. وجرى مناقشتها لأول مرة في القوائم البريدية العامة في 1997-1998 وفي عام 2000.

في عام 2011، نشر شولز هذه الطريقة في المجلة الأكاديمية *Social Choice and Welfare*.

## الاستخدام
[يسار|تصغير| نموذج اقتراع لانتخابات [مؤسسة ويكيميديا|مجلس أمناء ويكيميديا]]

### الحكومات
تُستخدم طريقة شولز في مدينة بلنسية في جميع الاستفتاءات. كما تستخدم أيضًا في مدينتي تورينو وسان دونا دي بيافي ومنطقة ساوثوارك في لندن من خلال استخدامهم لمنصة WeGovNow، والتي تستخدم بدورها أداة اتخاذ القرار LiquidFeedback.

### الأحزاب السياسية
اعتمد حزب القراصنة السويدي (2009)، وحزب القراصنة الألماني (2010) هذه الطريقة. وجرى اختيار فرع بويسي، أيداهو، الذي جرى تشكيله حديثًا، من الاشتراكيين الديمقراطيين الأمريكيين في فبراير، لهذه الطريقة في أول انتخابات خاصة لهم أجريت في مارس 2018.

* حركة الخمس نجوم في كامبوباسو،  فوندي،  مونتي كومباتري،  مونتيمورلو،  بيسكارا،  وسان سيساريو
* أحزاب القراصنة في أستراليا،  النمسا،  بلجيكا،  البرازيل، ألمانيا،  أيسلندا،  إيطاليا،  هولندا، [13] السويد،  سويسرا،  والولايات المتحدة
* الاتحاد المستدام
* فولت أوروبا

### الجمعيات الطلابية

* AEGEE – منتدى الطلاب الأوروبيين
* Club der Ehemaligen der Deutschen SchülerAkademien e. خامسا
* حكومة الطلاب المنتسبين في المدرسة العليا بباريس
* الجمعية الفلمنكية لطلاب الهندسة لوفين
* منظمة طلاب الدراسات العليا في جامعة ولاية نيويورك: علوم الكمبيوتر (GSOCS)
* هيليغاس باركر هاوس
* قاعة كينجمان
* الطلاب المنتسبون لمدارس مينيرفا في KGI
* الهيئة الطلابية المنتسبة في جامعة نورث وسترن
* هيئة الطلاب المنتسبين بجامعة فرايبورغ
* هيئة الطلاب المنتسبين في قسم علوم الكمبيوتر بجامعة كايزرسلاوترن

### المنظمات
تُستخدم الطريقة في معهد مهندسي الكهرباء والإلكترونيات، وكذلك جمعية آلات الحوسبة، إضافة إلى USENIX من خلال استخدامهم لأداة اتخاذ القرار HotCRP.

تشمل المنظمات التي تستخدم حاليًا طريقة شولز ما يلي:

* 
*  (BVKJ)
* 
* 
* County Highpointers
* Dapr
* دبيان
* EuroBillTracker
* European Democratic Education Community (EUDEC)
* إف إف إم بي إي جي
* Free Geek
* Free Hardware Foundation of Italy
* جنتو لينكس
* جنو برايفسي جارد (GnuPG)
* هاسكل
* 
* آيكان (ICANN) (until 2023)
* Kanawha Valley Scrabble Club
* كدي
* 
* كوبيرنيتيس
* Kumoricon
* League of Professional System Administrators (LOPSA)
* ليكويد فيدباك
* Madisonium
* Metalab
* إم تي في
* Neo
* Noisebridge
* OpenEmbedded
* Open Neural Network Exchange
* أوبن ستاك
* OpenSwitch
* RLLMUK
* Squeak
* Students for Free Culture
* شوجر لابز
* Sverok
* توب كودر
* أوبونتو
* Vidya Gaem Awards
* مؤسسة ويكيميديا (2008)
* ويكيبيديا في ويكيبيديا الفرنسية،  ويكيبيديا العبرية،  ويكيبيديا المجرية،  ويكيبيديا الروسية،  ويكيبيديا الفارسية.

## المراجع

## روابط خارجية

*  بقلم ماركوس شولز
* طريقة شولز بقلم هيوبرت براي
* سبيلثيوري  بواسطة برنهارد نيبل
* الديمقراطية الدقيقة لروب لورينج
* كريستوف بورجرز (2009)، *[https://books.google.com/books?id=dccBaphP1G4C&pg=PA37 رياضيات الاختيار الاجتماعي: التصويت والتعويض والقسمة]*، SIAM،
* نيكولاس تيدمان (2006)، *[https://books.google.com/books?id=RN5q_LuByUoC&pg=PA228 القرارات الجماعية والتصويت: إمكانية الاختيار العام]*، بيرلينجتون: أشجيت، 
* الأدوات المسبقة من قبل مجموعة البرمجيات العامة
* أريزونا للتصويت المصنف في كوندورسيه
* تطبيق سطر أوامر Condorcet PHP ومكتبة PHP، يدعم أساليب Condorcet المتعددة، بما في ذلك Schulze.
* التنفيذ في جافا
* التنفيذ في روبي
* التنفيذ في بيثون 2
* التنفيذ في بيثون 3

تصنيف:دبيان
تصنيف:مقالات تحوي أمثلة مكتوبة بشبه رماز
تصنيف:نظم تصويت