نمایش مبدأ برای روش شولتسه

'''روش شولتسه''' {{آلمانی|Schulze-Methode}} نوعی [[نظام انتخاباتی]] تک‌برنده است که برگه‌های رأی در آن به شکل [[نظام انتخاباتی ترجیحی|ترجیحی]] (رتبه‌ای) می‌باشند. این روش را مارکوس شولتسه در سال ۱۹۹۷ ابداع کرد.

روش شولتسه نوعی [[روش کندورسه]] است، بدین معنی که اگر نامزدی وجود داشته باشد که در مقابله‌های دوبدو نسبت به تک‌تک نامزدهای دیگر برنده باشد، همان نامزد برنده خواهد بود.<ref name="schulze20113">Markus Schulze, "[[doi:10.1007/s00355-010-0475-4|A new monotonic, clone-independent, reversal symmetric, and condorcet-consistent single-winner election method]]", Social Choice and Welfare, volume 36, number 2, page 267–303, 2011. Preliminary version in ''Voting Matters'', 17:9-19, 2003.</ref>

خروجی روش شولتسه نامزدان را رتبه‌بندی می‌کند؛ بنابراین اگر k کرسی موجود باشد، می‌توان از همین روش بدون هیچ تغییری استفاده کرد و k نامزد حائز رتبه‌های بالاتر را بر k کرسی موجود نشاند. برای انتخابات چندبرنده، بدیل [[رأی انتقال‌پذیر شولتسه]] نیز پیشنهاد شده‌است.

چندین سازمان از جمله [[دبیان]]، [[اوبونتو (سیستم‌عامل)|اوبونتو]]، [[جنتو لینوکس|جنتو]]، [[نرم‌افزار در خدمت منافع عمومی]]، [[بنیاد نرم‌افزار آزاد اروپا]]، انجمن‌های [[احزاب دزدان دریایی]]، و . . . از روش شولتسه استفاده کرده‌اند.

== توصیف روش ==
=== برگه‌های رأی ===
[[پرونده:Preferential ballot in Persian(optimized).svg|انگشتی|نمونهٔ برگهٔ رأی نظام‌های انتخاباتی ترجیحی]]
ورودی روش شولتسه مشابه سایر [[نظام انتخاباتی تک‌برنده|نظام‌های انتخاباتی تک‌برندهٔ]] [[نظام انتخاباتی ترجیحی|ترجیحی]] است: رأی‌دهندگان نامزدان را نسبت به هم اولویت‌بندی می‌کنند. در ذکر اولویت‌ها تساوی نیز مجاز است. همهٔ نامزدها در برگه‌های رأیْ فهرست شده‌اند و هر رأی‌دهنده با استفاده از اعداد، این فهرست را به ترتیب ترجیحاتش رتبه‌بندی می‌کند: رأی‌دهنده شایسته‌ترین نامزد را در رتبهٔ اول می‌نشاند، و نامزد دوم از لحاظ شایستگی را در رتبهٔ دوم قرار می‌دهد و به همین منوال ادامه می‌دهد. هر رأی‌دهنده مجاز است:
* چندین نامزد را در یک رتبه بنشاند. این یعنی که از نظر رأی‌دهنده تفاوتی بین این نامزدان وجود ندارد.
* از اعداد نامتوالی استفاده کند. این امر روی نتیجهٔ انتخابات تأثیر نمی‌گذارد چرا که تنها ترتیب نامزدان نسبت به یکدیگر حائز اهمیت است و خود اعداد (۱ یا ۲ یا . . .) مهم نیستند.
* برخی از نامزدان را رتبه‌بندی نکند که در این صورت تفسیر رفتار او چنین است: الف) نامزدان رتبه‌بندی‌شده شایسته‌تر از نامزدان رتبه‌بندی‌نشده هستند؛ ب) بین نامزدان رتبه‌بندی‌نشده تفاوتی قائل نیست.

=== محاسبه ===
<math>d[V,W]</math> را تعداد رأی‌دهندگانی در نظر می‌گیریم که نامزد <math>V</math> را به نامزد <math>W</math> ترجیح داده‌اند.

