روش شولتسه

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

روش شولتسه نوعی روش کندورسه است، بدین معنی که اگر نامزدی وجود داشته باشد که در مقابله‌های دوبدو نسبت به تک‌تک نامزدهای دیگر برنده باشد، همان نامزد برنده خواهد بود.^[۱]

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

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

توصیف روش

برگه‌های رأی

نمونهٔ برگهٔ رأی نظام‌های انتخاباتی ترجیحی

ورودی روش شولتسه مشابه سایر نظام‌های انتخاباتی تک‌برندهٔ ترجیحی است: رأی‌دهندگان نامزدان را نسبت به هم اولویت‌بندی می‌کنند. در ذکر اولویت‌ها تساوی نیز مجاز است. همهٔ نامزدها در برگه‌های رأیْ فهرست شده‌اند و هر رأی‌دهنده با استفاده از اعداد، این فهرست را به ترتیب ترجیحاتش رتبه‌بندی می‌کند: رأی‌دهنده شایسته‌ترین نامزد را در رتبهٔ اول می‌نشاند، و نامزد دوم از لحاظ شایستگی را در رتبهٔ دوم قرار می‌دهد و به همین منوال ادامه می‌دهد. هر رأی‌دهنده مجاز است:

• چندین نامزد را در یک رتبه بنشاند. این یعنی که از نظر رأی‌دهنده تفاوتی بین این نامزدان وجود ندارد.
• از اعداد نامتوالی استفاده کند. این امر روی نتیجهٔ انتخابات تأثیر نمی‌گذارد چرا که تنها ترتیب نامزدان نسبت به یکدیگر حائز اهمیت است و خود اعداد (۱ یا ۲ یا . . .) مهم نیستند.
• برخی از نامزدان را رتبه‌بندی نکند که در این صورت تفسیر رفتار او چنین است: الف) نامزدان رتبه‌بندی‌شده شایسته‌تر از نامزدان رتبه‌بندی‌نشده هستند؛ ب) بین نامزدان رتبه‌بندی‌نشده تفاوتی قائل نیست.

محاسبه

${\displaystyle d[V,W]}$ را تعداد رأی‌دهندگانی در نظر می‌گیریم که نامزد ${\displaystyle V}$ را به نامزد ${\displaystyle W}$ ترجیح داده‌اند.

یک مسیر از نامزد ${\displaystyle X}$ به نامزد ${\displaystyle Y}$ به قدرت ${\displaystyle p}$ دنباله‌ای از نامزدان ${\displaystyle C(1),...,C(n)}$ با ویژگی‌های زیر تعریف می‌شود:

1. ${\displaystyle C(1)=X}$ و ${\displaystyle C(n)=Y}$.
2. برای هر ${\displaystyle i=1,...,(n-1)}$ داریم ${\displaystyle d[C(i),C(i+1)]>d[C(i+1),C(i)]}$.
3. برای هر ${\displaystyle i=1,...,(n-1)}$ داریم ${\displaystyle d[C(i),C(i+1)]{\text{≥}}p}$.

${\displaystyle p[A,B]}$، قدرت قوی‌ترین مسیر از نامزد ${\displaystyle A}$ به نامزد ${\displaystyle B}$، مقدار بیشینه‌ای است به قسمی که مسیری از نامزد ${\displaystyle A}$ به نامزد ${\displaystyle B}$ با آن قدرت وجود داشته باشد. اگر اصلاً مسیری از نامزد ${\displaystyle A}$ به ${\displaystyle B}$ وجود نداشته باشد، آنگاه ${\displaystyle p[A,B]=0}$.

نامزد ${\displaystyle D}$ از نامزد ${\displaystyle E}$ بهتر است اگر و فقط اگر ${\displaystyle p[D,E]>p[E,D]}$.

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

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

مثال

در مثال ذیل ۴۵ رأی‌دهنده ۵ نامزد را رتبه‌بندی می‌کنند.

• ۵ ${\displaystyle ACBED}$ ^[الف]
• ۵ ${\displaystyle ADECB}$
• ۸ ${\displaystyle BEDAC}$
• ۳ ${\displaystyle CABED}$
• ۷ ${\displaystyle CAEBD}$
• ۲ ${\displaystyle CBADE}$
• ۷ ${\displaystyle DCEBA}$
• ۸ ${\displaystyle EBADC}$

