روش شولتسه

روش شولتسه نوعی نظام انتخاباتی تک‌برنده است که برگه‌های رای در آن به شکل ترجیحی (رتبه‌ای) می‌باشند. این روش را مارکوس شولتسه در سال ۱۹۹۷ ابداع کرد.
روش شولتسه نوعی روش کندورسه است، بدین معنی که اگر نامزدی وجود داشته باشد که در مقابله‌های دوبدو نسبت به تک‌تک نامزدهای دیگر برنده باشد، همان نامزد برنده خواهد بود.
خروجی روش شولتسه نامزدان را رتبه‌بندی می‌کند؛ بنابراین اگر k کرسی موجود باشد، می‌توان از همین روش بدون هیچ تغییری استفاده کرد و k نامزد حائز رتبه‌های بالاتر را بر k کرسی موجود نشاند. برای انتخابات چندبرنده، بدیل رای انتقال‌پذیر شولتسه نیز پیشنهاد شده‌است.
چندین سازمان از جمله دبیان، اوبونتو، جنتو، نرم‌افزار در خدمت منافع عمومی، بنیاد نرم‌افزار آزاد اروپا، انجمن‌های احزاب دزدان دریایی، و . . . از روش شولتسه استفاده کرده‌اند.
توصیف روش
برگه‌های رای
نمونه برگه رای نظام‌های انتخاباتی ترجیحی
ورودی روش شولتسه مشابه سایر نظام‌های انتخاباتی تک‌برنده ترجیحی است: رای‌دهندگان نامزدان را نسبت به هم اولویت‌بندی می‌کنند. در ذکر اولویت‌ها تساوی نیز مجاز است. همه نامزدها در برگه‌های رای فهرست شده‌اند و هر رای‌دهنده با استفاده از اعداد، این فهرست را به ترتیب ترجیحاتش رتبه‌بندی می‌کند: رای‌دهنده شایسته‌ترین نامزد را در رتبه اول می‌نشاند، و نامزد دوم از لحاظ شایستگی را در رتبه دوم قرار می‌دهد و به همین منوال ادامه می‌دهد. هر رای‌دهنده مجاز است:
چندین نامزد را در یک رتبه بنشاند. این یعنی که از نظر رای‌دهنده تفاوتی بین این نامزدان وجود ندارد.
از اعداد نامتوالی استفاده کند. این امر روی نتیجه انتخابات تاثیر نمی‌گذارد چرا که تنها ترتیب نامزدان نسبت به یکدیگر حائز اهمیت است و خود اعداد (۱ یا ۲ یا . . .) مهم نیستند.
برخی از نامزدان را رتبه‌بندی نکند که در این صورت تفسیر رفتار او چنین است: الف) نامزدان رتبه‌بندی‌شده شایسته‌تر از نامزدان رتبه‌بندی‌نشده هستند؛ ب) بین نامزدان رتبه‌بندی‌نشده تفاوتی قائل نیست.
محاسبه
را تعداد رای‌دهندگانی در نظر می‌گیریم که نامزد را به نامزد ترجیح داده‌اند.
یک مسیر از نامزد به نامزد به قدرت دنباله‌ای از نامزدان با ویژگی‌های زیر تعریف می‌شود:
و .
برای هر داریم .
برای هر داریم .
، قدرت قوی‌ترین مسیر از نامزد به نامزد ، مقدار بیشینه‌ای است به قسمی که مسیری از نامزد به نامزد با آن قدرت وجود داشته باشد. اگر اصلا مسیری از نامزد به وجود نداشته باشد، آنگاه .
نامزد از نامزد بهتر است اگر و فقط اگر .
نامزد یک برنده بالقوه است اگر و فقط اگر برای هر نامزد دیگر داشته باشیم .
می‌توان ثابت کرد که و با هم نتیجه می‌دهند . بنابراین اطمینان حاصل می‌شود که الف) تعریف بالایی از «بهتری» واقعا معرف یک رابطه ترایا است و ب) همیشه حداقل یک نامزد وجود دارد که برای هر نامزد دیگر داشته باشیم: .
مثال
در مثال ذیل ۴۵ رای‌دهنده ۵ نامزد را رتبه‌بندی می‌کنند.
۵ (بدین معنی که ترتیب ترجیحات ۵ رای‌دهنده چنین است: )
۵
۸
۳
۷
۲
۷
۸
ابتدا می‌بایست مقابله‌های رو-در-رو را محاسبه کرد. مثلا در مقابله رو-در-روی و ، تعداد رای‌دهنده را به ترجیح داده‌اند و رای‌دهنده را به . پس و . نتایج کامل مقابله‌های رو-در-رو از قرار زیر است:
گراف جهتدار به همراه برچسب‌های مقابله‌های رو-در-رو
+ ماتریس مقابله‌های رو-در-رو
d*,A
d*,B
d*,C
d*,D
d*,E
dA,*
۲۰
۲۶
۳۰
۲۲
dB,*
۲۵
۱۶
۳۳
۱۸
dC,*
۱۹
۲۹
۱۷
۲۴
dD,*
۱۵
۱۲
۲۸
۱۴
dE,*
۲۳
۲۷
۲۱
۳۱
رنگ پس‌زمینه سلول سبز است اگر وگرنه قرمز. در این مثال برنده بلامنازعی وجود ندارد که صرفا با نگاه‌انداختن به مقابله‌های رو-در-رو آشکار شود.
حالا باید قوی‌ترین مسیرها را مشخص کرد. برای آنکه قوی‌ترین مسیرها به‌آسانی به چشم آیند، نتایج مقابله‌های رو-در-رو در گراف جهت‌دار سمت چپ ترسیم شده‌اند. پیکانی که از راس به نشانه رفته‌است برچسب دارد. برای پرهیز از شلوغ‌شدن گراف، فقط در صورتی که پیکان از راس به نشانه رفته‌است (سلول‌های سبز ماتریس). در این مثال زیرا قوی‌ترین مسیر از به ، مسیر مستقیم است که قدرت ۳۳ دارد. اما زیرا قوی‌ترین مسیر از به ، مسیر مستقیم به قدرت ۲۶ نیست، بلکه مسیر غیرمستقیم است که قدرت را دارد. قدرت یک مسیر، قدرت ضعیف‌ترین رشته پیوند است.
جدول زیر قوی‌ترین مسیر از نامزد به را برای هر جفت از نامزدان با رنگ قرمز نمایش می‌دهد و ضعیف‌ترین رشته پیوند مورب شده‌است.
+قوی‌ترین مسیرها
… به A
… به B
… به C
… به D
… به E
از A …
left A-(30)-D-(28)-C-(29)-B
left A-(30)-D-(28)-C
left A-(30)-D
left A-(30)-D-(28)-C-(24)-E
از A …
از B …
left B-(25)-A
left B-(33)-D-(28)-C
left B-(33)-D
left B-(33)-D-(28)-C-(24)-E
از B …
از C …
left C-(29)-B-(25)-A
left C-(29)-B
left C-(29)-B-(33)-D
left C-(24)-E
از C …
از D …
left D-(28)-C-(29)-B-(25)-A
left D-(28)-C-(29)-B
left D-(28)-C
left D-(28)-C-(24)-E
از D …
از E …
left E-(31)-D-(28)-C-(29)-B-(25)-A
left E-(31)-D-(28)-C-(29)-B
left E-(31)-D-(28)-C
left E-(31)-D
از E …
… به A
… به B
… به C
… به D
… به E
+قدرت قوی‌ترین مسیرها
p*,A
p*,B
p*,C
p*,D
p*,E
pA,*
۲۸
۲۸
۳۰
۲۴
pB,*
۲۵
۲۸
۳۳
۲۴
pC,*
۲۵
۲۹
۲۹
۲۴
pD,*
۲۵
۲۸
۲۸
۲۴
pE,*
۲۵
۲۸
۲۸
۳۱
حال می‌توان خروجی روش شولتسه را معین کرد. مثلا در مقایسه با چون پس نامزد از نامزد بهتر است. به عنوان مثالی دیگر پس نامزد از نامزد بهتر است. اگر به همین منوال ادامه دهیم، نتیجه (رتبه‌بندی شولتسه) خواهد بود و برنده خواهد شد. به عبارت دیگر برنده است چون برای هر نامزد دیگر داریم .
اجرا
تنها مرحله دشوار در اجرای روش شولتسه، محاسبه قدرت قوی‌ترین مسیرهاست. با وجود این، این مشکل مسئله‌ای مشهور در نظریه گراف‌ها موسوم به مسئله عریض‌ترین مسیر است. یک روش ساده برای محاسبه قدرت‌ها، بکارگیری بدیل الگوریتم فلوید-وارشال است. الگوریتم در شبه‌کد زیر شرح داده شده‌است:
Input: di,j, the number of voters who prefer candidate i to candidate j.
Output: pi,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 (di,j> dj,i) then
pi,j := di,j
else
pi,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
pj,k := max ( pj,k, min ( pj,i, pi,k ) )
این الگوریتم کاراست و مدت زمان اجرایش متناسب با می‌باشد که تعداد نامزدان است.
تساوی و دیگر روال‌ها
اگر رای‌دهندگان مجاز به استفاده از تساوی در ترجیحاتشان باشند، خروجی روش شولتسه به چگونگی تفسیر تساوی در تعریف بستگی پیدا خواهد کرد. این‌ها دو انتخاب معمولند: الف) تعداد رای‌دهندگانی باشد که اکیدا را به ترجیح می‌دهند؛ ب) تفاضل تعداد رای‌دهندگانی باشد که ( را به ترجیح می‌دهند) و (رای‌دهندگانی که را به ترجیح می‌دهند). اینکه‌ها چگونه تعریف شوند در نتیجه تاثیری نمی‌گذارد. روش شولتسه فاقد چرخه است و با فرض اینکه‌ها یکتا باشند، تساوی رخ نخواهد داد.
بروز تساوی در رتبه‌بندی شولتسه نامحتمل، اما ممکن است. مارکوس شولتسه، مبدع این روش، پیشنهاد می‌کند که برگه رای یکی از رای‌دهندگان به شکل تصادفی انتخاب شود و طبق نظر او، تساوی شکسته شود و در صورت نیاز این کار تکرار شود.
روال دیگری نیز برای تعیین برنده در روش شولتسه وجود دارد که البته کندتر است:
گراف جهتدار کاملی متشکل از همه نامزدها و همه یال‌های ممکن بین نامزدها رسم کنید؛
مکررا الف) نامزدانی را که در مجموعه شوارتس نیستند (هر نامزدی که نمی‌تواند به همه دیگر نامزدها برسد) حذف کنید و ب) ضعیف‌ترین حلقه اتصال را حذف کنید؛
آخرین نامزد حذف‌نشده برنده است.
تاریخچه
روش شولتسه را مارکوس شولتسه در سال ۱۹۹۷ ابداع کرد. اولین بار در سال‌های ۹۸–۱۹۹۷ و ۲۰۰۰ بر روی این روش در میلینگ‌لیست‌های عمومی بحث شد. بعدا نرم‌افزار در خدمت منافع عمومی (۲۰۰۳)، دبیان (۲۰۰۳)، جنتو (۲۰۰۵)، تاپ‌کدر (۲۰۰۵)، ویکی‌مدیا (۲۰۰۸)، کی‌دی‌ئی (۲۰۰۸)، بنیاد نرم‌افزار آزاد اروپا (۲۰۰۸)، حزب دزدان دریایی سوئد (۲۰۰۹)، و حزب دزدان دریایی آلمان (۲۰۱۰) از این روش استفاده کردند. روش شولتسه یکی از دو روش مورد استفاده در رای‌گیری‌های چندنامزدی در ویکی‌پدیای فرانسوی است که در سال ۲۰۰۵ با رای اکثریت تصویب شد و چندین بار مورد استفاده قرار گرفته‌است.
مارکوس شولتسه در سال ۲۰۱۱ مقاله‌ای درباره این روش در ژورنال دانشگاهی رفاه و انتخاب اجتماعی منتشر کرد.
استفاده‌کنندگان
برگه رای انتخابات هیئت امنای بنیاد ویکی‌مدیا
تاکنون از روش شولتسه برای انتخابات پارلمانی استفاده نشده اما حزب دزدان دریایی سوئد از این روش برای انتخابات مقدماتی پارلمان استفاده کرده‌است. اقبال به این روش از جانب سازمان‌های عمومی رو به افزایش است. برخی از سازمان‌هایی که از این روش استفاده می‌کنند، در زیر فهرست شده‌اند:
آزمایشگاه شکر
اف‌اف‌امپگ
ام‌تی‌وی
اوبونتو
اوپن‌استک
بنیاد نرم‌افزار آزاد اروپا
جنتو لینوکس
دانشگاه نورت‌وسترن
دبیان
جنبش پنج ستاره ایتالیا (پسکارا، فوندی، کامپوباسو، مونته مورلو)
حزب دزدان دریایی آلمان، اتریش، استرالیا، ایتالیا، ایسلند، برزیل، بلژیک، سوئد، سوئیس، نیوزیلند، هلند
کوبونتو
کی‌دی‌ئی
گنو پرایوسی گارد
ویکی‌پدیای فرانسوی، عبری، مجاری، و روسی.
هسکل