یک ''مسیر'' از نامزد <math>X</math> به نامزد <math>Y</math> به ''قدرت'' <math>p</math> دنباله‌ای از نامزدان <math>C(1),...,C(n)</math> با ویژگی‌های زیر تعریف می‌شود:
# <math>C(1) = X</math> و <math>C(n) = Y</math>.
# برای هر <math>i = 1,...,(n-1)</math> داریم <math>d[C(i),C(i+1)]> d[C(i+1),C(i)]</math>.
# برای هر <math>i = 1,...,(n-1)</math> داریم <math>d[C(i),C(i+1)] \text{≥} p</math>.

<math>p[A,B]</math>، ''قدرت قوی‌ترین مسیر'' از نامزد <math>A</math> به نامزد <math>B</math>، مقدار بیشینه‌ای است به قسمی که مسیری از نامزد <math>A</math> به نامزد <math>B</math> با آن قدرت وجود داشته باشد. اگر اصلاً مسیری از نامزد <math>A</math> به <math>B</math> وجود نداشته باشد، آنگاه <math>p[A,B] = 0</math>.

نامزد <math>D</math> از نامزد <math>E</math> ''بهتر'' است اگر و فقط اگر <math>p[D,E]> p[E,D]</math>.

نامزد <math>D</math> یک ''برندهٔ بالقوه'' است اگر و فقط اگر برای هر نامزد دیگر <math>E</math> داشته باشیم <math>p[D,E] \text{≥} p[E,D]</math>.

می‌توان ثابت کرد که <math>p[X,Y]> p[Y,X]</math> و <math>p[Y,Z]> p[Z,Y]</math> با هم نتیجه می‌دهند <math>p[X,Z]> p[Z,X]</math>. بنابراین اطمینان حاصل می‌شود که الف) تعریف بالایی از «''بهتری''» واقعاً معرف یک [[رابطهٔ ترایا]] است و ب) همیشه حداقل یک نامزد <math>D</math> وجود دارد که برای هر نامزد دیگر <math>E</math> داشته باشیم: <math>p[D,E] \text{≥} p[E,D]</math>.

== مثال ==
در مثال ذیل ۴۵ رأی‌دهنده ۵ نامزد را رتبه‌بندی می‌کنند.
* ۵ <math>ACBED</math> {{یاد|بدین معنی که ترتیب ترجیحات ۵ رأی‌دهنده چنین است: <math>A> C> B> E> D</math>}} 
* ۵ <math>ADECB</math>
* ۸ <math>BEDAC</math>
* ۳ <math>CABED</math>
* ۷ <math>CAEBD</math>
* ۲ <math>CBADE</math>
* ۷ <math>DCEBA</math>
* ۸ <math>EBADC</math>

ابتدا می‌بایست مقابله‌های رو-در-رو را محاسبه کرد. مثلاً در مقابلهٔ رو-در-روی <math>A</math> و <math>B</math>، تعداد <math>5+5+3+7=20</math> رأی‌دهنده <math>A</math> را به <math>B</math> ترجیح داده‌اند و <math>8+2+7+8=25</math> رأی‌دهنده <math>B</math> را به <math>A</math>. پس <math>d[A, B] = 20</math> و <math>d[B, A] = 25</math>. نتایج کامل مقابله‌های رو-در-رو از قرار زیر است:
[[پرونده:Schulze method example1.svg|انگشتی|300px|[[گراف جهتدار]] به همراه برچسب‌های مقابله‌های رو-در-رو <math>d[*, *]</math>]]