ابتدا می‌بایست مقابله‌های رو-در-رو را محاسبه کرد. مثلاً در مقابلهٔ رو-در-روی ${\displaystyle A}$ و ${\displaystyle B}$، تعداد ${\displaystyle 5+5+3+7=20}$ رأی‌دهنده ${\displaystyle A}$ را به ${\displaystyle B}$ ترجیح داده‌اند و ${\displaystyle 8+2+7+8=25}$ رأی‌دهنده ${\displaystyle B}$ را به ${\displaystyle A}$. پس ${\displaystyle d[A,B]=20}$ و ${\displaystyle d[B,A]=25}$. نتایج کامل مقابله‌های رو-در-رو از قرار زیر است:

گراف جهتدار به همراه برچسب‌های مقابله‌های رو-در-رو ${\displaystyle d[*,*]}$

ماتریس مقابله‌های رو-در-رو

	d[*,A]	d[*,B]	d[*,C]	d[*,D]	d[*,E]
d[A,*]		۲۰	۲۶	۳۰	۲۲
d[B,*]	۲۵		۱۶	۳۳	۱۸
d[C,*]	۱۹	۲۹		۱۷	۲۴
d[D,*]	۱۵	۱۲	۲۸		۱۴
d[E,*]	۲۳	۲۷	۲۱	۳۱

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

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

جدول زیر قوی‌ترین مسیر از نامزد ${\displaystyle X}$ به ${\displaystyle Y}$ را برای هر جفت از نامزدان با رنگ قرمز نمایش می‌دهد و ضعیف‌ترین رشتهٔ پیوند مورب شده‌است.

قوی‌ترین مسیرها

	… به A	… به B	… به C	… به D	… به E
از A ...		A-(30)-D-(28)-C-(29)-B	A-(30)-D-(28)-C	A-(30)-D	A-(30)-D-(28)-C-(24)-E	از A ...
از B ...	B-(25)-A		B-(33)-D-(28)-C	B-(33)-D	B-(33)-D-(28)-C-(24)-E	از B ...
از C ...	C-(29)-B-(25)-A	C-(29)-B		C-(29)-B-(33)-D	C-(24)-E	از C ...
از D ...	D-(28)-C-(29)-B-(25)-A	D-(28)-C-(29)-B	D-(28)-C		D-(28)-C-(24)-E	از D ...
از E ...	E-(31)-D-(28)-C-(29)-B-(25)-A	E-(31)-D-(28)-C-(29)-B	E-(31)-D-(28)-C	E-(31)-D		از E ...
	… به A	… به B	… به C	… به D	… به E

قدرت قوی‌ترین مسیرها

	p[*,A]	p[*,B]	p[*,C]	p[*,D]	p[*,E]
p[A,*]		۲۸	۲۸	۳۰	۲۴
p[B,*]	۲۵		۲۸	۳۳	۲۴
p[C,*]	۲۵	۲۹		۲۹	۲۴
p[D,*]	۲۵	۲۸	۲۸		۲۴
p[E,*]	۲۵	۲۸	۲۸	۳۱

حال می‌توان خروجی روش شولتسه را معین کرد. مثلاً در مقایسهٔ ${\displaystyle A}$ با ${\displaystyle B}$ چون ${\displaystyle 28=p[A,B]>p[B,A]=25}$ پس نامزد ${\displaystyle A}$ از نامزد ${\displaystyle B}$ بهتر است. به عنوان مثالی دیگر ${\displaystyle 31=p[E,D]>p[D,E]=24}$ پس نامزد ${\displaystyle E}$ از نامزد ${\displaystyle D}$ بهتر است. اگر به همین منوال ادامه دهیم، نتیجه (رتبه‌بندی شولتسه) ${\displaystyle E>A>C>B>D}$ خواهد بود و ${\displaystyle E}$ برنده خواهد شد. به عبارت دیگر ${\displaystyle E}$ برنده است چون برای هر نامزد دیگر ${\displaystyle X}$ داریم ${\displaystyle p[E,X]\geq p[X,E]}$.^[۲]

اجرا

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

# 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] ) )

این الگوریتم کاراست و مدت زمان اجرایش متناسب با ${\displaystyle C^{3}}$ می‌باشد که ${\displaystyle C}$ تعداد نامزدان است.

تساوی و دیگر روال‌ها