{| class="wikitable" style="text-align:center" dir="ltr"
|+ ماتریس مقابله‌های رو-در-رو
|-
! !! d[*,A] !! d[*,B] !! d[*,C] !! d[*,D] !! d[*,E]
|-
! d[A,*]
| || bgcolor=#fee7e6|۲۰ || bgcolor=#ddffdd|۲۶ || bgcolor=#ddffdd|۳۰ || bgcolor=#fee7e6|۲۲
|-
! d[B,*]
| bgcolor=#ddffdd|۲۵ || || bgcolor=#fee7e6|۱۶ || bgcolor=#ddffdd|۳۳ || bgcolor=#fee7e6|۱۸
|-
! d[C,*]
| bgcolor=#fee7e6|۱۹ || bgcolor=#ddffdd|۲۹ || || bgcolor=#fee7e6|۱۷ || bgcolor=#ddffdd|۲۴
|-
! d[D,*]
| bgcolor=#fee7e6|۱۵ || bgcolor=#fee7e6|۱۲ || bgcolor=#ddffdd|۲۸ || || bgcolor=#fee7e6|۱۴
|-
! d[E,*]
| bgcolor=#ddffdd|۲۳ || bgcolor=#ddffdd|۲۷ || bgcolor=#fee7e6|۲۱ || bgcolor=#ddffdd|۳۱ ||
|}

رنگ پس‌زمینهٔ سلول <math>d[X, Y]</math> سبز است اگر <math>d[X, Y]> d[Y, X]</math> وگرنه قرمز. در این مثال برندهٔ بلامنازعی وجود ندارد که صرفاً با نگاه‌انداختن به مقابله‌های رو-در-رو آشکار شود.

حالا باید قوی‌ترین مسیرها را مشخص کرد. برای آنکه قوی‌ترین مسیرها به‌آسانی به چشم آیند، نتایج مقابله‌های رو-در-رو در گراف جهت‌دار سمت چپ ترسیم شده‌اند. پیکانی که از رأس <math>X</math> به <math>Y</math> نشانه رفته‌است برچسب <math>d[X, Y]</math> دارد. برای پرهیز از شلوغ‌شدن گراف، فقط در صورتی که <math>d[X, Y]> d[Y, X]</math> پیکان از رأس <math>X</math> به <math>Y</math> نشانه رفته‌است (سلول‌های سبز ماتریس). در این مثال <math>p[B, D] = 33</math> زیرا قوی‌ترین مسیر از <math>B</math> به <math>D</math>، مسیر مستقیم است که قدرت ۳۳ دارد. اما <math>p[A, C] = 28</math> زیرا قوی‌ترین مسیر از <math>A</math> به <math>C</math>، مسیر مستقیم <math>(A, C)</math> به قدرت ۲۶ نیست، بلکه مسیر غیرمستقیم <math>(A, D, C)</math> است که قدرت <math>min(30, 28) = 28</math> را دارد. قدرت یک مسیر، قدرت ضعیف‌ترین رشتهٔ پیوند است.

جدول زیر قوی‌ترین مسیر از نامزد <math>X</math> به <math>Y</math> را برای هر جفت از نامزدان با رنگ قرمز نمایش می‌دهد و ضعیف‌ترین رشتهٔ پیوند ''مورب'' شده‌است.

{{clear}}
{| class="wikitable" style="text-align:center"
|+قوی‌ترین مسیرها
|-
! !! … به A !! … به B !! … به C !! … به D !! … به E !!
|-
! از A ...
| || [[پرونده:Schulze method example1 AB.svg|border|none|150px|left]] A-(30)-D-(''28'')-C-(29)-B || [[پرونده:Schulze method example1 AC.svg|border|none|150px|left]] A-(30)-D-(''28'')-C || [[پرونده:Schulze method example1 AD.svg|border|none|150px|left]] A-(''30'')-D || [[پرونده:Schulze method example1 AE.svg|border|none|150px|left]] A-(30)-D-(28)-C-(''24'')-E
! از A ...
|-
! از B ...
| [[پرونده:Schulze method example1 BA.svg|border|none|150px|left]] B-(''25'')-A || || [[پرونده:Schulze method example1 BC.svg|border|none|150px|left]] B-(33)-D-(''28'')-C || [[پرونده:Schulze method example1 BD.svg|border|none|150px|left]] B-(''33'')-D || [[پرونده:Schulze method example1 BE.svg|border|none|150px|left]] B-(33)-D-(28)-C-(''24'')-E
! از B ...
|-
! از C ...
| [[پرونده:Schulze method example1 CA.svg|border|none|150px|left]] C-(29)-B-(''25'')-A || [[پرونده:Schulze method example1 CB.svg|border|none|150px|left]] C-(''29'')-B || || [[پرونده:Schulze method example1 CD.svg|border|none|150px|left]] C-(''29'')-B-(33)-D || [[پرونده:Schulze method example1 CE.svg|border|none|150px|left]] C-(''24'')-E
! از C ...
|-
! از D ...
| [[پرونده:Schulze method example1 DA.svg|border|none|150px|left]] D-(28)-C-(29)-B-(''25'')-A || [[پرونده:Schulze method example1 DB.svg|border|none|150px|left]] D-(''28'')-C-(29)-B || [[پرونده:Schulze method example1 DC.svg|border|none|150px|left]] D-(''28'')-C || || [[پرونده:Schulze method example1 DE.svg|border|none|150px|left]] D-(28)-C-(''24'')-E
! از D ...
|-
! از E ...
| [[پرونده:Schulze method example1 EA.svg|border|none|150px|left]] E-(31)-D-(28)-C-(29)-B-(''25'')-A || [[پرونده:Schulze method example1 EB.svg|border|none|150px|left]] E-(31)-D-(''28'')-C-(29)-B || [[پرونده:Schulze method example1 EC.svg|border|none|150px|left]] E-(31)-D-(''28'')-C || [[پرونده:Schulze method example1 ED.svg|border|none|150px|left]] E-(''31'')-D ||
! از E ...
|-
! !! … به A !! … به B !! … به C !! … به D !! … به E !!
|}

{| class="wikitable" style="text-align:center" dir="ltr"
|+قدرت قوی‌ترین مسیرها
|-
! !! p[*,A] !! p[*,B] !! p[*,C] !! p[*,D] !! p[*,E]
|-
! p[A,*]
| || bgcolor=#ddffdd|۲۸ || bgcolor=#ddffdd|۲۸ || bgcolor=#ddffdd|۳۰ || bgcolor=#fee7e6|۲۴
|-
! p[B,*]
| bgcolor=#fee7e6|۲۵ || || bgcolor=#fee7e6|۲۸ || bgcolor=#ddffdd|۳۳ || bgcolor=#fee7e6|۲۴
|-
! p[C,*]
| bgcolor=#fee7e6|۲۵ || bgcolor=#ddffdd|۲۹ || || bgcolor=#ddffdd|۲۹ || bgcolor=#fee7e6|۲۴
|-
! p[D,*]
| bgcolor=#fee7e6|۲۵ || bgcolor=#fee7e6|۲۸ || bgcolor=#fee7e6|۲۸ || || bgcolor=#fee7e6|۲۴
|-
! p[E,*]
| bgcolor=#ddffdd|۲۵ || bgcolor=#ddffdd|۲۸ || bgcolor=#ddffdd|۲۸ || bgcolor=#ddffdd|۳۱ ||
|}

حال می‌توان خروجی روش شولتسه را معین کرد. مثلاً در مقایسهٔ <math>A</math> با <math>B</math> چون <math>28 = p[A,B]> p[B,A] = 25</math> پس نامزد <math>A</math> از نامزد <math>B</math> بهتر است. به عنوان مثالی دیگر <math>31 = p[E,D]> p[D,E] = 24</math> پس نامزد <math>E</math> از نامزد <math>D</math> بهتر است. اگر به همین منوال ادامه دهیم، نتیجه (رتبه‌بندی شولتسه) <math>E> A> C> B> D</math> خواهد بود و <math>E</math> برنده خواهد شد. به عبارت دیگر <math>E</math> برنده است چون برای هر نامزد دیگر <math>X</math> داریم <math>p[E,X] \ge p[X,E]</math>.<ref>Tideman, T. Nicolaus, "Independence of clones as a criterion for voting rules", Social Choice and Welfare vol 4 #3 (1987), pp. 185–206.</ref>