اگر رأی‌دهندگان مجاز به استفاده از تساوی در ترجیحاتشان باشند، خروجی روش شولتسه به چگونگی تفسیر تساوی در تعریف ${\displaystyle d[*,*]}$ بستگی پیدا خواهد کرد. این‌ها دو انتخاب معمولند: الف) ${\displaystyle d[A,B]}$ تعداد رأی‌دهندگانی باشد که اکیداً ${\displaystyle A}$ را به ${\displaystyle B}$ ترجیح می‌دهند؛ ب) ${\displaystyle d[A,B]}$ تفاضل تعداد رأی‌دهندگانی باشد که (${\displaystyle A}$ را به ${\displaystyle B}$ ترجیح می‌دهند) و (رأی‌دهندگانی که ${\displaystyle B}$ را به ${\displaystyle A}$ ترجیح می‌دهند). اینکه ${\displaystyle d}$ها چگونه تعریف شوند در نتیجه تأثیری نمی‌گذارد. روش شولتسه فاقد چرخه است و با فرض اینکه ${\displaystyle d}$ها یکتا باشند، تساوی رخ نخواهد داد.^[۳]

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

روال دیگری نیز برای تعیین برنده در روش شولتسه وجود دارد که البته کندتر است:

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

تاریخچه

روش شولتسه را مارکوس شولتسه در سال ۱۹۹۷ ابداع کرد. اولین بار در سال‌های ۹۸–۱۹۹۷ و ۲۰۰۰ بر روی این روش در میلینگ‌لیست‌های عمومی بحث شد. بعداً نرم‌افزار در خدمت منافع عمومی (۲۰۰۳)، دبیان (۲۰۰۳)، جنتو (۲۰۰۵)، تاپ‌کُدر (۲۰۰۵)، ویکی‌مدیا (۲۰۰۸)، کی‌دی‌ئی (۲۰۰۸)، بنیاد نرم‌افزار آزاد اروپا (۲۰۰۸)، حزب دزدان دریایی سوئد (۲۰۰۹)، و حزب دزدان دریایی آلمان (۲۰۱۰) از این روش استفاده کردند. روش شولتسه یکی از دو روش مورد استفاده در رأی‌گیری‌های چندنامزدی در ویکی‌پدیای فرانسوی است که در سال ۲۰۰۵ با رأی اکثریت تصویب شد و چندین بار مورد استفاده قرار گرفته‌است.^[۴][۵]

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

استفاده‌کنندگان

برگهٔ رأی انتخابات هیئت امنای بنیاد ویکی‌مدیا

تاکنون از روش شولتسه برای انتخابات پارلمانی استفاده نشده اما حزب دزدان دریایی سوئد از این روش برای انتخابات مقدماتی پارلمان استفاده کرده‌است. اقبال به این روش از جانب سازمان‌های عمومی رو به افزایش است.^[۶] برخی از سازمان‌هایی که از این روش استفاده می‌کنند، در زیر فهرست شده‌اند:

• آزمایشگاه شکر
• اف‌اف‌امپگ
• ام‌تی‌وی
• اوبونتو
• اوپن‌استک
• بنیاد نرم‌افزار آزاد اروپا
• جنتو لینوکس
• دانشگاه نورت‌وسترن
• دبیان
• جنبش پنج ستاره ایتالیا (پسکارا، فوندی، کامپوباسو، مونته مورلو)
• حزب دزدان دریایی آلمان، اتریش، استرالیا، ایتالیا، ایسلند، برزیل، بلژیک، سوئد، سوئیس، نیوزیلند، هلند
• کوبونتو
• کی‌دی‌ئی
• گنو پرایوسی گارد
• ویکی‌پدیای فرانسوی، عبری، مجاری، و روسی.
• هسکل

یادداشت‌

1. بدین معنی که ترتیب ترجیحات ۵ رأی‌دهنده چنین است: ${\displaystyle A>C>B>E>D}$

منابع

1. Markus Schulze, "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.
2. Tideman, T. Nicolaus, "Independence of clones as a criterion for voting rules", Social Choice and Welfare vol 4 #3 (1987), pp. 185–206.
3. Markus Schulze, "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.
4. Anthony Towns, Disambiguation of 4.1.5, November 2000
5. "Statutory Language for Choice Voting, Cumulative Voting, and Instant Runoff Voting". Behind the Ballot Box: 191–195. 2000. doi:10.5040/9798400617362.0019.
6. Hortanoticias, Redacción (2016-02-23). "Al voltant de 2.000 participants en dos dies en la primera enquesta popular de Silla que decidirà sobre espectacles taurins". Hortanoticias.com (به اسپانیایی). Retrieved 2022-09-24.

• Wikipedia contributors, "Schulze method," Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/w/index.php?title=Schulze_method&oldid=628267803 (accessed October 10, 2014).