== اجرا ==
تنها مرحلهٔ دشوار در اجرای روش شولتسه، محاسبهٔ قدرت قوی‌ترین مسیرهاست. با وجود این، این مشکل مسئله‌ای مشهور در نظریهٔ گراف‌ها موسوم به [[مسئله عریض‌ترین مسیر|مسئلهٔ عریض‌ترین مسیر]] است. یک روش ساده برای محاسبهٔ قدرت‌ها، به‌کارگیری بدیل [[الگوریتم فلوید-وارشال]] است. الگوریتم در [[شبه‌کد]] زیر شرح داده شده‌است:

<syntaxhighlight line lang="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] ) )
</syntaxhighlight>

این الگوریتم [[کلاس پی|کاراست]] و مدت زمان اجرایش متناسب با <math>C^3</math> می‌باشد که <math>C</math> تعداد نامزدان است.

== تساوی و دیگر روال‌ها ==
اگر رأی‌دهندگان مجاز به استفاده از تساوی در ترجیحاتشان باشند، خروجی روش شولتسه به چگونگی تفسیر تساوی در تعریف <math>d[*,*]</math> بستگی پیدا خواهد کرد. این‌ها دو انتخاب معمولند: الف) <math>d[A, B]</math> تعداد رأی‌دهندگانی باشد که اکیداً <math>A</math> را به <math>B</math> ترجیح می‌دهند؛ ب) <math>d[A, B]</math> تفاضل تعداد رأی‌دهندگانی باشد که (<math>A</math> را به <math>B</math> ترجیح می‌دهند) و (رأی‌دهندگانی که <math>B</math> را به <math>A</math> ترجیح می‌دهند). اینکه <math>d</math>ها چگونه تعریف شوند در نتیجه تأثیری نمی‌گذارد. روش شولتسه فاقد چرخه است و با فرض اینکه <math>d</math>ها یکتا باشند، تساوی رخ نخواهد داد.<ref name="schulze201132">Markus Schulze, "[[doi:10.1007/s00355-010-0475-4|A new monotonic, clone-independent, reversal symmetric, and condorcet-consistent single-winner election method]]", Social Choice and Welfare, volume 36, number 2, page 267–303, 2011. Preliminary version in ''Voting Matters'', 17:9-19, 2003.</ref>

بروز تساوی در رتبه‌بندی شولتسه نامحتمل، اما ممکن است. مارکوس شولتسه، مبدع این روش، پیشنهاد می‌کند که برگهٔ رأی یکی از رأی‌دهندگان به شکل تصادفی انتخاب شود و طبق نظر او، تساوی شکسته شود و در صورت نیاز این کار تکرار شود.

روال دیگری نیز برای تعیین برنده در روش شولتسه وجود دارد که البته کندتر است:
# [[گراف جهتدار]] کاملی متشکل از همهٔ نامزدها و همهٔ یال‌های ممکن بین نامزدها رسم کنید؛
# مکرراً الف) نامزدانی را که در [[مجموعه شوارتس|مجموعهٔ شوارتس]] نیستند (هر نامزدی که نمی‌تواند به همهٔ دیگر نامزدها برسد) حذف کنید و ب) ضعیف‌ترین حلقهٔ اتصال را حذف کنید؛
# آخرین نامزد حذف‌نشده برنده است.

== تاریخچه ==
روش شولتسه را مارکوس شولتسه در سال ۱۹۹۷ ابداع کرد. اولین بار در سال‌های ۹۸–۱۹۹۷ و ۲۰۰۰ بر روی این روش در میلینگ‌لیست‌های عمومی بحث شد. بعداً [[نرم‌افزار در خدمت منافع عمومی]] (۲۰۰۳)، [[دبیان]] (۲۰۰۳)، [[جنتو لینوکس|جنتو]] (۲۰۰۵)، [[تاپ‌کدر|تاپ‌کُدر]] (۲۰۰۵)، [[بنیاد ویکی‌مدیا|ویکی‌مدیا]] (۲۰۰۸)، [[کی‌دی‌ئی]] (۲۰۰۸)، [[بنیاد نرم‌افزار آزاد اروپا]] (۲۰۰۸)، [[حزب دزدان دریایی سوئد]] (۲۰۰۹)، و [[حزب دزدان دریایی آلمان]] (۲۰۱۰) از این روش استفاده کردند. روش شولتسه یکی از دو روش مورد استفاده در رأی‌گیری‌های چندنامزدی در [[ویکی‌پدیای فرانسوی]] است که در سال ۲۰۰۵ با رأی اکثریت تصویب شد و چندین بار مورد استفاده قرار گرفته‌است.<ref>Anthony Towns, [https://lists.debian.org/debian-vote/2000/11/msg00121.html Disambiguation of 4.1.5], November 2000</ref><ref>{{Cite journal|date=2000|title=Statutory Language for Choice Voting, Cumulative Voting, and Instant Runoff Voting|url=https://doi.org/10.5040/9798400617362.0019|journal=Behind the Ballot Box|pages=191–195|doi=10.5040/9798400617362.0019}}</ref>

مارکوس شولتسه در سال ۲۰۱۱ مقاله‌ای دربارهٔ این روش در ژورنال دانشگاهی ''رفاه و انتخاب اجتماعی'' منتشر کرد.

== استفاده‌کنندگان ==
{{گسترش بخش}} 
[[پرونده:Voting2.png|انگشتی|برگهٔ رأی انتخابات هیئت امنای بنیاد ویکی‌مدیا]]
تاکنون از روش شولتسه برای انتخابات پارلمانی استفاده نشده اما [[حزب دزدان دریایی سوئد]] از این روش برای [[انتخابات مقدماتی]] پارلمان استفاده کرده‌است. اقبال به این روش از جانب سازمان‌های عمومی رو به افزایش است.<ref>{{Cite web|last=Hortanoticias|first=Redacción|date=2016-02-23|title=Al voltant de 2.000 participants en dos dies en la primera enquesta popular de Silla que decidirà sobre espectacles taurins|url=https://www.hortanoticias.com/al-voltant-de-2-000-participants-en-dos-dies-en-la-primera-enquesta-popular-de-silla-que-decidira-sobre-espectacles-taurins/|access-date=2022-09-24|website=Hortanoticias.com|language=es}}</ref> برخی از سازمان‌هایی که از این روش استفاده می‌کنند، در زیر فهرست شده‌اند:
* [[آزمایشگاه شکر]]
* [[اف‌اف‌امپگ]]
* [[ام‌تی‌وی]]
* [[اوبونتو (سیستم‌عامل)|اوبونتو]]
* [[اوپن‌استک]]
* [[بنیاد نرم‌افزار آزاد اروپا]]
* [[جنتو لینوکس]]
* [[دانشگاه نورت‌وسترن]]
* [[دبیان]]
* [[جنبش پنج ستاره]] ایتالیا ([[پسکارا]]، [[فوندی]]، [[کامپوباسو]]، [[مونته مورلو]])
* [[حزب دزدان دریایی]] آلمان، اتریش، استرالیا، ایتالیا، ایسلند، برزیل، بلژیک، سوئد، سوئیس، نیوزیلند، هلند
* [[کوبونتو]]
* [[کی‌دی‌ئی]]
* [[گنو پرایوسی گارد]]
* [[ویکی‌پدیا]]ی [[ویکی‌پدیای فرانسوی|فرانسوی]]، [[ویکی‌پدیای عبری|عبری]]، [[ویکی‌پدیای مجاری|مجاری]]، و [[ویکی‌پدیای روسی|روسی]].
* [[هسکل (زبان برنامه‌نویسی)|هسکل]]

== یادداشت‌ ==
{{یادداشت}}

== منابع ==
{{پانویس}}
{{چپ‌چین}}
* Wikipedia contributors, "Schulze method," Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/w/index.php?title=Schulze_method&oldid=628267803 (accessed October 10, 2014).
{{پایان چپ‌چین}}
[[رده:دبیان]]

[[رده:نظام‌های انتخاباتی]]
[[رده:نظام‌های انتخاباتی تک‌برنده]]